Hostname: page-component-78c5997874-mlc7c Total loading time: 0 Render date: 2024-11-05T16:47:51.507Z Has data issue: false hasContentIssue false
  • English
  • Français

A Note on the Completeness of Kozen's Axiomatisation of the Propositional μ-Calculus

Published online by Cambridge University Press:  15 January 2014

Igor Walukiewicz
Igor Walukiewicz*
Affiliation:
Basic Research in Computer Science, Centre of the Danish National Research Foundation (BRICS), Department of Computer Science, University of Aarhus, NY Munkegade, DK-8000 Aarhus C, Denmark E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The prepositional μ-calculus is an extension of the modal system K with a least fixpoint operator. Kozen posed a question about completeness of the axiomatisation of the logic which is a small extension of the axiomatisation of the modal system K. It is shown that this axiomatisation is complete.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 2 , Issue 3 , September 1996 , pp. 349 - 366
Copyright
Copyright © Association for Symbolic Logic 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Bull, R. and Segerberg, K., Basic modal logic, Handbook of philosophical logic (Gabbay, D. and Guenther, F., editors), vol. 2, D. Reidel Publishing Company, 1984, pp. 1–89.Google Scholar
[2] Emerson, E. A., Temporal and modal logic, Handbook of theoretical computer science (Leeuven, J., editor), vol. B, Elsevier, 1990, pp. 995–1072.Google Scholar
[3] Emerson, E. A. and Jutla, C. S., The complexity of tree automata and logics ofprograms, 29th FOCS, 1988.Google Scholar
[4] Fitting, M., Proof methods for modal and intuitionistic logics, D. Reidel Publishing Company, 1983.CrossRefGoogle Scholar
[5] Harel, D., Dynamic logic, Handbook of philosophical logic, vol. II, D. Reidel Publishing Company, 1984, pp. 497–604.CrossRefGoogle Scholar
[6] Janin, D. and Waluoewicz, I., Automata for the μ-calculus and related results, MFCS '95, Lecture Notes in Computer Science, vol. 969, 1995, pp. 552–562.Google Scholar
[7] Kaivola, R., Axiomatising linear time μ-calculus, CONCUR '95, Lecture Notes in Computer Science, vol. 962, 1995, pp. 423–437.CrossRefGoogle Scholar
[8] Kozen, D., Results on thepropositional μ-calculus, Theoretical Computer Science, vol. 27 (1983), pp. 333–354.CrossRefGoogle Scholar
[9] Kozen, D., A finite model theorem for the propositional μ-calculus, Studia Logica, vol. 47 (1988), no. 3, pp. 234–241.CrossRefGoogle Scholar
[10] Kozen, D. and Tiurïn, J., Logics of programs, Handbook of theoretical computer science (Leeuven, J., editor), vol. B, Elsevier, 1990, pp. 789–840.Google Scholar
[11] Mostowskl, A. W., Regular expressions for infinite trees and a standard form of automata, Fifth symposium on computation theory (Skowron, A., editor), Lecture Notes in Computer Science, vol. 208, 1984, pp. 157–168.CrossRefGoogle Scholar
[12] Niwińskl, D., Fixed points vs. infinite generation, LICS '88, 1988, pp. 402–409.Google Scholar
[13] Niwiński, D. and Waluoewicz, I., Games for μ-calculus, Technical Report TR 94-03(192), Institute of Informatics, Warsaw Univeristy, 02 1994, to appear in Theoretical Computer Science ; available from: http://www.daimi.aau.dk/~igw/home.html.Google Scholar
[14] Rabin., M., Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[15] Slefkes, D., Büchi's monadic second order successor arithmetic, Lecture notes in mathematics, vol. 120, Springer-Verlag, 1970.Google Scholar
[16] Stirling, C. S., Modal and temporal logics, Handbook of logic in comuter science (Abramsky, S., Gabbay, D., and Maibaum, T., editors), Oxford University Press, 1991, pp. 477–563.Google Scholar
[17] Streett, R. S. and Emerson, E. A., An automata theoretic procedure for the propositional μ-calculus, Information and Computation, vol. 81 (1989), pp. 249–264.CrossRefGoogle Scholar
[18] Walukiewicz, I., On completeness of the μ-calculus, LICS '93, 1993, pp. 136–146.Google Scholar