Solving a PSPACE-complete problem by gene assembly

Thomas ZerjatkeThomas Zerjatke, Monika SturmMonika Sturm

DOI Link

Thomas Zerjatke, Monika Sturm
Solving a PSPACE-complete problem by gene assembly
Journal of Logic and Computation, 23(4):897-908, 2013

Details
Bibtex

KurzfassungAbstract
Gene assembly is a natural process of genome re-arrangement that occurs during sexual reproduction of unicellular organisms called ciliates. Two computational models adapting this process of gene assembly have been proposed: the intramolecular, e.g. (Ehrenfeucht et al., 2004, Computation in Living Cells: Gene Assembly in Ciliates), and the intermolecular model, e.g. (Landweber and Kari, 2001, Evolution as Computation). A context sensitive version of the intramolecular model introduced by Ishdorj and Petre (2007, Proceedings of the 6th International Conference on Unconventional Computation) was shown to be computationally universal and efficient for solving NP-complete problems. In this article we show that within this model PSPACE-complete problems can also be solved in linear time.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@article{ ZeSt-JLC-13,
  author = {Thomas {Zerjatke} and Monika {Sturm}},
  doi = {\url{http://dx.doi.org/10.1093/logcom/exr052}},
  journal = {Journal of Logic and Computation},
  number = {4},
  pages = {897--908},
  publisher = {Oxford University Press},
  title = {Solving a {PSPACE}-complete problem by gene assembly},
  volume = {23},
  year = {2013},
}