- Assembling Molecules in Atomix is Hard. Theoretical Computer Science 303(3), pages 447-462, 2004. ( PDF ) .

- 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 Hüffner
*et al.*Thus, there are Atomix games which have superpolynomially long optimal solutions. We also give an easy construction of Atomix game levels whose optimal solutions meet the worst case.

@article{HS-tcs04, | ||

author = |
{Holzer, Markus and Schwoon, Stefan}, | |

journal = |
{Theoretical Computer Science}, | |

month = | feb,
| |

number = | {3},
| |

pages = |
{447-462}, | |

publisher = |
{Elsevier Science Publishers}, | |

title = |
{Assembling Molecules in {A}tomix is Hard}, | |

url = |
{http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/hs-tcs04.pdf},
| |

volume = |
{303}, | |

year = |
{2004}, | |

} |

- Private Pages
- Page maintained by the BibLSV group.