Weighted Automata, Formal Power Series and Weighted Logic
Seiten
2022
|
1st ed. 2022
Springer Fachmedien Wiesbaden GmbH (Verlag)
978-3-658-39322-9 (ISBN)
Springer Fachmedien Wiesbaden GmbH (Verlag)
978-3-658-39322-9 (ISBN)
The main objective of this work is to represent the behaviors of weighted automata by expressively equivalent formalisms: rational operations on formal power series, linear representations by means of matrices, and weighted monadic second-order logic.
First, we exhibit the classical results of Kleene, Büchi, Elgot and Trakhtenbrot, which concentrate on the expressive power of finite automata. We further derive a generalization of the Büchi-Elgot-Trakhtenbrot Theorem addressing formulas, whereas the original statement concerns only sentences. Then we use the language-theoretic methods as starting point for our investigations regarding power series. We establish Schützenberger's extension of Kleene's Theorem, referred to as Kleene-Schützenberger Theorem. Moreover, we introduce a weighted version of monadic second-order logic, which is due to Droste and Gastin. By means of this weighted logic, we derive an extension of the Büchi-Elgot-Trakhtenbrot Theorem. Thus, we point out relations among the different specification approaches for formal power series. Further, we relate the notions and results concerning power series to their counterparts in Language Theory.
Overall, our investigations shed light on the interplay between languages, formal power series, automata and monadic second-order logic.
First, we exhibit the classical results of Kleene, Büchi, Elgot and Trakhtenbrot, which concentrate on the expressive power of finite automata. We further derive a generalization of the Büchi-Elgot-Trakhtenbrot Theorem addressing formulas, whereas the original statement concerns only sentences. Then we use the language-theoretic methods as starting point for our investigations regarding power series. We establish Schützenberger's extension of Kleene's Theorem, referred to as Kleene-Schützenberger Theorem. Moreover, we introduce a weighted version of monadic second-order logic, which is due to Droste and Gastin. By means of this weighted logic, we derive an extension of the Büchi-Elgot-Trakhtenbrot Theorem. Thus, we point out relations among the different specification approaches for formal power series. Further, we relate the notions and results concerning power series to their counterparts in Language Theory.
Overall, our investigations shed light on the interplay between languages, formal power series, automata and monadic second-order logic.
Laura Wirth completed her Master's thesis in Mathematics at the University of Konstanz in 2022. It was supervised Prof. Salma Kuhlmann as well as Prof. Sven Kosub and received the highest grade with honors.
Introduction.- Languages, Automata and Monadic Second-Order Logic.- Weighted Automata.- The Kleene-Schützenberger Theorem.- Weighted Monadic Second-Order Logic and Weighted Automata.- Summary and Further Research.
| Erscheinungsdatum | 15.10.2022 |
|---|---|
| Reihe/Serie | BestMasters |
| Zusatzinfo | XI, 190 p. 63 illus. Textbook for German language market. |
| Verlagsort | Wiesbaden |
| Sprache | englisch |
| Maße | 148 x 210 mm |
| Gewicht | 273 g |
| Themenwelt | Mathematik / Informatik ► Mathematik ► Analysis |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Schlagworte | Büchi, Elgot, Trakhtenbrot • Droste and Gastin • Formal power series • monadic second-order logic • mso • Schützenberger • Weighted Automata • weighted logic |
| ISBN-10 | 3-658-39322-X / 365839322X |
| ISBN-13 | 978-3-658-39322-9 / 9783658393229 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
Mehr entdecken
aus dem Bereich
aus dem Bereich
Band 5: Hydraulik, Stromfadentheorie, Wellentheorie, Gasdynamik
Buch | Softcover (2024)
De Gruyter Oldenbourg (Verlag)
CHF 83,90
