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