 Preface  5 

 List of Contributors  9 

 Contents  11 

 Part I Foundations  18 

 Chapter 1: Semirings and Formal Power Series  19 
 Introduction  19 
 Monoids and Semirings  21 
 Formal Power Series  28 
 Matrices  33 
 CycleFree Linear Equations  38 
 References  42 
 Chapter 2: Fixed Point Theory  45 
 Introduction  45 
 Some Notation  46 
 Least Fixed Points  46 
 Conway Theories  54 
 Iteration Theories  57 
 Unique Fixed Points  60 
 Fixed Points of Linear Functions  62 
 Inductive *Semirings  67 
 Complete Semirings  68 
 Iterative Semirings  69 
 Fixed Points of Affine Functions  70 
 Complete SemiringSemimodule Pairs  75 
 Biinductive SemiringSemimodule Pairs  77 
 References  78 
 Part II Concepts of Weighted Recognizability  82 

 Chapter 3: Finite Automata  83 
 Introduction  83 
 Finite Automata over Semirings  84 
 Finite Automata over Arbitrary Power Series Semirings  86 
 Finite Automata over Conway Semirings  89 
 Finite Linear Systems  95 
 Finite Automata over Quemirings  97 
 SemiringSemimodule Pairs and Quemirings  99 
 Finite Automata over Quemirings and a Kleene Theorem  105 
 Finite Linear Systems over Quemirings  113 
 References  117 
 Chapter 4: Rational and Recognisable Power Series  119 
 Introduction  120 
 Rational Series and Weighted Rational Expressions  121 
 Series over a Graded Monoid  121 
 Graded Monoid  123 
 Topology on S  123 
 Topology on S  123 

 Topology on S  123 

 Topology on S  123 

 124  123 

 Distance on S  123 
 Distance on S  123 

 Distance on S  123 

 Distance on S  123 

 125  123 

 Summable Families  126 
 Rational Series  128 
 Star of a Series  128 
 Star of a Proper Series  129 
 Strong Semirings and Star of an Arbitrary Series  130 
 The Family of Rational Series  132 
 SRational Operations  132 
 Characteristic Series and Unambiguous Rational Sets  133 
 Rational SExpressions  134 
 Weighted Automata  136 
 The Behaviour of a Weighted Automaton  136 
 The Fundamental Theorem of Automata  140 
 Proper Automata  141 
 Standard Automata  142 
 Statement and Proof of the Fundamental Theorem  144 
 Conjugacy and Covering of Automata  146 
 From Conjugacy to Covering  146 
 Minimal SQuotient  148 
 From Covering to Conjugacy  150 
 Recognisable Series and Representations  152 
 The Family of Recognisable Series  152 
 Other Products on Recognisable Series  155 
 Tensor Product of SRepresentations  155 
 Hadamard Product  156 
 Shuffle Product
