| KARHUMÄKI, Juhani, Michal KUNC and Alexander OKHOTIN. Communication of two stacks and rewriting. In Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II. Berlin: Springer, 2006, p. 468-479. ISBN 3-540-35907-9. |
Other formats:
BibTeX
LaTeX
RIS
@inproceedings{694334,
author = {Karhumäki, Juhani and Kunc, Michal and Okhotin, Alexander},
address = {Berlin},
booktitle = {Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II},
keywords = {Multi-pushdown automaton; Word rewriting; Universal computation; Context-free language; Regular language},
language = {eng},
location = {Berlin},
isbn = {3-540-35907-9},
pages = {468-479},
publisher = {Springer},
title = {Communication of two stacks and rewriting},
url = {http://dx.doi.org/10.1007/11787006_40},
year = {2006}
}
TY - JOUR
ID - 694334
AU - Karhumäki, Juhani - Kunc, Michal - Okhotin, Alexander
PY - 2006
TI - Communication of two stacks and rewriting
PB - Springer
CY - Berlin
SN - 3540359079
KW - Multi-pushdown automaton
KW - Word rewriting
KW - Universal computation
KW - Context-free language
KW - Regular language
UR - http://dx.doi.org/10.1007/11787006_40
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 can be naturally viewed as two stacks communicating with each other according to a fixed protocol. The paper systematically considers different cases of these systems and determines their expressiveness. Several cases are identified where very limited communication surprisingly yields universal computation power.
ER -
KARHUMÄKI, Juhani, Michal KUNC and Alexander OKHOTIN. Communication of two stacks and rewriting. In \textit{Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II}. Berlin: Springer, 2006, p.~468-479. ISBN~3-540-35907-9.
|
