On the expressive power of counting. (English) Zbl 0874.68091
Summary: We investigate the expressive power of various extensions of first-order, inductive, and infinitary logic with counting quantifiers. We consider in particular a LOGSPACE extension of first-order logic, and a PTIME extension of fixpoint logic with counters. Counting is a fundamental tool of algorithms. It is essential in the case of unordered structures. Our aim is to understand the expressive power gained with a limited counting ability. We consider two problems: (i) unnested counters, and (ii) counters with no free variables. We prove a hierarchy result based on the arity of the counters under the first restriction. The proof is based on a game technique that is introduced in the paper. We also establish results on the asymptotic probabilities of sentences with counters under the second restriction. In particular, we show that first-order logic with equality of the cardinalities of relations has a 0/1 law.
MSC:
| 68P15 | Database theory |
References:
| [1] | Abiteboul, S.; Vianu, V., Generic computation and its complexity, (Proc. ACM Symp. on Theory of Computing. Proc. ACM Symp. on Theory of Computing, New Orleans (1991)) |
| [2] | Barwise, J., On Moschovakis’ closure ordinals, J. Symbolic Logic, 42, 292-296 (1977) · Zbl 0367.02021 |
| [3] | Barwise, J.; Feferman, S., Model Theoretic Logics (1985), Springer: Springer Berlin · Zbl 0587.03001 |
| [4] | Blass, A.; Gurevich, Y.; Kozen, D., A zero-one law for logic with a fixed-point operator, Inform. and Control, 67, 70-90 (1985) · Zbl 0608.68077 |
| [5] | Cai, J.; Furer, M.; Immerman, N., An optimal lower bound on the number of variables for graph identification, (Proc. IEEE Foundations of Computer Science (1989)), 612-617 |
| [6] | Dawar, A.; Hella, L., The expressive power of finitely many generalized quantifiers, (Proc. IEEE Symp. of Logic in Computer Science (1994)), 20-29 |
| [7] | Dawar, A.; Lindell, S.; Weinstein, S., Infinitary logic and inductive definability over finite structures, Inform. Comput. (1994) |
| [8] | Dublish, P.; Maheshwari, S., Expressibility of bounded-arity fixed-point query hierarchies, (Proc. 8th ACM Symp. on Principles of Database Systems. Proc. 8th ACM Symp. on Principles of Database Systems, Philadelphia (1989)), 324-335 |
| [9] | Ehrenfeucht, A., An application of games to the completeness problem for formalized theories, Fund. Math., 49 (1961) · Zbl 0096.24303 |
| [10] | Fagin, R., Probabilities on finite models, J. Symbolic Logic, 41, 1, 50-58 (1976) · Zbl 0341.02044 |
| [11] | Fagin, R., Finite model theory — a personal perspective, Theoret. Comput. Sci., 116, 3-31 (1993) · Zbl 0788.03037 |
| [12] | Fayolle, G.; Grumbach, S.; Tollu, C., Asymptotic probabilities of languages with generalized quantifiers, (Proc. IEEE Symp. of Logic in Computer Science. Proc. IEEE Symp. of Logic in Computer Science, Montreal (1993)), 199-207 |
| [13] | Fraïssé, R., Sur les classifications des systèmes de relations, Publ. Sci. Univ. Alger, I, 1 (1954) |
| [14] | Gaifman, H., On local and non local properties, (Stern, J., Proc. Herbrand Symposium Logic Colloquium (1981), North-Holland: North-Holland Amsterdam), 105-135 · Zbl 0518.03008 |
| [15] | Glebskii, Y.; Kogan, D.; Liogon’kii, M.; Talanov, V., Range and degree of realizability of formulas in the restricted predicate calculus, Kibernetica (1969) |
| [16] | Grädel, E.; Otto, M., Inductive definability with counting on finite structures, (Proc. of Computer Science Logic 92. Proc. of Computer Science Logic 92, Lecture Notes in Computer Science, Vol. 702 (1993), Springer: Springer Berlin), 207-231 · Zbl 0792.68061 |
| [17] | Grandjean, E., Complexity of the first order theory of almost all structures, Inform. and Control, 52, 180-204 (1983) · Zbl 0542.03018 |
| [18] | Gurevich, Y.; Shelah, S., Fixed-point extensions of first order logic, (Proc. IEEE Foundations of Computer Science (1985)) · Zbl 0621.03013 |
| [19] | Grumbach, S.; Tollu, C., Query languages with counters, (Biskup, J.; Hull, R., Proc. Int. Conf. on Database Theory. Proc. Int. Conf. on Database Theory, Lecture Notes in Computer Science, Vol 646 (1992), Springer: Springer Berlin), 124-139 |
| [20] | Gurevich, Y., Algebras of feasible functions, (Proc. IEEE Foundations of Computer Science (1983)), 210-214 |
| [21] | Gurevich, Y., Logic and the challenge of computer science, (Borger, E., Current Trends in Theoretical Computer Science (1988), Computer Science Press: Computer Science Press Rockville, MI), 1-57 |
| [22] | Hartig, H., Über einen Quantifikator mit zwei Wirkungsbereichen, (Kalmar, L., Colloquium on Foundations of Mathematics, Mathematical Machines and their Applications. Colloquium on Foundations of Mathematics, Mathematical Machines and their Applications, Budapest (1965)), 31-36 · Zbl 0154.00503 |
| [23] | Hella, L., Logical hierarchies in PTIME, (Proc. 7th Symp. of Logic in Computer Science (1992)) · Zbl 0864.68095 |
| [24] | Immerman, N.; Lander, E., Describing graphs: A first-order approach to graph canonization, (Selman, A., Complexity Theory Retrospective (1990), Springer: Springer Berlin), 59-81 |
| [25] | Immerman, N., Relational queries computable in polynomial time, Inform. and Control, 68, 86-104 (1986) · Zbl 0612.68086 |
| [26] | Knyazev, V., Cybernetics, 26, 292-296 (1990), English translation appears in · Zbl 0752.03021 |
| [27] | Kolaitis, P.; Vardi, M. Y., The decision problem for the probabilities of higher properties, (Proc. 19th ACM Symp. on Theory of Computing (1987)), 425-435 |
| [28] | Kolaitis, P.; Vardi, M. Y., 0-1 laws and decision problems for fragments of second order logic, Inform. and Comput., 87, 302-338 (1990) · Zbl 0708.03004 |
| [29] | Kolaitis, P.; Vardi, M. Y., On the expressive power of datalog: Tools and a case study, (Proc. 9th ACM Symp. on Principles of Database Systems (1990)), 61-71 |
| [30] | Kolaitis, P.; Vardi, M. Y., Fixpoint logic vs. infinitary logic in finite model theory, (Proc. 7th Symp. of Logic in Computer Science (1992)), 46-57 |
| [31] | Kolaitis, P.; Vardi, M. Y., Infinitary logic and 0-1 laws, Inform. and Comput., 98, 2, 258-294 (1992) · Zbl 0762.03016 |
| [32] | Kolaitis, P.; Väänänen, J. A., Generalized quantifiers and pebble games on finite structures, (Proc. 7th Symp. of Logic in Computer Science (1992)), to appear in Ann. Pure Appl. Logic · Zbl 0826.03017 |
| [33] | Lindström, P., First order predicate logic with generalized quantifiers, Theoria, 32, 186-195 (1966) · Zbl 1230.03072 |
| [34] | Lynch, J., Almost sure theories, Ann. Math. Logic, 18, 91-135 (1980) · Zbl 0433.03020 |
| [35] | Mostowski, A., On a generalization of quantifiers, Fund. Math., 44, 12-36 (1957) · Zbl 0078.24401 |
| [36] | Otto, M., The expressive power of fixed-point logic with counting (1992), manuscript |
| [37] | Rescher, N., Plurality quantification, J. Symbolic Logic, 27, 373-374 (1962) |
| [38] | Vardi, M., The complexity of relational query languages, (Proc. 14th ACM Symp. on Theory of Computing (1982)), 137-146 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
