| KARHUMÄKI, Juhani, Michal KUNC and Alexander OKHOTIN. Computational power of two stacks with restricted communication. Information and Computation. Amsterdam: Elsevier, 2010, vol. 208, No 9, p. 1060-1089. ISSN 0890-5401. |
Other formats:
BibTeX
LaTeX
RIS
@article{850976,
author = {Karhumäki, Juhani and Kunc, Michal and Okhotin, Alexander},
article_location = {Amsterdam},
article_number = {9},
keywords = {Word rewriting; String rewriting; Post systems; Multi-pushdown machines; Communication; Universality},
language = {eng},
issn = {0890-5401},
journal = {Information and Computation},
title = {Computational power of two stacks with restricted communication},
url = {http://dx.doi.org/10.1016/j.ic.2009.07.001},
volume = {208},
year = {2010}
}
TY - JOUR
ID - 850976
AU - Karhumäki, Juhani - Kunc, Michal - Okhotin, Alexander
PY - 2010
TI - Computational power of two stacks with restricted communication
JF - Information and Computation
VL - 208
IS - 9
SP - 1060
EP - 1060
PB - Elsevier
SN - 08905401
KW - Word rewriting
KW - String rewriting
KW - Post systems
KW - Multi-pushdown machines
KW - Communication
KW - Universality
UR - http://dx.doi.org/10.1016/j.ic.2009.07.001
N2 - 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.
ER -
KARHUMÄKI, Juhani, Michal KUNC and Alexander OKHOTIN. Computational power of two stacks with restricted communication. \textit{Information and Computation}. Amsterdam: Elsevier, 2010, vol.~208, No~9, p.~1060-1089. ISSN~0890-5401.
|
