TU Darmstadt / ULB / TUbiblio

Persistent Arrays, Path Problems, and Context-free Languages

Glier, Oliver (2005)
Persistent Arrays, Path Problems, and Context-free Languages.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

Abstract

The goal of this thesis is to provide a framework for several path problems for graphs. From the conceptual part, there are context-free grammars and semirings. Context-free grammars allow us to describe recursive generative processes, such as in grammars for natural languages or in models for the growth of cell complexes. They also capture the structure of certain dynamic programming schemes, as it is used in the CYK algorithm for context-free parsing and of some pseudo-polynomial algorithms for hard problems. The connection of context-free grammars with path problems in graphs allows us to model several language-restrictions for feasible paths and thus generalizes the classic shortest-path problem. On the other hand --- similarly to the algebraic shortest path problem --- context-free grammars can be equipped with semiring values. In chapter 4 of this thesis, we explore the relationship between semiring-valued context-free grammars and path problems. The connection is fruitful since it gives us a conceptual framework for many generalizations of the path problem. For instance it allows us to formulate tentative polynomial-time algorithms for transportation problems which cannot, or only with great difficulty, formulated as conventional shortest-path problems. As one can observe, language-restrictions on paths might cause the shortest feasible paths to grow exponentially. Persistent arrays, represented as balanced binary trees, allow us to deal with this problem and still maintain polynomial-time computability. The ability to represent certain exponentially long arrays in polynomial space gives rise to the question what kind of computations they apply to. Indeed, even determining equality for two of these arrays appears to be difficult. We provide a probabilistic equality test in the third chapter, among other algorithms for persistent arrays. Persistent arrays themselves are briefly introduced in the first chapter of this thesis. There, we also show that zipping two persistent arrays (represented as trees) is generally not possible in time polynomial in its size in memory. The second chapter sets the stage for path problems on graphs. The first section shows how shortest paths in forests can be maintained dynamically. The resulting algorithms are somewhat slower than the best algorithms known in the literature, but easier to implement if persistent arrays are already provided by a programming library. We also introduce the semiring framework for path problems here. Chapter 5. shows some results in formal language theory which are useful for our conceptual framework. In chapter 6. we show how Rytter's formulation of Valiant's subcubic context-free parsing algorithm is connected to semiring parsing and path problems.

Item Type: Ph.D. Thesis
Erschienen: 2005
Creators: Glier, Oliver
Type of entry: Primary publication
Title: Persistent Arrays, Path Problems, and Context-free Languages
Language: English
Referees: Albert, Prof.Dr. Jürgen ; Brandt, Priv.Doz. Ulrike
Advisors: Walter, Prof.Dr. Hermann K.-G.
Date: 20 October 2005
Place of Publication: Darmstadt
Publisher: Technische Universität
Refereed: 21 April 2005
URL / URN: urn:nbn:de:tuda-tuprints-6185
Abstract:

The goal of this thesis is to provide a framework for several path problems for graphs. From the conceptual part, there are context-free grammars and semirings. Context-free grammars allow us to describe recursive generative processes, such as in grammars for natural languages or in models for the growth of cell complexes. They also capture the structure of certain dynamic programming schemes, as it is used in the CYK algorithm for context-free parsing and of some pseudo-polynomial algorithms for hard problems. The connection of context-free grammars with path problems in graphs allows us to model several language-restrictions for feasible paths and thus generalizes the classic shortest-path problem. On the other hand --- similarly to the algebraic shortest path problem --- context-free grammars can be equipped with semiring values. In chapter 4 of this thesis, we explore the relationship between semiring-valued context-free grammars and path problems. The connection is fruitful since it gives us a conceptual framework for many generalizations of the path problem. For instance it allows us to formulate tentative polynomial-time algorithms for transportation problems which cannot, or only with great difficulty, formulated as conventional shortest-path problems. As one can observe, language-restrictions on paths might cause the shortest feasible paths to grow exponentially. Persistent arrays, represented as balanced binary trees, allow us to deal with this problem and still maintain polynomial-time computability. The ability to represent certain exponentially long arrays in polynomial space gives rise to the question what kind of computations they apply to. Indeed, even determining equality for two of these arrays appears to be difficult. We provide a probabilistic equality test in the third chapter, among other algorithms for persistent arrays. Persistent arrays themselves are briefly introduced in the first chapter of this thesis. There, we also show that zipping two persistent arrays (represented as trees) is generally not possible in time polynomial in its size in memory. The second chapter sets the stage for path problems on graphs. The first section shows how shortest paths in forests can be maintained dynamically. The resulting algorithms are somewhat slower than the best algorithms known in the literature, but easier to implement if persistent arrays are already provided by a programming library. We also introduce the semiring framework for path problems here. Chapter 5. shows some results in formal language theory which are useful for our conceptual framework. In chapter 6. we show how Rytter's formulation of Valiant's subcubic context-free parsing algorithm is connected to semiring parsing and path problems.

