DOI

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.

Язык оригиналаанглийский
Название основной публикацииSOFSEM 2011
Подзаголовок основной публикацииTheory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings
Страницы431-443
Число страниц13
DOI
СостояниеОпубликовано - 26 янв 2011
Событие37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011 - Novy Smokovec, Словакия
Продолжительность: 22 янв 201128 янв 2011

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том6543 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011
Страна/TерриторияСловакия
ГородNovy Smokovec
Период22/01/1128/01/11

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 41142962