Computational power of two stacks with restricted communication



: Karhumaki Juhani, Kunc Michal, Okhotin Alexander

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2010

: Information and Computation

: INFORMATION AND COMPUTATION

: INFORM COMPUT

: 9

: 208

: 9

: 1060

: 1089

: 30

: 0890-5401

DOI: https://doi.org/10.1016/j.ic.2009.07.001


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. (C) 2009 Elsevier Inc. All rights reserved.



Last updated on 2024-26-11 at 17:50