Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
The paper considers a family of formal grammars that extends linear context-free grammars with an operator for referring to the left context of a substring being defined, as well as with a conjunction operation (as in linear conjunctive grammars). These grammars are proved to be computationally equivalent to an extension of one-way real-time cellular automata with an extra data channel. The main result is the undecidability of the emptiness problem for grammars restricted to a one-symbol alphabet, which is proved by simulating a Turing machine by a cellular automaton with feedback. The same construction proves the σ02-completeness of the finiteness problem for these grammars.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | LATIN 2014 |
| Подзаголовок основной публикации | Theoretical Informatics - 11th Latin American Symposium, Proceedings |
| Издатель | Springer Nature |
| Страницы | 190-201 |
| Число страниц | 12 |
| ISBN (печатное издание) | 9783642544224 |
| DOI | |
| Состояние | Опубликовано - 1 янв 2014 |
| Событие | 11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Уругвай Продолжительность: 31 мар 2014 → 4 апр 2014 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 8392 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 11th Latin American Theoretical Informatics Symposium, LATIN 2014 |
|---|---|
| Страна/Tерритория | Уругвай |
| Город | Montevideo |
| Период | 31/03/14 → 4/04/14 |
ID: 41478686