TY - GEN

T1 - Comparing linear conjunctive languages to subfamilies of the context-free languages

AU - Okhotin, Alexander

PY - 2011/1/26

Y1 - 2011/1/26

N2 - Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable to the context-free languages (Terrier, "On real-time one-way cellular array", Theoret. Comput. Sci., 1995). This paper investigates subclasses of the context-free languages for possible containment in this class. It is shown that every visibly pushdown automaton (Alur, Madhusudan, "Visibly pushdown languages", STOC 2004) can be simulated by a one-way real-time cellular automaton, but already for LL(1) context-free languages and for one-counter DPDAs no simulation is possible.

AB - Linear conjunctive grammars define the same family of languages as one-way real-time cellular automata (Okhotin, "On the equivalence of linear conjunctive grammars to trellis automata", RAIRO ITA, 2004), and this family is known to be incomparable to the context-free languages (Terrier, "On real-time one-way cellular array", Theoret. Comput. Sci., 1995). This paper investigates subclasses of the context-free languages for possible containment in this class. It is shown that every visibly pushdown automaton (Alur, Madhusudan, "Visibly pushdown languages", STOC 2004) can be simulated by a one-way real-time cellular automaton, but already for LL(1) context-free languages and for one-counter DPDAs no simulation is possible.

UR - http://www.scopus.com/inward/record.url?scp=78751675091&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-18381-2_36

DO - 10.1007/978-3-642-18381-2_36

M3 - Conference contribution

AN - SCOPUS:78751675091

SN - 9783642183805

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 431

EP - 443

BT - SOFSEM 2011

T2 - 37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011

Y2 - 22 January 2011 through 28 January 2011

ER -