Position-and-Length-Dependent Context-Free Grammars - A New Type of Restricted Rewriting

  • For many decades, the search for language classes that extend the context-free laguages enough to include various languages that arise in practice, while still keeping as many of the useful properties that context-free grammars have - most notably cubic parsing time - has been one of the major areas of research in formal language theory. In this thesis we add a new family of classes to this field, namely position-and-length-dependent context-free grammars. Our classes use the approach of regulated rewriting, where derivations in a context-free base grammar are allowed or forbidden based on, e.g., the sequence of rules used in a derivation or the sentential forms, each rule is applied to. For our new classes we look at the yield of each rule application, i.e. the subword of the final word that eventually is derived from the symbols introduced by the rule application. The position and length of the yield in the final word define the position and length of the rule application and each rule is associated a set of positions and lengths where it is allowed to be applied. We show that - unless the sets of allowed positions and lengths are really complex - the languages in our classes can be parsed in the same time as context-free grammars, using slight adaptations of well-known parsing algorithms. We also show that they form a proper hierarchy above the context-free languages and examine their relation to language classes defined by other types of regulated rewriting. We complete the treatment of the language classes by introducing pushdown automata with position counter, an extension of traditional pushdown automata that recognizes the languages generated by position-and-length-dependent context-free grammars, and we examine various closure and decidability properties of our classes. Additionally, we gather the corresponding results for the subclasses that use right-linear resp. left-linear base grammars and the corresponding class of automata, finite automata with position counter. Finally, as an application of our idea, we introduce length-dependent stochastic context-free grammars and show how they can be employed to improve the quality of predictions for RNA secondary structures.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar
Verfasserangaben:Frank Weinberg
URN (Permalink):urn:nbn:de:hbz:386-kluedo-38142
Betreuer:Markus Nebel
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):26.06.2014
Jahr der Veröffentlichung:2014
Veröffentlichende Institution:Technische Universität Kaiserslautern
Titel verleihende Institution:Technische Universität Kaiserslautern
Datum der Annahme der Abschlussarbeit:03.03.2014
Datum der Publikation (Server):27.06.2014
GND-Schlagwort:Endlicher Automat; Formale Grammatik; Formale Sprache; Kellerautomat
Seitenzahl:VIII, 96
Fachbereiche / Organisatorische Einheiten:Fachbereich Informatik
CCS-Klassifikation (Informatik):F. Theory of Computation / F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES / F.4.3 Formal Languages (D.3.1) / Classes defined by grammars or automata (e.g., context-free languages, regular sets, recursive sets)
DDC-Sachgruppen:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 10.09.2012