In this thesis, we investigate different theoretical questions concerning weighted automata models over tree-like input structures. First, we study exact and approximated determinisation and then, we turn to Kleene-like and Büchi-like characterisations. We consider multiple weighted automata models, including weighted tree automata over semirings (Chapters 3 and 4), weighted forest automata over M-monoids (Chapter 5), and rational weighted tree languages with storage (Chapter 6). For an explanation as to why the last class can be considered as a weighted automaton model, we refer to page 188 of the thesis. We will now summarise the main contributions of the thesis.
In Chapter 3, we focus on the determinisation of weighted tree automata and present our determinisation framework, called M-sequentialisation, which can model different notions of determinisation from the existing literature. Then, we provide a positive M-sequentialisation result for the case of additively idempotent semirings or finitely M-ambiguous weighted tree automata. Another important contribution of Chapter 3 is Theorem 77, where we provide a blueprint theorem that can be used to find determini- sation results for more classes of semirings and weighted tree automata easily. In fact, instead of repeating an entire determinisation construction, Theorem 77 allows us to prove a determinisation result by finding certain finite equivalence relations. This is a very potent tool for future research in the area of determinisation.
In Chapter 4, we move from exact determinisation towards approximate determini- sation. We lift the formalisms and the main results from one approach from the literature from the word case to the tree case. This successfully results in an approximated determinisation construction for weighted tree automata over the tropical semiring. We provide a formal mathematical description of the approximated determinisation construction, rather than an algorithmic description as found in the related approach from the literature.
In Chapter 5, we turn away from determinisation and instead consider Kleene-like and Büchi-like characterisations of weighted recognisability. We introduce weighted forest automata over M-monoids, which are a generalisation of weighted tree automata over M-monoids and weighted forest automata over semirings. Then, we prove that our recognisable weighted forest languages can be decomposed into a finite product of recognisable weighted tree languages. We also prove that the initial algebra semantic and the run semantic for weighted forest automata are equivalent under certain conditions. Lastly, we define rational forest expressions and forest M-expressions and and prove that the classes of languages generated by these formalisms coincide with recognisable weighted forest languages under certain conditions.
In Chapter 6, we consider rational weighted tree languages with storage, where the storage is introduced by composing rational weighted tree languages without storage with a storage map. It has been proven in the literature that rational weighted tree languages with storage are closed under the rational operations. In Chapter 6, we provide alternative proofs of these closure properties. In fact, we prove that our way of introducing storage to rational weighted tree languages preserves the closure properties from rational weighted tree languages without storage.:1 Introduction
2 Preliminaries
2.1 Languages
2.2 WeightedLanguages
2.3 Weighted Tree Automata
3 A Unifying Framework for the Determinisation of Weighted Tree Automata
3.1 Introduction
3.2 Preliminaries
3.3 Factorisation in Monoids
3.3.1 Ordering Multisets over Monoids
3.3.2 Cayley Graph and Cayley Distance
3.3.3 Divisors and Rests
3.3.4 Factorisation Properties
3.4 Weighted Tree Automata over M_fin(M) and the Twinning Property
3.4.1 Weighted Tree Automata over M_fin(M)
3.4.2 The Twinning Property
3.5 Sequentialisation of Weighted Tree Automata over M_fin(M)
3.5.1 The Sequentialisation Construction
3.5.2 The Finitely R-Ambiguous Case
3.6 Relating WTA over M_fin(M) and WTA over S
3.7 M-Sequentialisation of Weighted Tree Automata
3.7.1 Accumulation of D_B
3.7.2 M-Sequentialisation Results
3.8 Comparison of our Results to the Literature
3.8.1 Determinisation of Unweighted Tree Automata
3.8.2 The Free Monoid Case
3.8.3 The Group Case
3.8.4 The Extremal Case
3.9 Conclusion
4 Approximated Determinisation of Weighted Tree Automata 125
4.1 Introduction
4.2 Preliminaries
4.3 Approximated Determinisation
4.3.1 The Approximated Determinisation Construction
4.3.2 Correctness of the Construction
4.4 The Approximated Twinning Property
4.4.1 Implications for Approximated Determinisability
4.4.2 Decidability of the Twinning Property
4.5 Conclusion
5 Kleene and Büchi Theorems for Weighted Forest Languages over M-Monoids
5.1 Introduction
5.2 Preliminaries
5.3 WeightedForestAutomata
5.3.1 Forests
5.3.2 WeightedForestAutomata
5.3.3 Rectangularity
5.3.4 I-recognisable is R-recognisable
5.4 Kleene’s Theorem
5.4.1 Kleene’s Theorem for Trees
5.4.2 Kleene’s Theorem for Forests
5.4.3 An Inductive Approach
5.5 Büchi’s Theorem
5.5.1 Büchi’s Theorem for Trees
5.5.2 Büchi’s Theorem for Forests
5.6 Conclusion
6 Rational Weighted Tree Languages with Storage
6.1 Introduction
6.2 Preliminaries
6.3 Rational Weighted Tree Languages with Storage
6.4 The Kleene-Goldstine Theorem
6.5 Closure of Rat(S¢,Σ,S) under Rational Operations
6.5.1 Top-Concatenation, Scalar Multiplication, and Sum
6.5.2 α-Concatenation
6.5.3 α-Kleene Star
6.6 Conclusion
7 Outlook
References
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:82195 |
| Date | 15 November 2022 |
| Creators | Dörband, Frederic |
| Contributors | Vogler, Heiko, Daviaud, Laure, Technische Universität Dresden |
| Source Sets | Hochschulschriftenserver (HSSS) der SLUB Dresden |
| Language | English |
| Detected Language | English |
| Type | info:eu-repo/semantics/publishedVersion, doc-type:doctoralThesis, info:eu-repo/semantics/doctoralThesis, doc-type:Text |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | info:eu-repo/grantAgreement/Deutsche Forschungsgemeinschaft/RTG 1763/189782547//Quantitative Logics and Automata/QuantLA |
Page generated in 0.003 seconds