Alternative Abstract:
Alternative abstract Language

Das Ziel dieser Arbeit ist es, einen Rahmen für die Modellierung sprachbeschränkter Wegeprobleme in Graphen zu schaffen. Von konzeptioneller Seite sind da kontextfreie Grammatiken und Semiringe zu nennen. Kontextfreie Grammatiken erlauben die Beschreibung rekursiver generativer Prozesse, wie sie beispielsweise in der Grammatik natürlicher Sprache auftauchen oder zur Beschreibung von Zellwachstum dienen können. Sie erfassen außerdem die Struktur einiger dynamischer Programmierschemata, so wie sie zum Beispiel im CYK Algorithmus für kontextfreies Parsing oder in manchen pseudopolynomiellen Algorithmen für schwere Probleme benutzt werden. Die Verbindung kontextfreier Grammatiken mit Wegeproblemen in Graphen erlauben die Modellierung zusätzlicher formalsprachlicher Einschränkungen der möglichen Wege. Auf der anderen Seite können kontextfreie Grammatiken analog zum algebraischen Wegeproblem mit Semiringwerten ausgestattet werden. Im vierten Kapitel dieser Arbeit werden diese Beziehungen zwischen semiringbewerteten kontextfreien Grammatiken und Wegeproblemen näher untersucht. Diese Verbindung ist fruchtbar und erlaubt einen konzeptionellen Rahmen für Verallgemeinerungen des Wegeproblems für Graphen, beispielsweise zur Formulierung von Polynomialzeitalgorithmen für Transportprobleme welche sonst gar nicht oder nur umständlich als konventionelle Wegeprobleme dargestellt werden können. Wie sich beobachten lässt, können formalsprachliche Einschränkungen dazu führen, dass die erlaubten Wege exponentiell lang werden. Persistente Arrays, welche als binäre Bäume dargestellt werden, erlauben mit diesem Problem umzugehen und erhalten die Eigenschaft der Polynomialzeitberechenbarkeit. Allerdings wirft die Darstellung bestimmter exponentiell langer Wege in polynomiellem Platz die Frage auf, welche Berechnungen überhaupt auf sie angewandt werden können. Tatsächlich scheint sogar die Bestimmung, ob zwei solche Arrays äquivalent sind, schwer durchführbar zu sein. Im dritten Kapitel zeigen wir neben anderen Algorithmen für persistente Arrays einen probabilistischen Äquivalenztest. Persistente Arrays als solche werden bereits im ersten Kapitel kurz vorgestellt. Dort zeigen wir auch, dass das "Zippen" zweier persistenter Arrays exponentieller Länge, welche als Bäume dargestellt werden, im Allgemeinen nicht in einer Zeit durchgeführt werden kann, welche polynomiell zu deren Größe im Speicher wächst. Das zweite Kapitel führt in Wegeprobleme in Graphen ein. Der erste Abschnitt befasst sich mit Wegeproblemen in dynamischen Wäldern. Auch wenn der resultierende Algorithmus nicht so schnell wie die bestbekannten Algorithmen ist, erlaubt er eine einfache Implementierung, falls persistente Arrays bereits in einer Programmierbibliothek vorhanden sind. Wir stellen außerdem Semiringe und das algebraische Wegeproblem in Verbindung mit persistenten Arrays vor. Kapitel 5. zeigt einige Ergebnisse aus der Theorie formaler Sprachen, welche sich während dieser Arbeit ergeben haben. In Kapitel 6. zeigen wir weiterhin, wie Rytters Formulierung von Valiants subkubischem Algorithmus für kontextfreies Parsing mit Semiringparsing und Wegeproblemen in Verbindung steht.

German
Uncontrolled Keywords: sprachbeschränkte Wegeprobleme, persistente Arrays
Alternative keywords:
Alternative keywordsLanguage
language-restricted path problems, persistent arraysEnglish
Classification DDC: 000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
Date Deposited: 17 Oct 2008 09:22
Last Modified: 05 Mar 2013 09:26
PPN:
Referees: Albert, Prof.Dr. Jürgen ; Brandt, Priv.Doz. Ulrike
Refereed / Verteidigung / mdl. Prüfung: 21 April 2005
Alternative keywords:
Alternative keywordsLanguage
language-restricted path problems, persistent arraysEnglish
Export:
Suche nach Titel in: TUfind oder in Google
Send an inquiry Send an inquiry

Options (only for editors)
Show editorial Details Show editorial Details