Abstract
Fixed points and fixed point computations occur in just about every field of Computer Science. It has been noticed that several fundamental theorems are consequences of just a few equational properties of fixed point operations. This chapter gives an introduction to that part of the theory of fixed points that has applications to weighted automata and languages.
The author was partially supported by grant no. MTM2007-63422 from the Ministry of Education and Science of Spain.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Arnold and D. Niwinski. Rudiments of μ -Calculus. Elsevier, Amsterdam, 2001.
S. Banach. Sur les operations dans les ensembles abstraits et leur applications aux équations intégrales. Fundamenta Mathematicae, 22:133–181, 1922.
M. Barr and C. Wells. Category Theory for Computing Science. Prentice Hall International, Englewood Cliffs, 1990.
H. Bekić. Definable operations in general algebras, and the theory of automata and flowcharts. Technical Report, IBM Laboratory, Vienna, 1969.
L. Bernátsky and Z. Ésik. Semantics of flowchart programs and the free Conway theories. Theoretical Informatics and Applications, RAIRO, 32:35–78, 1998.
S.L. Bloom, C.C. Elgot, and J.B. Wright. Solutions of the iteration equation and extension of the scalar iteration operation. SIAM Journal on Computing, 9:26–45, 1980.
S.L. Bloom, C.C. Elgot, and J.B. Wright. Vector iteration of pointed iterative theories. SIAM Journal on Computing, 9:525–540, 1980.
S.L. Bloom and Z. Ésik. Axiomatizing schemes and their behaviors. Journal of Computer and System Sciences, 31:375–393, 1985.
S.L. Bloom and Z. Ésik. Iteration Theories: The Equational Logic of Iterative Processes. Monographs in Theoretical Computer Science. An EATCS Series, Springer, Berlin, 1993.
S.L. Bloom and Z. Ésik. Two axiomatizations of a star semiring quasi-variety. Bulletin of the European Association for Theoretical Computer Science, 59:150–152, 1996.
S.L. Bloom and Z. Ésik. The equational logic of fixed points. Theoretical Computer Science, 179:1–60, 1997.
S.L. Bloom and Z. Ésik. Axiomatizing rational power series. Information and Computation, 207:793–811, 2009.
S.L. Bloom S. Ginali, and J. Rutledge. Scalar and vector iteration. Journal of Computer and System Sciences, 14:251–256, 1977.
M. Boffa. Une remarque sur les systèmes complets d’identités rationnelles. (A remark on complete systems of rational identities). Theoretical Informatics and Applications, RAIRO, 24:419–423, 1990 (in French).
M. Boffa. Une condition impliquant toutes les identités rationnelles (A condition implying all rational identities). Theoretical Informatics and Applications, RAIRO, 29:515–518, 1995 (in French).
P.M. Cohn. Universal Algebra. Harper & Row, New York, 1965.
J.C. Conway. Regular Algebra and Finite Machines. Chapman & Hall, London, 1971.
B. Courcelle, G. Kahn, and J. Vuillemin. Algorithmes d’équivalence et de réduction á des expressions minimales dans une classe d’équations récursives simples. In Proc. ICALP 74, Saarbrücken, volume 14 of Lecture Notes in Computer Science, pages 200–213. Springer, Berlin, 1974.
B.A. Davey and H.A. Priestley. Introduction to Lattices and Order, 2nd edition, Cambridge University Press, Cambridge, 2002.
J.W. De Bakker and D. Scott. A theory of programs. Technical Report, IBM Vienna, 1969.
M. Droste and W. Kuich. Semirings and formal power series. In W. Kuich, M. Droste, and H. Vogler, editors. Handbook of Weighted Automata. Chapter 1. Springer, Berlin, 2009.
C.C. Elgot. Monadic computation and iterative algebraic theories. In J.C. Shepherdson, editor, Logic Colloquium 1973, volume 80 of Studies in Logic, pages 175–230. North-Holland, Amsterdam, 1975.
C.C. Elgot. Matricial theories. Journal of Algebra, 42:391–421, 1976.
Z. Ésik. Identities in iterative algebraic theories. Computational Linguistics and Computer Languages, 14:183–207, 1980.
Z. Ésik. A note on the axiomatization of iteration theories. Acta Cybernetica, 9:375–384, 1990.
Z. Ésik. Completeness of Park induction. Theoretical Computer Science, 177:217–283, 1997.
Z. Ésik. Group axioms for iteration. Information and Computation, 148:131–180, 1999.
Z. Ésik. Iteration theories of boolean functions. In Math. Found. of Computer Science, 2000, volume 1893 of Lecture Notes in Computer Science, pages 343–352. Springer, Berlin, 2000.
Z. Ésik. Iteration semirings. In Proc. DLT 08, volume 5257 of Lecture Notes in Computer Science, pages 1–20. Springer, Berlin, 2008.
Z. Ésik and W. Kuich. Rationally additive semirings. Journal of Universal Computer Science, 2(8):173–183, 2002.
Z. Ésik and W. Kuich. Inductive *-semirings. Theoretical Computer Science, 324:3–33, 2004.
Z. Ésik and W. Kuich. On iteration semiring–semimodule pairs. Semigroup Forum, 75:129–159, 2007.
Z. Ésik and W. Kuich. Finite automata. In W. Kuich, M. Droste, and H. Vogler, editors, Handbook of Weighted Automata. Chapter 3. Springer, Berlin, 2009.
Z. Ésik and A. Labella. Equational properties of iteration in algebraically complete categories. Theoretical Computer Science, 195:61–89, 1998.
J.S. Golan. The Theory of Semirings with Applications in Computer Science. Longman, Harlow, 1993.
M. Hasegawa. Recursion from cyclic sharing: Traced monoidal categories and models of cyclic lambda calculi. In Typed Lambda Calculi and Applications, Nancy, 1997, volume 1210 of Lecture Notes in Computer Science, pages 196–213. Springer, Berlin, 1997.
U. Hebisch. The Kleene theorem in countably complete semirings. Bayreuther Mathematische Schriften, 31:55–66, 1990.
A. Joyal, R. Street, and D. Verity. Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society, 119:447–468, 1996.
D. Kozen. On Kleene algebras and closed semirings. In Proc. MFCS’90, volume 452 of Lecture Notes in Computer Science, pages 26–47. Springer, Berlin, 1990.
D. Kozen. A completeness theorem for Kleene algebras and the algebra of regular events. Information and Computation, 110:366–390, 1994.
D. Krob. Complete systems of B-rational identities. Theoretical Computer Science, 89:207–343, 1991.
F.W. Lawvere. Functorial semantics of algebraic theories. Proceedings of the National Academy of Sciences of the United States of America, 50:869–873, 1963.
G. Markowsky. Chain-complete posets and directed sets with applications. Algebra Universalis, 6:53–68, 1976.
D. Niwinski. Equational μ-calculus. In Computation Theory, Zaborów, 1984, volume 208 of Lecture Notes in Computer Science, pages 169–176. Springer, Berlin, 1985.
D. Niwinski. On fixed-point clones. In Proc. ICALP’86, volume 226 of Lecture Notes in Computer Science, pages 464–473. Springer, Berlin, 1986.
D. Perrin and J.-E. Pin. Infinite Words, volume 141 of Pure and Applied Mathematics. Elsevier, Amsterdam, 2004.
G.D. Plotkin. Domains. Lecture Notes, Department of Computer Science, University of Edinburgh, 1983.
A. Simpson and G. Plotkin. Complete axioms for categorical fixed-point operators. In 15th Annual IEEE Symposium on Logic in Computer Science, Santa Barbara, CA, 2000, pages 30–41. IEEE Computer Society, Los Alamitos, 2000.
Gh. Stefanescu. Network Algebra. Springer, Berlin, 2000.
A. Tarski. A lattice theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, 5:285–309, 1955.
J.B. Wright, J.W. Thatcher, J. Goguen, and E.G. Wagner. Rational algebraic theories and fixed-point solutions. In Proceedings 17th IEEE Symposium on Foundations of Computing, Houston, Texas, pages 147–158, 1976.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Ésik, Z. (2009). Fixed Point Theory. In: Droste, M., Kuich, W., Vogler, H. (eds) Handbook of Weighted Automata. Monographs in Theoretical Computer Science. An EATCS Series. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01492-5_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-01492-5_2
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01491-8
Online ISBN: 978-3-642-01492-5
eBook Packages: Computer ScienceComputer Science (R0)