On the equivalence of linear conjunctive grammars and trellis automata

Issue		RAIRO-Theor. Inf. Appl. Volume 38, Number 1, January-March 2004


Page(s)		69 - 88
DOI		10.1051/ita:2004004

Theoret. Informatics Appl. 38, 69-88 (2004)
DOI: 10.1051/ita:2004004

On the equivalence of linear conjunctive grammars and trellis automata

Alexander Okhotin

School of Computing, Queen's University, Kingston, Ontario, Canada; okhotin@cs.queensu.ca.

(Accepted January 15, 2004.)

Abstract
This paper establishes computational equivalence of two seemingly unrelated concepts: linear conjunctive grammars and trellis automata. Trellis automata, also studied under the name of one-way real-time cellular automata, have been known since early 1980s as a purely abstract model of parallel computers, while linear conjunctive grammars, introduced a few years ago, are linear context-free grammars extended with an explicit intersection operation. Their equivalence implies the equivalence of several other formal systems, including a certain restricted class of Turing machines and a certain type of language equations, thus giving further evidence for the importance of the language family they all generate.

Mathematics Subject Classification. 68Q01, 68Q42, 68Q70, 68Q80.

Key words: Conjunctive grammar -- trellis automaton -- cellular automaton -- language equation -- Turing machine.

© EDP Sciences 2004

What is OpenURL?

The OpenURL standard is a protocol for transmission of metadata describing the resource that you wish to access. An OpenURL link contains article metadata and directs it to the OpenURL server of your choice. The OpenURL server can provide access to the resource and also offer complementary services (specific search engine, export of references...). The OpenURL link can be generated by different means.

If your librarian has set up your subscription with an OpenURL resolver, OpenURL links appear automatically on the abstract pages.
You can define your own OpenURL resolver with your EDPS Account. In this case your choice will be given priority over that of your library.
You can use an add-on for your browser (Firefox or I.E.) to display OpenURL links on a page (see http://www.openly.com/openurlref/). You should disable this module if you wish to use the OpenURL server that you or your library have defined.