Communication of two stacks and rewriting
| Authors | |
|---|---|
| Year of publication | 2006 |
| Type | Article in Proceedings |
| Conference | Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II |
| MU Faculty or unit | |
| Citation | |
| web | http://dx.doi.org/10.1007/11787006_40 |
| Field | General mathematics |
| Keywords | Multi-pushdown automaton; Word rewriting; Universal computation; Context-free language; Regular language |
| Description | 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. |
| Related projects: |