Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-20T04:36:56.398Z Has data issue: false hasContentIssue false
  • English
  • Français

On fixed-point logic with counting

Published online by Cambridge University Press:  12 March 2014

Jörg Flum  and
Martin Grohe
Jörg Flum
Affiliation:
Institut für Mathematische Logik, Eckerstr. 1, 79104 Freiburg, Germany, E-mail: [email protected]
Martin Grohe
Affiliation:
Institut für Mathematische Logik, Eckerstr. 1, 79104 Freiburg, Germany, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Extract

One of the fundamental results of descriptive complexity theory, due to Immerman [13] and Vardi [18], says that a class of ordered finite structures is definable in fixed-point logic if, and only if, it is computable in polynomial time. Much effort has been spent on the problem of capturing polynomial time, that is, describing all polynomial time computable classes of not necessarily ordered finite structures by a logic in a similar way.

The most obvious shortcoming of fixed-point logic itself on unordered structures is that it cannot count. Immerman [14] responded to this by adding counting constructs to fixed-point logic. Although it has been proved by Cai, Fürer, and Immerman [1] that the resulting fixed-point logic with counting, denoted by IFP+C, still does not capture all of polynomial time, it does capture polynomial time on several important classes of structures (on trees, planar graphs, structures of bounded tree-width [15, 9, 10]).

The main motivation for such capturing results is that they may give a better understanding of polynomial time. But of course this requires that the logical side is well understood. We hope that our analysis of IFP+C-formulas will help to clarify the expressive power of IFP+C; in particular, we derive a normal form. Moreover, we obtain a problem complete for IFP+C under first-order reductions.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 2 , June 2000 , pp. 777 - 787
Copyright
Copyright © Association for Symbolic Logic 2000

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]Cai, J., Fürer, M., and Immerman, N., An optimal lower bound on the number of variables for graph identification, Combinatorica, vol. 12 (1992), pp. 389–410.CrossRefGoogle Scholar
[2]Dahlhaus, E., Skolem normal forms concerning the least fixed point, Computation theory and logic (Börger, E., editor). Lecture Notes in Computer Science, no. 270, Springer-Verlag, 1987, pp. 20–36.Google Scholar
[3]Dawar, A., Generalized quantifiers and logical reducibilities, Journal of Logic and Computation, vol. 5 (1995), pp. 213–226.CrossRefGoogle Scholar
[4]Dawar, A., Lindell, S., and Weinstein, S., Infinitary logic and inductive definability over finite structures, Information and Computation, vol. 119 (1995), pp. 160–175.CrossRefGoogle Scholar
[5]Ebbinghaus, H.-D. and Flum, J., Finite model theory, Springer-Verlag, 1995.Google Scholar
[6]Flum, J., Kubierschky, M., and Ludäscher, B., Total and partial well-founded datalog coincide, Proceedings of the 6th International Conference on database theory, 1997, Lecture Notes in Computer Science, no. 1186, Springer-Verlag, pp. 113–129.Google Scholar
[7]Grädel, E. and Otto, M., Inductive definability with counting on finite structures, Computer science logic, 6th workshop, CSL '92, San Miniato 1992, selected papers (Börger, E., Jäger, G., Büning, H. Kleine, Martini, S., and Richter, M. M., editors), Lecture Notes in Computer Science, no. 702, Springer-Verlag, 1993, pp. 231–247.Google Scholar
[8]Grohe, M., Complete problems for fixed-point logics, this Journal, vol. 60 (1995), pp. 517–527.Google Scholar
[9]Grohe, M., Fixed-point logics on planar graphs, Proceedings of the 13th IEEE symposium on logic in computer science, 1998, pp. 6–15.Google Scholar
[10]Grohe, M. and Mariño, J., Definability and descriptive complexity on databases of bounded tree-width, Proceedings of the 7th International Conference on database theory (Beeri, C., editor), Lecture Notes in Computer Science, Springer-Verlag, 1999, to appear.Google Scholar
[11]Gurevich, Y. and Shelah, S., Fixed point extensions of first-order logic, Annals of Pure and Applied Logic, vol. 32 (1986), pp. 265–280.CrossRefGoogle Scholar
[12]Imhof, H., Regular logics that define their own semantics, to appear in Archive for Mathematical Logic.Google Scholar
[13]Immerman, N., Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.CrossRefGoogle Scholar
[14]Immerman, N., Expressibility as a complexity measure: results and directions, Proceedings of the 2nd IEEE symposium on structure in complexity theory, 1987, pp. 194–202.Google Scholar
[15]Immerman, N. and Lander, E., Describing graphs: A first-order approach to graph canonization, Complexity theory retrospective (Selman, A., editor), Springer-Verlag, 1990, pp. 59–81.CrossRefGoogle Scholar
[16]Otto, M., The expressive power of fixed-point logic with counting, this Journal, vol. 61 (1996), pp. 147–176.Google Scholar
[17]Otto, M., Bounded variable logics and counting, Lecture Notes in Logic, no. 9, Springer-Verlag, 1997.CrossRefGoogle Scholar
[18]Vardi, M. Y., The complexity of relational query languages, Proceedings of the 14th ACM symposium on theory of computing, 1982, pp. 137–146.Google Scholar