## 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.

Author: | Frank Weinberg |
---|---|

URN (permanent link): | urn:nbn:de:hbz:386-kluedo-38142 |

Advisor: | Markus Nebel |

Document Type: | Doctoral Thesis |

Language of publication: | English |

Publication Date: | 2014/06/26 |

Year of Publication: | 2014 |

Publishing Institute: | Technische Universität Kaiserslautern |

Granting Institute: | Technische Universität Kaiserslautern |

Acceptance Date of the Thesis: | 2014/03/03 |

Date of the Publication (Server): | 2014/06/27 |

GND-Keyword: | Endlicher Automat; Formale Grammatik; Formale Sprache; Kellerautomat |

Number of page: | VIII, 96 |

Faculties / Organisational entities: | Fachbereich Informatik |

CCS-Classification (computer science): | 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-Cassification: | 0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik |

Licence (German): | Standard gemäß KLUEDO-Leitlinien vom 10.09.2012 |