KARHUMÄKI, Juhani, Michal KUNC a Alexander OKHOTIN. Computational power of two stacks with restricted communication. Information and Computation. Amsterdam: Elsevier, 2010, roč. 208, č. 9, s. 1060-1089. ISSN 0890-5401. |
Další formáty:
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 a Alexander OKHOTIN. Computational power of two stacks with restricted communication. \textit{Information and Computation}. Amsterdam: Elsevier, 2010, roč.~208, č.~9, s.~1060-1089. ISSN~0890-5401.
|