Search

eingereicht von Michael Sebastian Jahn, BSc. Kurzfassungen in deutscher und englischer Sprache Universität Linz, Univ., Masterarbeit, 2016

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.

The dissertation describes the new Bellman’s GAP which is a programming system for writing dynamic programming algorithms over sequential data. It is the second generation implementation of the algebraic dynamic programming framework (ADP). The system includes the multi-paradigm language (GAP-L), its compiler (GAP-C), functional modules (GAP-M) and a web site (GAP Pages) to experiment with GAP-L programs. GAP-L includes declarative constructs, e.g. tree grammars to model the search space, and imperative constructs for programming advanced scoring functions. The syntax of GAP-L is similar to C/Java to lower usage barriers. GAP-C translates the high-level and index-free GAP-L programs into efficient C++-Code, which is competitive with handwritten code. It includes a novel table design optimization algorithm, support for dynamic programming (DP) over multiple sequences (multi-track DP), sampling, optional top-down evaluation, various backtracing schemes etc. GAP-M includes modules for use in GAP-L programs. Examples are efficient representations of classification data types and sampling as well as filter helper functions. GAP Pages contain web dialogs for selected text book dynamic programming algorithms implemented in GAP-L. The web dialogs allow interactive ad-hoc experiments with different inputs and combinations of algebras. Several benchmarks and examples in the dissertation show the practical efficiency of Bellman’s GAP in terms of program runtime and development time.

In this dissertation, we show that that both the generative capacity and the parsing complexity of lexicalized grammar formalisms are systematically related to structural properties of the dependency structures that these formalisms can induce. Dependency structures model the syntactic dependencies among the words of a sentence. We identify three empirically relevant classes of dependency structures, and show how they can be characterized both in terms of restrictions on the relation between dependency and word-order and within an algebraic framework. In the second part of the dissertation, we develop natural notions of automata and grammars for dependency structures, show how these yield infinite hierarchies of ever more powerful dependency languages, and classify several grammar formalisms with respect to the languages in these hierarchies that they are able to characterize. Our results provide fundamental insights into the relation between dependency structures and lexicalized grammars. In dieser Arbeit zeigen wir, dass sowohl die Ausdrucksmächtigkeit als auch die Verarbeitungskomplexität von lexikalisierten Grammatikformalismen auf systematische Art und Weise von strukturellen Eigenschaften der Dependenzstrukturen abhängen, die diese Formalismen induzieren. Dependenzstrukturen modellieren die syntaktischen Abhängigkeiten zwischen den Wörtern eines Satzes. Wir identifizieren drei empirisch relevante Klassen von Dependenzstrukturen und zeigen, wie sich diese sowohl durch Einschränkungen der Interaktion zwischen Dependenz und Wortstellung, als auch in einem algebraischen Rahmen charakterisieren lassen. Im zweiten Teil der Arbeit entwickeln wir natürliche Begriffe von Automaten und Grammatiken für Dependenzstrukturen, zeigen, wie diese zu unendlichen Hierarchien immer ausdrucksmächtigerer Dependenzsprachen führen, und klassifizieren mehrere Grammatikformalismen in Bezug auf die Sprachen in diesen Hierarchien, die von ihnen charakterisiert werden können. Unsere Resultate liefern grundlegende Einsichten in das Verhältnis zwischen Dependenzstrukturen und lexikalisierten Grammatiken.