Chapter 2: Fixed Point Theory
Zoltán Ésik
University of Szeged, Szeged, Hungary
Rovira i Virgili University, Tarragona, Spain
This chapter introduces the theory of fixed points, focusing on its applications to weighted automata and languages. It begins with an overview of fixed points in ordered settings and reviews theorems ensuring the existence of least (or greatest) fixed points. It then establishes several equational properties of the least fixed point operation, including the Bekić identity, which allows solving systems of fixed point equations through successive elimination. The chapter introduces axiomatic frameworks for Conway and iteration theories, providing axiomatizations and completeness results showing that iteration theories capture the equational properties of the fixed point operation in a large class of models. The last two sections treat fixed points of linear and affine functions over semirings and semimodules. The main results show that for such functions, the fixed point operation can be characterized by a star operation, possibly in conjunction with an omega operation. The equational properties of the fixed point operation are reflected by corresponding properties of the star and omega operations.
Some notation is provided, including function composition, identity functions, target pairings, and tuplings. The chapter also defines base functions, product functions, and projection functions.Chapter 2: Fixed Point Theory
Zoltán Ésik
University of Szeged, Szeged, Hungary
Rovira i Virgili University, Tarragona, Spain
This chapter introduces the theory of fixed points, focusing on its applications to weighted automata and languages. It begins with an overview of fixed points in ordered settings and reviews theorems ensuring the existence of least (or greatest) fixed points. It then establishes several equational properties of the least fixed point operation, including the Bekić identity, which allows solving systems of fixed point equations through successive elimination. The chapter introduces axiomatic frameworks for Conway and iteration theories, providing axiomatizations and completeness results showing that iteration theories capture the equational properties of the fixed point operation in a large class of models. The last two sections treat fixed points of linear and affine functions over semirings and semimodules. The main results show that for such functions, the fixed point operation can be characterized by a star operation, possibly in conjunction with an omega operation. The equational properties of the fixed point operation are reflected by corresponding properties of the star and omega operations.
Some notation is provided, including function composition, identity functions, target pairings, and tuplings. The chapter also defines base functions, product functions, and projection functions.