The \(k\)-variable property is stronger than H-dimension \(k\). (English) Zbl 0976.03017
Summary: We study the notion of H-dimension and the formally stronger \(k\)-variable property, as considered by Gabbay, Immerman and Kozen. We exhibit a class of flows of time that has H-dimension 3, and admits a finite expressively complete set of one-dimensional temporal connectives, but does not have the \(k\)-variable property for any finite \(k\).
MSC:
| 03B44 | Temporal logic |
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. |
| [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. |
| [3] | P.J. Cameron, Oligomorphic Permutation Groups, London Mathematical Society Lecture Notes 152, Cambridge University Press, 1990. · Zbl 0813.20002 |
| [4] | A. Dawar, S. Lindell, and S. Weinstein, Infinitary logic and inductive definability over finite structures, Information and Computation 119(1995), 160–175. · Zbl 0834.68029 · doi:10.1006/inco.1995.1084 |
| [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. · Zbl 0783.03020 |
| [6] | D.M. Gabbay, Expressive functional completeness in tense logic, in: U. Monnich (ed.), Aspects of Philosophical Logic, Reidel, Dordrecht, 1981, 91–117. · Zbl 0523.03017 |
| [7] | D.M. Gabbay, I.M. Hodkinson, and M.A. Reynolds, Temporal logic, Volume 1, Oxford University Press, 1994. · Zbl 0921.03023 |
| [8] | L. Henkin, Logical systems containing only a finite number of symbols, Les Presses de l’ Université de Montréal, Montréal, Canada, 1967. |
| [9] | I.M. Hodkinson, Finite H-dimension does not imply expressive completeness, J. Philosophical Logic 23(1994), 535–573. · Zbl 0811.03027 · doi:10.1007/BF01049409 |
| [10] | I.M. Hodkinson, Finite variable logics, Bull. Europ. Assoc. Theor. Comp. Sci. 51(1993), 111–140. · Zbl 0788.03051 |
| [11] | N. Immerman, Upper and lower bounds for first-order expressibility, J. Comput. System Sci. 25(1982), 76–98. · Zbl 0503.68032 · doi:10.1016/0022-0000(82)90011-3 |
| [12] | N. Immerman and D. Kozen, Definability with bounded number of bound variables, Proceedings IEEE (1987), 236–244. · Zbl 0711.03004 |
| [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. · Zbl 0762.03016 · doi:10.1016/0890-5401(92)90021-7 |
| [15] | I. N00E9meti, Free Algebras and Decidability in Algebraic Logic, Dissertation for D.Sc. with the Hung. Acad. Sci., Budapest, 1986 (in Hungarian). |
| [16] | A. Tarski and S. Givant, A Formalization of Set Theory without Variables, AMS Colloquium publications, Providence, R.I., Vol. 41, 1987. · Zbl 0654.03036 |
| [17] | Y. Venema, Many-dimensional Modal Logic, Ph.D. Thesis, University of Amsterdam, 1992. · Zbl 0785.03007 |
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.
