Fixed Point Theory

Fixed Point Theory

2009 | Zoltán Ésik
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.
Reach us at info@futurestudyspace.com
[slides] Fixed Point Theory | StudySpace