Další formáty:
BibTeX
LaTeX
RIS
@article{492122, author = {Jurdzinski, Martin and Mogens, Nielsen and Srba, Jiří}, article_location = {Netherlands}, article_number = {2}, keywords = {partial order; bisimilarity; domino games}, language = {eng}, issn = {0890-5401}, journal = {Information and Computation}, title = {Undecidability of Domino Games and Hhp-Bisimilarity}, url = {http://www.brics.dk/~srba/publ.html}, volume = {184}, year = {2003} }
TY - JOUR ID - 492122 AU - Jurdzinski, Martin - Mogens, Nielsen - Srba, Jiří PY - 2003 TI - Undecidability of Domino Games and Hhp-Bisimilarity JF - Information and Computation VL - 184 IS - 2 SP - 343-368 EP - 343-368 PB - Springer-Verlag SN - 08905401 KW - partial order KW - bisimilarity KW - domino games UR - http://www.brics.dk/~srba/publ.html N2 - History preserving bisimilarity (hp-bisimilarity) and hereditary history preserving bisimilarity (hhp-bisimilarity) are behavioural equivalences taking into account causal relationships between events of concurrent systems. Their prominent feature is that they are preserved under action refinement, an operation important for the top-down design of concurrent systems. It is shown that, in contrast to hp-bisimilarity, checking hhp-bisimilarity for finite labelled asyn\-chro\-nous transition systems is undecidable, by a reduction from the halting problem of 2-counter machines. To make the proof more transparent a novel intermediate problem of checking domino bisimilarity for origin constrained tiling systems is introduced and shown undecidable. It is also shown that the unlabelled domino bisimilarity problem is undecidable, which implies undecidability of hhp-bisimilarity for unlabelled finite asynchronous systems. Moreover, it is argued that the undecidability of hhp-bisimilarity holds for finite elementary net systems and 1-safe Petri nets. ER -
JURDZINSKI, Martin, Nielsen MOGENS a Jiří SRBA. Undecidability of Domino Games and Hhp-Bisimilarity. \textit{Information and Computation}. Netherlands: Springer-Verlag, 2003, roč.~184, č.~2, s.~343-368. ISSN~0890-5401.
|