@article{Jurdzinski_Nielsen_1999, title={Hereditary History Preserving Bisimilarity is Undecidable}, volume={6}, url={https://tidsskrift.dk/brics/article/view/20076}, DOI={10.7146/brics.v6i19.20076}, abstractNote={We show undecidability of hereditary history preserving bisimilarity<br />for finite asynchronous transition systems by a reduction from the halting<br />problem of deterministic 2-counter machines. To make the proof more<br />transparent we introduce an intermediate problem of checking domino<br />bisimilarity for origin constrained tiling systems. First we reduce the<br />halting problem of deterministic 2-counter machines to origin constrained<br />domino bisimilarity. Then we show how to model domino bisimulations as<br />hereditary history preserving bisimulations for finite asynchronous transitions<br />systems. We also argue that the undecidability result holds for<br />finite 1-safe Petri nets, which can be seen as a proper subclass of finite<br />asynchronous transition systems.}, number={19}, journal={BRICS Report Series}, author={Jurdzinski, Marcin and Nielsen, Mogens}, year={1999}, month={Jan.} }