Comparing Linear Conjunctive Languages to Subfamilies of the Context-Free Languages - UTU Tutkimustietojärjestelmä

A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

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

Tekijät: Okhotin A

Julkaisuvuosi: 2011

Journal: Lecture Notes in Computer Science

Kokoomateoksen nimi: SOFSEM 2011:Theory and Practice of Computer Science

Tietokannassa oleva lehden nimi: SOFSEM 2011: THEORY AND PRACTICE OF COMPUTER SCIENCE

Lehden akronyymi: LECT NOTES COMPUT SC

Vuosikerta: 6543

Aloitussivu: 431

Lopetussivu: 443

Sivujen määrä: 13

ISBN: 978-3-642-18380-5

ISSN: 0302-9743

Tiivistelmä

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.