Theoretical computer science is inconceivable without the concept of finite automata. These devices and their upgraded versions, weighted automata, are widely
used to implement (quantitative) evaluations of inputs in image compression, probabilistic systems or natural language processing. In particular, the handling of natural language requires more sophisticated input structures such as trees. Together with the quantitative dimension, this leads to the model of weighted tree automata and the regular weighted tree languages they recognize. From a computational point of view, regular languages have many advantages: They allow compact representations, many of their fundamental properties are decidable and they are closed under several natural operations. One exception to this, however, are tree homomorphisms. It is long known that these deterministic transformations do not necessarily preserve regularity, but for decades, it was an open problem whether regularity of the homomorphic image is decidable. In 2010, this so-called HOM-problem was solved by Godoy, Giménez, Ramos and Àlvarez. More precisely, given a tree automaton and a tree homomorphism, it can be decided in exponential time whether the homomorphic image of the recognized language is again regular. In this thesis, we approach different weighted versions of this problem, where the input automaton is a weighted device over a certain semiring. We prove the decidability of this problem, both for restricted and unrestricted input, for different classes of weight domains. For this, we introduce a novel extension of weighted tree automata with explicit constraints, which we use to represent and study the homomorphic images. Moreover,
we demonstrate an additional application of this automata model as we use it to describe the ranges of bottom-up and top-down weighted tree transformations.:1 Introduction
1.1 About this Work
1.2 Publications
2 Background
2.1 Preliminaries
2.1.1 Trees
2.1.2 Semirings
2.1.3 Tree Homomorphisms
2.2 Tree Automata and the HOM-Problem
3 Weighted Tree Automata with Constraints
3.1 The Model
3.2 Closure Properties
3.3 Hom-Regular Languages and the Subclass WTAh
3.4 Recognizing Homomorphic Images
3.5 A Pumping Lemma for WTAh
3.6 Conclusion
4 Unambiguity and the Weighted HOM-Problem
4.1 Translating TAh into TAhom
4.2 Deciding Regularity for Unambiguous WTAh
4.3 Unambiguity and the Instances of the HOM-Problem
4.4 Conclusion and Perspective
5 The N-Weighted HOM-Problem
5.1 The Large Duplication Property
5.2 Deciding the N-Weighted HOM-Problem
5.3 Conclusion
6 The HOM-Problem for Fields
6.1 Relating WTAh to WTA
6.2 A Pumping Lemma for WTAh over Fields
6.3 The Tetris-Free Weighted HOM-Problem
6.4 Conclusion
7 Weighted Tree Transducers in Light of Hom-Regular Tree Languages
7.1 Preliminaries: Transformations
7.2 Weighted Bottom-up Tree Transducers
7.2.1 Separating Weighted TOP and BOT – Part I
7.2.2 The Range of a Weighted Bottom-up Tree Transducer
7.3 Weighted Top-down Tree Transducers
7.3.1 Separating Weighted TOP and BOT – Part II
7.3.2 The Range of a Weighted Top-down Tree Transducer
7.4 Conclusion
8 Conclusion
8.1 Summary
8.2 FutureWork
Bibliography
Lebenslauf
Selbständigkeitserklärung
| Identifer | oai:union.ndltd.org:DRESDEN/oai:qucosa:de:qucosa:92912 |
| Date | 05 August 2024 |
| Creators | Nász, Andreea-Teodora |
| Contributors | Universität Leipzig |
| 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 |
Page generated in 0.002 seconds