2006
Communication of two stacks and rewriting
KARHUMÄKI, Juhani; Michal KUNC and Alexander OKHOTINBasic information
Original name
Communication of two stacks and rewriting
Name in Czech
Komunikace dvou zásobníků a přepisování
Authors
KARHUMÄKI, Juhani (246 Finland); Michal KUNC (203 Czech Republic, guarantor) and Alexander OKHOTIN (643 Russian Federation)
Edition
Berlin, Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part II, p. 468-479, 2006
Publisher
Springer
Other information
Language
English
Type of outcome
Proceedings paper
Field of Study
10101 Pure mathematics
Country of publisher
Germany
Confidentiality degree
is not subject to a state or trade secret
References:
RIV identification code
RIV/00216224:14330/06:00017106
Organization unit
Faculty of Informatics
ISBN
3-540-35907-9
UT WoS
000239475900040
Keywords in English
Multi-pushdown automaton; Word rewriting; Universal computation; Context-free language; Regular language
Tags
Changed: 24/3/2010 11:15, doc. Mgr. Michal Kunc, Ph.D.
In the original language
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.
In Czech
V práci se zabýváme přepisovacími systémy pracujícími na slovech se středovou značkou. Odvozování se provádí umazáním prefixu nebo sufixu a následným přidáním prefixu nebo sufixu. Tento proces je možné přirozeně chápat jako vzájemnou komunikaci dvou zásobníků podle jistého pevného protokolu. Systematicky uvažujeme různé případy těchto systémů a určujeme jejich vyjadřovací schopnost. Nalézáme několik případů, kde velmi omezená komunikace překvapivě poskytuje univerzální výpočetní sílu.
Links
| 1M0545, research and development project |
|