Login
 
Hauptdaten
Herausgeber: Manfred Droste, Werner Kuich, Heiko Vogler
Titel: Handbook of Weighted Automata
Verlag: Springer-Verlag
ISBN/ISSN: 9783642014925
Auflage: 1
Preis : CHF 209.40
Erscheinungsdatum:
Inhalt
Kategorie: Informatik, EDV Buch
Sprache: English
Technische Daten
Seiten: 608
Kopierschutz: DRM
Geräte: PC/MAC/eReader/Tablet
Formate: PDF
Inhaltsangabe
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.
Inhaltsverzeichnis
Preface5
List of Contributors9
Contents11
Part I Foundations18
Chapter 1: Semirings and Formal Power Series19
Introduction19
Monoids and Semirings21
Formal Power Series28
Matrices33
Cycle-Free Linear Equations38
References42
Chapter 2: Fixed Point Theory45
Introduction45
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
References78
Part II Concepts of Weighted Recognizability82
Chapter 3: Finite Automata83
Introduction83
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
References117
Chapter 4: Rational and Recognisable Power Series119
Introduction120
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
124123
Distance on S123
Distance on S123
Distance on S123
Distance on S123
125123
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