Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen: http://dx.doi.org/10.18419/opus-2706
Autor(en): Kopecki, Steffen
Titel: Formal language theory of hairpin formations
Sonstige Titel: Formalsprachliche Theorie der Haarnadelstruktur
Erscheinungsdatum: 2011
Dokumentart: Dissertation
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-63784
http://elib.uni-stuttgart.de/handle/11682/2723
http://dx.doi.org/10.18419/opus-2706
Zusammenfassung: The (bounded) hairpin completion, the hairpin lengthening, and their iterated versions are operations on formal languages which have been inspired by the hairpin formation in DNA biochemistry. In this paper we discuss the hairpin formations from a language theoretic point of view. The hairpin completion of a formal language has been defined in 2006. In the first paper on this topic it has been shown that the hairpin completion of a regular language is not necessarily regular but always linear context-free. In the same paper the open problem was stated, if it is decidable, whether the hairpin completion of a regular language is regular. We solved this problem positively in 2009. Here, we prove that the problem is NL-complete and we present an algorithm whose time complexity is bounded by a polynomial of degree 8. As a by-product of our technique to prove the complexities, we obtain that the hairpin completion of a regular language is actually an unambiguous linear context-free language. In addition, we provide results concerning language classes within the regular languages. We show that if the hairpin completion of an aperiodic (i.e., star-free) language is regular, then the hairpin completion is aperiodic, too. The same is true for the language class induced by the variety LDA. The hairpin lengthening is a variant of the hairpin completion which has been investigated first in 2010. The hairpin lengthening of a regular language seems to behave quite similar to the hairpin completion: It is not necessarily regular but linear context-free. We prove, however, that the hairpin lengthening of a regular language may be an inherent ambiguous linear language. We also consider the problem if it is decidable, whether the hairpin lengthening of a regular language is regular, but we are only able to prove decidability for the one-sided case of hairpin lengthening. (The one-sided case is closer to biochemistry, yet the two-sided case is more interesting from a theoretic point of view). The bounded hairpin completion can be seen as a weaker variant of the hairpin completion. It is well-known that all language classes in the Chomsky hierarchy are closed under bounded hairpin completion and that context-free, context-sensitive, and recursively enumerable languages are closed under iterated bounded hairpin completion. In 2009 it was asked in literature, whether the regular languages are closed under iterated bounded hairpin completion as well. We solve this question by presenting a more general result. We give an effective representation for the iterated bounded hairpin completion which uses union, intersection with regular sets, and concatenation with regular. Thus, all lan- guage classes which are (effectively) closed under these basic operations are also (effectively) closed under iterated bounded hairpin completion. This applies to all classes in the Chomsky hierarchy and to all usual complexity classes. Furthermore, we give an exponential lower and upper bound for the size of non-deterministic finite automata accepting the iterated bounded hairpin completion of a regular language. The iterated (unbounded) hairpin completion of a regular language is known to be context-sensitive and it may be not context-free. However, it is was not known whether the iterated hairpin completion of a singleton (or finite language) is always regular or context-free. This was stated as an open problem in 2008. In contrast to the previous questions this one has a negative answer. We give an example of a singleton whose iterated hairpin completion is not context-free.
Die (begrenzete) Haarnadel Vervollständigung, die Haarnadel Verlängerung und ihre iterierten Varianten sind Operationen auf formalen Sprachen, welche durch die Haarnadelstruktur in der DNA Biochemie inspiriert sind. In dieser Arbeit behandeln wir die formalsprachliche Theorie der Haarnadelstrukturen. In 2006 wurde die Haarnadel Vervollständigung von formalen Sprachen eingeführt. Aus der ersten Arbeit über Haarnadel Vervollständigungen ist bekannt, dass die Haarnadel Vervollständigung einer regulären Sprachen nicht regulär sein muss, aber immer linear kontextfrei ist. Ebenfalls in 2006 wurde das offene Problem gestellt, ob entscheidbar ist, ob die Haarnadel Vervollständigung einer regulären Sprache wieder regulär ist. Wir haben das Problem in 2009 gelöst. Hier zeigen wir, dass das Problem NL-vollständig ist, und wir werden einen Entscheidungsalgorithmus für das Problem angeben, dessen Zeitkomplexität durch ein Polynom achten Grades beschränkt ist. Aus dem Beweis der Komplexität können wir zudem folgern, dass die Haarnadel Vervollständigung einer regulären Sprache durch eine eindeutige linear kontextfreie Grammatik erzeugt wird. Darüber hinaus untersuchen wir die Haarnadel Vervollständigung von Sprachklassen innerhalb der regulären Sprachen. Wir zeigen, dass, wenn die Haarnadel Vervollständigung einer aperiodischen (d.h. sternfreien) Sprache regulär ist, dann ist sie wieder aperiodisch. Ein analoges Resultat zeigen wir für die Sprachklasse, welche durch die Varietät LDA induziert wird. Die Haarnadel Verlängerung ist eine Variante der Haarnadel Vervollständigung, welche 2010 eingeführt wurde. Für die Haarnadel Verlängerung einer regulären Sprache gilt ebenfalls, dass sie nicht regulär sein muss, aber immer linear kontextfrei ist. Wir zeigen, dass die Haarnadel Verlängerung einer regulären Sprache, im Gegensatz zur Haarnadel Vervollständigung, eine inhärent mehrdeutige Sprache sein kann. Wir betrachten ebenfalls das Entscheidungsproblem, ob die Haarnadel Verlängerung einer regulären Sprache regulär ist. Allerdings können wir nur beweisen, dass das Problem für den einseitigen Spezialfall entscheidbar ist. (Der einseitige Fall beschreibt die biochemischen Prozesse besser, der beidseitige Fall ist allerdings aus einer theoretischen Sicht interessanter.) Die begrenzte Haarnadel Vervollständigung kann als eine schwächere Variante der Haarnadel Vervollständigung gesehen werden. Es ist bekannt, dass alle Klassen in der Chomsky Hierarchie unter begrenzter Haarnadel Vervollständigung abgeschlossen sind und dass die kontextfreien, kontextsensitiven und rekursiv aufzählbaren Sprachen unter iterierter, begrenzter Haarnadel Vervollständigung abgeschlossen sind. 2009 wurde die Frage, ob reguläre Sprachen ebenfalls unter iterierter begrenzter Haarnadel Vervollständigung abgeschlossen sind, als offenes Problem gestellt. Wir lösen dieses Problem und zeigen ein allgemeineres Resultat: Wir geben eine effektive Darstellung der iterierten begrenzten Haarnadel Vervollständigung einer Sprache an, die nur die Operationen Vereinigung, Durchschnitt mit regulären Sprachen und Konkatenation mit regulären Sprachen nutzt. Somit sind alle Sprachklassen, die unter diesen drei elementaren Operationen (effektiv) abgeschlossen sind, ebenfalls unter iterierter, begrenzter Haarnadel Vervollständigung (effektiv) abgeschlossen. Dies trifft auf alle Klassen in der Chomsky Hierarchie und auf alle üblichen Komplexitätsklassen zu. Des weiteren geben wir eine exponentielle untere und obere Schranke für die Größe nicht-deterministischer Automaten an, die die iterierte, begrenzte Haarnadel Vervollständigung einer regulären Sprache akzeptieren. Es ist bekannt, dass die iterierte (unbegrenzte) Haarnadel Vervollständigung einer regulären Sprache kontextsensitiv und nicht immer kontextfrei ist. In 2008 wurde das offene Problem gestellt, ob die iterierte Haarnadel Vervollständigung einer einenlementigen Sprache (oder einer endlichen Sprache) nicht regulär oder nicht kontextfrei sein kann. Wir lösen dieses Problem, indem wir eine einelementige Sprache angeben, deren iterierte Haarnadel Vervollständigung nicht kontextfrei ist.
Enthalten in den Sammlungen:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
main.pdf555,68 kBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.