Undecidability Results for Bisimilarity on Prefix Rewrite Systems

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F06%3A00013662" target="_blank" >RIV/61989100:27240/06:00013662 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—

Result language
angličtina
Original language name
Undecidability Results for Bisimilarity on Prefix Rewrite Systems
Original language description
We answer an open question related to bisimilarity checking on labelled transition systems generated by prefix rewrite rules on words. Stirling (1996, 1998) proved the decidability of bisimilarity for normed pushdown processes. This result was substantially extended by S'{e}nizergues (1998, 2005) who showed the decidability for regular (or equational) graphs of finite out-degree (which include unnormed pushdown processes). The question of decidability of bisimilarity for a more general class of so called Type -1 systems (generated by prefix rewrite rules of the form $R goes{a} w$ where $R$ is a regular language) was left open; this was repeatedly indicated by both Stirling and S'{e}nizergues. Here we answer the question negatively, i.e., we show undecidability of bisimilarity on Type -1 systems, even in the normed case.
Czech name
Nerozhodnutelnost pro bisimilaritu na prefixových přepisovacích systémech
Czech description
Zodpovídáme otevřenou otázku týkající se bisimilarity na prefixových přepisovacích systémech. Otázka byla nastolena Stirlingem a Senizerguesem a týká se systémů generovaných pravidly typu R --> w , kde R je regulární jazyk. Zde ukazujeme nerozhodnutelnost příslušného problému a doplňujeme několik dalších výsledků.

Project
<a href="/en/project/1M0567" target="_blank" >1M0567: Centre for Applied Cybernetics</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year
2006
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)