A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Computational power of two stacks with restricted communication
Tekijät: Karhumaki Juhani, Kunc Michal, Okhotin Alexander
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2010
Journal: Information and Computation
Tietokannassa oleva lehden nimi: INFORMATION AND COMPUTATION
Lehden akronyymi: INFORM COMPUT
Numero sarjassa: 9
Vuosikerta: 208
Numero: 9
Aloitussivu: 1060
Lopetussivu: 1089
Sivujen määrä: 30
ISSN: 0890-5401
DOI: https://doi.org/10.1016/j.ic.2009.07.001
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali