User: Guest  Login
Title:

Assembling Molecules in Atomix is Hard

Document type:
Technical Report
Author(s):
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...     »
Year:
2001
Year / month:
2001-06-01 00:00:00
Pages:
17
 BibTeX