Fixed Point Theory

Fixed Point Theory

2009 | Zoltán Ésik
This chapter introduces the theory of fixed points, which are fundamental in various fields of computer science, particularly in the semantics of recursion. The author, Zoltán Ésik, provides an overview of the applications of fixed points in weighted automata and weighted languages. The chapter begins with a review of basic theorems guaranteeing the existence of least and greatest fixed points in ordered settings. It then delves into the properties of the least fixed point operation, including the Bekić identity, which allows for the solution of systems of fixed point equations through successive elimination. The chapter also introduces axiomatic frameworks of Conway and iteration theories, detailing their axiomatizations and completeness results. Finally, it discusses fixed points of linear and affine functions over semirings and semimodules, showing that these fixed points can be characterized by star and omega operations, with their equational properties reflected in these operations. The chapter concludes with a review of notation and definitions related to function composition, pairing, tupling, and projection functions.This chapter introduces the theory of fixed points, which are fundamental in various fields of computer science, particularly in the semantics of recursion. The author, Zoltán Ésik, provides an overview of the applications of fixed points in weighted automata and weighted languages. The chapter begins with a review of basic theorems guaranteeing the existence of least and greatest fixed points in ordered settings. It then delves into the properties of the least fixed point operation, including the Bekić identity, which allows for the solution of systems of fixed point equations through successive elimination. The chapter also introduces axiomatic frameworks of Conway and iteration theories, detailing their axiomatizations and completeness results. Finally, it discusses fixed points of linear and affine functions over semirings and semimodules, showing that these fixed points can be characterized by star and omega operations, with their equational properties reflected in these operations. The chapter concludes with a review of notation and definitions related to function composition, pairing, tupling, and projection functions.
Reach us at info@study.space