Rewriting systems working on words with a center marker are considered. The derivation is done by erasing a prefix or a suffix and then adding a prefix or a suffix. This can be naturally viewed as two stacks communicating with each other according to a fixed protocol. The paper systematically considers different cases of these systems and determines their expressiveness. Several cases are identified where very limited communication surprisingly yields universal computation power.
| Original language | English |
|---|---|
| Title of host publication | Automata, Languages and Programming - 33rd International Colloquium, ICALP 2006, Proceedings |
| Publisher | Springer Nature |
| Pages | 468-479 |
| Number of pages | 12 |
| ISBN (Print) | 3540359079, 9783540359074 |
| State | Published - 1 Jan 2006 |
| Externally published | Yes |
| Event | 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 - Venice, Italy Duration: 10 Jul 2006 → 14 Jul 2006 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 4052 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 33rd International Colloquium on Automata, Languages and Programming, ICALP 2006 |
|---|---|
| Country/Territory | Italy |
| City | Venice |
| Period | 10/07/06 → 14/07/06 |
ID: 41143994