Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
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.
| Original language | English |
|---|---|
| Title of host publication | LATIN 2014 |
| Subtitle of host publication | Theoretical Informatics - 11th Latin American Symposium, Proceedings |
| Publisher | Springer Nature |
| Pages | 190-201 |
| Number of pages | 12 |
| ISBN (Print) | 9783642544224 |
| DOIs | |
| State | Published - 1 Jan 2014 |
| Event | 11th Latin American Theoretical Informatics Symposium, LATIN 2014 - Montevideo, Uruguay Duration: 31 Mar 2014 → 4 Apr 2014 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 8392 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 11th Latin American Theoretical Informatics Symposium, LATIN 2014 |
|---|---|
| Country/Territory | Uruguay |
| City | Montevideo |
| Period | 31/03/14 → 4/04/14 |
ID: 41478686