Computational power of two stacks with restricted communication

Warning

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

Authors	KARHUMÄKI Juhani KUNC Michal OKHOTIN Alexander
Year of publication	2010
Type	Article in Periodical
Magazine / Source	Information and Computation
MU Faculty or unit	Faculty of Science
Citation
Web	http://dx.doi.org/10.1016/j.ic.2009.07.001
Field	General mathematics
Keywords	Word rewriting; String rewriting; Post systems; Multi-pushdown machines; Communication; Universality
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 models a communication of two stacks according to a fixed protocol defined by the choice of rewriting rules. The paper systematically considers different cases of these systems and determines their expressive power. Several cases are identified where very restricted communication surprisingly yields computational universality.
Related projects:	Mathematical structures and their physical applications Algebraic Methods in Automata and Formal Language Theory II