Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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.
Original language | English |
---|---|
Title of host publication | SOFSEM 2011 |
Subtitle of host publication | Theory and Practice of Computer Science - 37th Conference on Current Trends in Theory and Practice of Computer Science, Proceedings |
Pages | 431-443 |
Number of pages | 13 |
DOIs | |
State | Published - 26 Jan 2011 |
Event | 37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011 - Novy Smokovec, Slovakia Duration: 22 Jan 2011 → 28 Jan 2011 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 6543 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 37th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2011 |
---|---|
Country/Territory | Slovakia |
City | Novy Smokovec |
Period | 22/01/11 → 28/01/11 |
ID: 41142962