Hereditary History Preserving Simulation is Undecidable

Forfattere

  • Marcin Jurdzinski
  • Mogens Nielsen

DOI:

https://doi.org/10.7146/brics.v6i1.19501

Resumé

We 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.

Downloads

Publiceret

1999-01-01

Citation/Eksport

Jurdzinski, M., & Nielsen, M. (1999). Hereditary History Preserving Simulation is Undecidable. BRICS Report Series, 6(1). https://doi.org/10.7146/brics.v6i1.19501