Skip to main content
SpringerLink
Log in

The k-variable property is stronger than H-dimension k

  • Published:
Journal of Philosophical Logic Aims and scope Submit manuscript

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

REFERENCES

  1. H. Andréka, Complexity of Equations Valid in Algebras of Relations, Dissertation for D.Sc. with the Hung. Acad. of Sci., Budapest, 1992.

    Google Scholar 

  2. H. Andr00E9ka and I. N00E9meti, Relation Algebraic Conditions for Representability of Cylindric and Polyadic Algebras, Preprint, Math. Inst. of the Hung. Acad. of Sci., Budapest, 1988. Submitted.

    Google Scholar 

  3. P.J. Cameron, Oligomorphic Permutation Groups, London Mathematical Society Lecture Notes 152, Cambridge University Press, 1990.

  4. A. Dawar, S. Lindell, and S. Weinstein, Infinitary logic and inductive definability over finite structures, Information and Computation 119(1995), 160–175.

    Google Scholar 

  5. J. Flum, On bounded theories, in: E. Boerger, G. Jaeger, H. Kleine Buening, and M.M. Richter (eds.), Proc. Computer Science Logic 91, Berne, Lecture Notes in Computer Science 626, Springer-Verlag, 111–118.

  6. D.M. Gabbay, Expressive functional completeness in tense logic, in: U. Monnich (ed.), Aspects of Philosophical Logic, Reidel, Dordrecht, 1981, 91–117.

    Google Scholar 

  7. D.M. Gabbay, I.M. Hodkinson, and M.A. Reynolds, Temporal logic, Volume 1, Oxford University Press, 1994.

  8. L. Henkin, Logical systems containing only a finite number of symbols, Les Presses de l’ Université de Montréal, Montréal, Canada, 1967.

    Google Scholar 

  9. I.M. Hodkinson, Finite H-dimension does not imply expressive completeness, J. Philosophical Logic 23(1994), 535–573.

    Google Scholar 

  10. I.M. Hodkinson, Finite variable logics, Bull. Europ. Assoc. Theor. Comp. Sci. 51(1993), 111–140.

    Google Scholar 

  11. N. Immerman, Upper and lower bounds for first-order expressibility, J. Comput. System Sci. 25(1982), 76–98.

    Google Scholar 

  12. N. Immerman and D. Kozen, Definability with bounded number of bound variables, Proceedings IEEE (1987), 236–244.

  13. J.A.W. Kamp, Tense Logic and the Theory of Linear Order, Ph.D. thesis, University of California, 1968.

  14. Ph. Kolaitis and M. Vardi, Infinitary logics and 0–1 laws, Information and Computation 98(1992), 258–294.

    Google Scholar 

  15. I. N00E9meti, Free Algebras and Decidability in Algebraic Logic, Dissertation for D.Sc. with the Hung. Acad. Sci., Budapest, 1986 (in Hungarian).

    Google Scholar 

  16. A. Tarski and S. Givant, A Formalization of Set Theory without Variables, AMS Colloquium publications, Providence, R.I., Vol. 41, 1987.

  17. Y. Venema, Many-dimensional Modal Logic, Ph.D. Thesis, University of Amsterdam, 1992.

Download references

Author information

Authors and Affiliations

  1. Department of Computing, Imperial College, 180 Queen’s Gate, London, SW7 2BZ, U.K

    Ian Hodkinson

  2. Mathematical Institute of the Hungarian Academy of Sciences, Budapest, P.O.B. 127, H-1364, Hungary

    András Simon

Authors
  1. Ian Hodkinson
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. András Simon
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Hodkinson, I., Simon, A. The k-variable property is stronger than H-dimension k . Journal of Philosophical Logic 26, 81–101 (1997). https://doi.org/10.1023/A:1017951631048

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1017951631048

Search

Navigation