A1 Refereed original research article in a scientific journal
Computational power of two stacks with restricted communication
Authors: Karhumaki Juhani, Kunc Michal, Okhotin Alexander
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2010
Journal: Information and Computation
Journal name in source: INFORMATION AND COMPUTATION
Journal acronym: INFORM COMPUT
Number in series: 9
Volume: 208
Issue: 9
First page : 1060
Last page: 1089
Number of pages: 30
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2009.07.001
Abstract
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.
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.
UTU Research Portal