Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-19T02:59:12.393Z Has data issue: false hasContentIssue false
  • English
  • Français

Fixed Point Logics

Published online by Cambridge University Press:  15 January 2014

Anuj Dawar  and
Yuri Gurevich
Anuj Dawar
Affiliation:
Cambridge University Computer Laboratory, Cambridge CB2 3QG, UKE-mail: [email protected]
Yuri Gurevich
Affiliation:
Microsoft Research, One Microsoft Way, Redmond, WA 98052, USAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We consider fixed point logics, i.e., extensions of first order predicate logic with operators defining fixed points. A number of such operators, generalizing inductive definitions, have been studied in the context of finite model theory, including nondeterministic and alternating operators. We review results established in finite model theory, and also consider the expressive power of the resulting logics on infinite structures. In particular, we establish the relationship between inflationary and nondeterministic fixed point logics and second order logic, and we consider questions related to the determinacy of games associated with alternating fixed points.

Type
Research Article
Information
Bulletin of Symbolic Logic , Volume 8 , Issue 1 , March 2002 , pp. 65 - 88
Copyright
Copyright © Association for Symbolic Logic 2002

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] Abiteboul, S., Vardi, M. Y., and Vianu, V., Fixpoint logics, relational machines, and computational complexity, Proceedings of the 7 th IEEE symposium on structure in complexity theory, 1992.Google Scholar
[2] Abiteboul, S. and Vianu, V., Datalog extensions for database queries and updates, Journal of Computer and System Sciences, vol. 43 (1991), pp. 62–124.CrossRefGoogle Scholar
[3] Abiteboul, S., Computing with first-order logic, Journal of Computer and System Sciences, vol. 50 (1995), no. 2, pp. 309–335.CrossRefGoogle Scholar
[4] Aczel, P., An introduction to inductive definitions, Handbook of mathematical logic (Barwise, J., editor), North Holland, 1977, pp. 739–782.CrossRefGoogle Scholar
[5] Aho, A. V. and Ullman, J. D., Universality of data retrieval languages, 6th ACM symposium on principles of programming languages, 1979, pp. 110–117.Google Scholar
[6] Chandra, A. and Harel, D., Structure and complexity of relational queries, Journal of Computer and System Sciences, vol. 25 (1982), pp. 99–128.CrossRefGoogle Scholar
[7] Dawar, A., A restricted second order logic for finite structures, Information and Computation, vol. 143 (1998), pp. 154–174.CrossRefGoogle Scholar
[8] Ebbinghaus, H-D. and Flum, J., Finite model theory, Springer, 1995.Google Scholar
[9] Fagln, R., Generalized first-order spectra and polynomial-time recognizable sets, Complexity of computation, SIAM-AMS proceedings (Karp, R. M., editor), vol. 7, 1974, pp. 43–73.Google Scholar
[10] Gale, D. and Stewart, F. M., Infinite games with perfect information, Contributions to the theory ofgames, Annals of Mathematical Studies, vol. 28, Princeton University Press, 1953, pp. 245–266.Google Scholar
[11] Gurevich, Y., Toward logic tailored for computational complexity, Computation and proof theory, (Richter, M. et al., editors), Lecture Notes in Mathematics, Springer, 1984, pp. 175–216.CrossRefGoogle Scholar
[12] Gurevich, Y. and Shelah, S., Fixed-point extensions offirst-order logic, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 265–280.CrossRefGoogle Scholar
[13] Immerman, N., Upper and lower bounds for first-order expressibility, Journal of Computer and System Sciences, vol. 25 (1982), pp. 76–98.CrossRefGoogle Scholar
[14] Kleene, S. C., Arithmetical predicates and function quantifiers, Transactions of the American Mathematical Society, vol. 79 (1955), pp. 312–340.CrossRefGoogle Scholar
[15] Moschovakis, Y. N., Elementary induction on abstract structures, North Holland, 1974.Google Scholar
[16] Moschovakis, Y. N., On nonmonotone inductive definability, Fundamenta Mathematicae, vol. 82 (1974), pp. 39–83.CrossRefGoogle Scholar
[17] Moschovakis, Y. N., Descriptive set theory, North Holland, 1980.Google Scholar
[18] Vardi, M. Y., The complexity of relational query languages, Proceedings of the 14th ACM symposium on the theory of computing, 1982, pp. 137–146.Google Scholar