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.

Original languageEnglish
Title of host publicationSOFSEM 2011
Subtitle of host publicationTheory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Pages431-443
Number of pages13
DOIs
StatePublished - 26 Jan 2011
Event37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011 - Novy Smokovec, Slovakia
Duration: 22 Jan 201128 Jan 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6543 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011
Country/TerritorySlovakia
CityNovy Smokovec
Period22/01/1128/01/11

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41142962