Benutzer: Gast  Login
Titel:

Assembling Molecules in Atomix is Hard

Dokumenttyp:
Technical Report
Autor(en):
Markus Holzer; Stefan Schwoon
Abstract:
It is shown that assembling molecules in the Atomix game can be used to simulate finite automata. In particular, an instance of Atomix is constructed that has a solution if and only if the non-emptiness intersection problem for finite automata is solvable. This shows that the game under consideration is PSPACE-complete, improving a recent result of Hueffner et al. Thus, there are Atomix games which have superpolynomially long optimal solutions. We also give an easy construction of Atomix game le...     »
Jahr:
2001
Jahr / Monat:
2001-06-01 00:00:00
Seiten/Umfang:
17
 BibTeX