Bibliograph. Daten | Diekert, Volker; Kopecki, Steffen: Complexity Results and the Growths of Hairpin Completions of Regular Languages. Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik, Technischer Bericht Informatik Nr. 2010/04. 16 Seiten, englisch.
|
CR-Klassif. | F.4.3 (Formal Languages)
|
Keywords | Automata and Formal Languages; Finite Automata; DNA-Computing; Hairpin Completion |
Kurzfassung | The hairpin completion is a natural operation on formal languages which has been inspired by molecular phenomena in biology and by DNA-computing. In 2009 we presented a (polynomial time) decision algorithm to decide regularity of the hairpin completion. In this paper we provide four new results:
1.) We show that the decision problem is NL-complete.
2.) There is a polynomial time decision algorithm which runs in time O(n^8), this improves our previous results, which provided O(n^{20}).
3.) For the one-sided case (which is closer to DNA computing) the time is O(n^2), only.
4.) The hairpin completion of a regular language is unambiguous linear context-free. This result allows to compute the growth (generating function) of the hairpin completion and to compare it with the growth of the underlying regular language.
|
Volltext und andere Links | PDF (413087 Bytes)
|
Kontakt | steffen.kopecki@fmi.uni-stuttgart.de |
Abteilung(en) | Universität Stuttgart, Institut für Formale Methoden der Informatik, Theoretische Informatik
|
Eingabedatum | 28. Juni 2010 |
---|