Main Data
Editor: Manfred Droste, Werner Kuich, Heiko Vogler
Title: Handbook of Weighted Automata
Publisher: Springer-Verlag
ISBN/ISSN: 9783642014925
Edition: 1
Price: CHF 202,30
Publication date: 01/01/2009
Category: Informatik, EDV Buch
Language: English
Technical Data
Pages: 608
Kopierschutz: DRM
Geräte: PC/MAC/eReader/Tablet
Formate: PDF
Table of contents
The purpose of this Handbook is to highlight both theory and applications of weighted automata. Weighted finite automata are classical nondeterministic finite automata in which the transitions carry weights. These weights may model, e. g. , the cost involved when executing a transition, the amount of resources or time needed for this,or the probability or reliability of its successful execution. The behavior of weighted finite automata can then be considered as the function (suitably defined) associating with each word the weight of its execution. Clearly, weights can also be added to classical automata with infinite state sets like pushdown automata; this extension constitutes the general concept of weighted automata. To illustrate the diversity of weighted automata, let us consider the following scenarios. Assume that a quantitative system is modeled by a classical automaton in which the transitions carry as weights the amount of resources needed for their execution. Then the amount of resources needed for a path in this weighted automaton is obtained simply as the sum of the weights of its transitions. Given a word, we might be interested in the minimal amount of resources needed for its execution, i. e. , for the successful paths realizing the given word. In this example, we could also replace the 'resources' by 'profit' and then be interested in the maximal profit realized, correspondingly, by a given word.
Table of contents
List of Contributors9
Part I Foundations18
Chapter 1: Semirings and Formal Power Series19
Monoids and Semirings21
Formal Power Series28
Cycle-Free Linear Equations38
Chapter 2: Fixed Point Theory45
Some Notation46
Least Fixed Points46
Conway Theories54
Iteration Theories57
Unique Fixed Points60
Fixed Points of Linear Functions62
Inductive *-Semirings67
Complete Semirings68
Iterative Semirings69
Fixed Points of Affine Functions70
Complete Semiring-Semimodule Pairs75
Bi-inductive Semiring-Semimodule Pairs77
Part II Concepts of Weighted Recognizability82
Chapter 3: Finite Automata83
Finite Automata over Semirings84
Finite Automata over Arbitrary Power Series Semirings86
Finite Automata over Conway Semirings89
Finite Linear Systems95
Finite Automata over Quemirings97
Semiring-Semimodule Pairs and Quemirings99
Finite Automata over Quemirings and a Kleene Theorem105
Finite Linear Systems over Quemirings113
Chapter 4: Rational and Recognisable Power Series119
Rational Series and Weighted Rational Expressions121
Series over a Graded Monoid121
Graded Monoid123
Topology on S123
Topology on S123
Topology on S123
Topology on S123
Distance on S123
Distance on S123
Distance on S123
Distance on S123
Summable Families126
Rational Series128
Star of a Series128
Star of a Proper Series129
Strong Semirings and Star of an Arbitrary Series130
The Family of Rational Series132
S-Rational Operations132
Characteristic Series and Unambiguous Rational Sets133
Rational S-Expressions134
Weighted Automata136
The Behaviour of a Weighted Automaton136
The Fundamental Theorem of Automata140
Proper Automata141
Standard Automata142
Statement and Proof of the Fundamental Theorem144
Conjugacy and Covering of Automata146
From Conjugacy to Covering146
Minimal S-Quotient148
From Covering to Conjugacy150
Recognisable Series and Representations152
The Family of Recognisable Series152
Other Products on Recognisable Series155
Tensor Product of S-Representations155
Hadamard Product156
Shuffle Product