Communication of two stacks and rewriting

Warning

This publication doesn't include Faculty of Arts. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander

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

Faculty of Informatics

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:

You are running an old browser version. We recommend updating your browser to its latest version.