Options
The decidability border of hereditary history preserving bisimilarity
Publikationstyp
Journal Article
Date Issued
2004-12-29
Sprache
English
Author(s)
Journal
Volume
93
Issue
6
Start Page
289
End Page
293
Citation
Information Processing Letters 93 (6): 289-293 (2005-03-31)
Publisher DOI
Scopus ID
Publisher
Elsevier
The decidability border of the weaker hereditary history preserving bisimilarity is discussed. A domino system D is universally encoded by a finite system N(D) such that the building of a domino snake can be faithfully mimicked by a special pattern of forwards and backtrack moves in the unfolding structure of N(D). The domino bisimilarity is undecidable by a reduction from the halting problem of 2-counter machines. Theoretical investigation suggests that finding the borderline is difficult.
Subjects
Bisimulation games
Concurrency
Infinite-space verification
True-concurrency
DDC Class
004: Informatik