KARHUMÄKI, Juhani, Michal KUNC a 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, s. 468-479. ISBN 3-540-35907-9. |
Další formáty:
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 a 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, s.~468-479. ISBN~3-540-35907-9.
|