User: Guest  Login
Document type:
Technical Report 
Author(s):
Markus Holzer; Stefan Schwoon 
Title:
Assembling Molecules in Atomix is Hard 
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 
versions