Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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 янв 2011 → 28 янв 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/11 → 28/01/11 |
ID: 41142962