Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-18T20:39:28.887Z Has data issue: false hasContentIssue false
  • English
  • Français

The dimension of the negation of transitive closure

Published online by Cambridge University Press:  12 March 2014

Gregory L. McColm
Gregory L. McColm*
Affiliation:
Department of Mathematics, University of South Florida, Tampa, Florida 33620, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that any positive elementary (least fixed point) induction expressing the negation of transitive closure on finite nondirected graphs requires at least two recursion variables.

Keywords

Finite model theorycomputational expressibilitypebble gamestransitive closureconnectivityfixedpoint logicnumber of variables
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 60 , Issue 2 , June 1995 , pp. 392 - 414
Copyright
Copyright © Association for Symbolic Logic 1995

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

Aho, A. V. and Ullman, J. D. [1979], Universality of data retrieval languages, Conference record of the sixth ACM symposium on principles of programming languages (San Antonio, Texas, 1979), ACM, New York, 1979, pp. 110–120.Google Scholar
Ajtai, M. and Fagin, R. [1990], Reachability is harder for directed than for undirected graphs, this Journal, vol. 55 (1990), pp. 113–150.Google Scholar
Buchi, J. R. [1973], The monadic second order theory of ω1, Decidable theories II: The monadic second order theory of all countable ordinals (Müller, G. H. and Siefkes, D., editors), Lecture Notes in Mathematics, vol. 328, Springer-Verlag, Berlin, 1973, pp. 1–127.CrossRefGoogle Scholar
Chandra, A. and Harel, D. [1982], Structure and complexity of relational queries, Journal of Computer and System Sciences, vol. 25 (1982), pp. 99–128.CrossRefGoogle Scholar
Ehrenfeucht, A. [1961], An application of games to the completeness problem for formalized theories, Fundamenta Mathematicae, vol. 49 (1961), pp. 120–141.CrossRefGoogle Scholar
Fagin, R. [1974], Generalized first-order spectra and polynomial-time recognizable sets, SIAM-AMS Proceedings (Karp, R., editor), American Mathematical Society, Providence, Rhode Island, vol. 7, 1974, pp. 43–73.Google Scholar
Fagin, R. [1975], Monadic generalized spectra, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 21 (1975), pp. 89–96.CrossRefGoogle Scholar
Grohe, M. [1993], Bounded-arity hierarchies in fixedpoint logic, Ph.D.thesis, Universität Freiburg, Freiburg, 1993.Google Scholar
Harel, D. and Kozen, D. [1984], A programming language for the inductive sets, and applications, Information and Control, vol. 63 (1984), pp. 118–139.CrossRefGoogle Scholar
Immerman, N. [1981], Number of quantifiers is better than number of tape cells, Journal of Computer and System Sciences, vol. 22 (1981), pp. 384–406.CrossRefGoogle Scholar
Immerman, N. [1982], Upper and lower bounds for first order expressibility, Journal of Computer and System Sciences, vol. 25 (1982), pp. 76–98.CrossRefGoogle Scholar
Immerman, N. [1986], Relational queries computable in polynomial time, Information and Control, vol. 68 (1986), pp. 86–104.CrossRefGoogle Scholar
Immerman, N. [1987], Languages that capture complexity classes, SIAM Journal on Computing, vol. 16 (1987), pp. 760–778.CrossRefGoogle Scholar
Kolaitis, P. G. and Vardi, M. Y. [1990], On the expressive power of datalog: tools and a case study, Proceedings of the ninth ACM symposium on the principles of database systems (Nashville, Tennessee, 1990), ACM, New York, 1990, pp. 61–71.Google Scholar
Ladner, R. E. [1977], Application of model theoretic games to discrete linear orders and finite automata, Information and Control, vol. 33 (1977), pp. 281–303.CrossRefGoogle Scholar
Lakshmanan, V. S. and Mendelzon, A. O. [1989], Inductive pebble games and the expressive powers of datalog, Proceedings of the eighth ACM symposium on the principles of database management, ACM, New York, 1989, pp. 301–310.Google Scholar
McColm, G.L. [1989], Some restrictions on simple fixed points of the integers, this Journal, vol. 54 (1989), pp. 1324–1345.Google Scholar
McColm, G.L. [1990], Parametrization over inductive relations of a bounded number of variables, Annals of Pure and Applied Logic, vol. 48 (1990), pp. 103–134.CrossRefGoogle Scholar
McColm, G. L. [1992], Eventual periodicity and “one-dimensional”queries, Notre Dame Journal of Formal Logic, vol. 33 (1992), pp. 273–290.CrossRefGoogle Scholar
McColm, G. L. [1995A], Dimension versus number of variables, and connectivity, too, Mathematical Logic Quarterly (to appear).Google Scholar
McColm, G. L. [1995B], Pebble games and lease simple fixed points, Information and Computation (to appear).Google Scholar
Moschovakis, Y. N. [1971], The game quantifier, Proceedings of the American Mathematical Society, vol. 31 (1971), pp. 245–250.CrossRefGoogle Scholar
Moschovakis, Y. N. [1974], Elementary induction on algebraic structures, North-Holland, Amsterdam, 1974.Google Scholar
Moschovakis, Y. N. [1983], Abstract recursion as a foundation for the theory of algorithms Computation and proof theory, Logic Colloquium ’;83, Aachen (Richter, M. M.et al., editors), Lecture Notes in Mathematics, vol. 1104, Springer-Verlag, Berlin, 1983, pp. 289–364.Google Scholar
Stolboushkin, A. P. [1994], Finitely monotone properties, unpublished manuscript.Google Scholar
Vardi, M. [1982], Complexity of relational database systems, Fourteenth annual ACM symposium on the theory of computing (San Francisco, California, 1982), ACM, New York, 1982, pp. 137–146.Google Scholar