Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages



: Okhotin A

: 2011

: Lecture Notes in Computer Science

: SOFSEM 2011:Theory and Practice of Computer Science

: SOFSEM 2011: THEORY AND PRACTICE OF COMPUTER SCIENCE

: LECT NOTES COMPUT SC

: 6543

: 431

: 443

: 13

: 978-3-642-18380-5

: 0302-9743


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.



Last updated on 2024-26-11 at 12:39