Hereditary History Preserving Simulation is Undecidable
AbstractWe show undecidability of hereditary history preserving simulation
for finite asynchronous transition systems by a reduction from the halting
problem of deterministic Turing machines. To make the proof more
transparent we introduce an intermediate problem of deciding the winner
in domino snake games. First we reduce the halting problem of deterministic
Turing machines to domino snake games. Then we show how to
model a domino snake game by a hereditary history simulation game on
a pair of finite asynchronous transition systems.
How to Cite
Jurdzinski, M., & Nielsen, M. (1999). Hereditary History Preserving Simulation is Undecidable. BRICS Report Series, 6(1). https://doi.org/10.7146/brics.v6i1.19501
Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.