Weighted Automata, Formal Power Series and Weighted Logic
53,49 €
Sofort verfügbar, Lieferzeit: Sofort lieferbar
Weighted Automata, Formal Power Series and Weighted Logic, Spektrum Akademischer Verlag bei Elsevier
Von Laura Wirth, im heise shop in digitaler Fassung erhältlich
Produktinformationen "Weighted Automata, Formal Power Series and Weighted Logic"
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.
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.
Artikel-Details
- Anbieter:
- Spektrum Akademischer Verlag bei Elsevier
- Autor:
- Laura Wirth
- Artikelnummer:
- 9783658393236
- Veröffentlicht:
- 13.10.22