zbMATH — the first resource for mathematics

On dynamic topological and metric logics. (English) Zbl 1114.03026
Summary: We investigate computational properties of propositional logics for dynamical systems. First, we consider logics for dynamic topological systems \(\langle W,f\rangle\), where \(W\) is a topological space and \(f\) a homeomorphism on \(W\). The logics come with ‘modal’ operators interpreted by the topological closure and interior, and temporal operators interpreted along the orbits \(\{w, f(w), f^{2}(w),\dots\}\) of points \(w \in W\). We show that for various classes of topological spaces the resulting logics are not recursively enumerable (and so not recursively axiomatisable). This gives a ‘negative’ solution to a conjecture of Kremer and Mints. Second, we consider logics for dynamical systems \(\langle W,f\rangle\), where \(W\) is a metric space and \(f\) and isometric function. The operators for topological interior/closure are replaced by distance operators of the form ‘everywhere/somewhere in the ball of radius \(a\)’, for \(a \in \mathbb {Q}^+\). In contrast to the topological case, the resulting logic turns out to be decidable, but not in time bounded by any elementary function.

03B60 Other nonclassical logic
03B45 Modal logic (including the logic of norms)
03B44 Temporal logic
03B25 Decidability of theories and sets of sentences
54H20 Topological dynamics (MSC2010)
PDF BibTeX Cite
Full Text: DOI
[1] Alexandroff, P. S., ’Diskrete Räume’, Matematicheskii Sbornik, 2 (44):501–518, 1937.
[2] Artemov, S., J. Davoren, and A. Nerode, Modal logics and topological semantics for hybrid systems, Technical Report MSI 97-05, Cornell University, 1997.
[3] Bourbaki, N., General Topology, Part 1, Hermann, Paris and Addison-Wesley, 1966. · Zbl 0145.19302
[4] Brown, J. R., Ergodic Theory and Topological Dynamics, Academic Press, 1976. · Zbl 0334.28011
[5] Büchi, J. R., ’On a decision method in restricted second order arithmetic’, in Logic, Methodology and Philosophy of Science: Proceedings of the 1960 International Congress, Stanford University Press, 1962, pp. 1–11. · Zbl 0147.25103
[6] Davoren, J., and A. Nerode, ’Logics for hybrid systems’, Proceedings of the IEEE, 88:985–1010, 2000.
[7] Gabbay, D., A. Kurucz, F. Wolter, and M. Zakharyaschev, Many-Dimensional Modal Logics: Theory and Applications, vol. 148 of Studies in Logic, Elsevier, 2003. · Zbl 1051.03001
[8] Gabelaia, D., A. Kurucz, F. Wolter, and M. Zakharyaschev, ’Non-primitive recursive decidability of products of modal logics with expanding domains’, Annals of Pure and Applied Logic, 142:245–268, 2006. · Zbl 1099.03008
[9] Gabelaia, D., R. Kontchakov, A. Kurucz, F. Wolter, and M. Zakharyaschev, ’Combining spatial and temporal logics: expressiveness vs. complexity’, Journal of Artificial Intelligence Research, 23:167–243, 2005. · Zbl 1080.68682
[10] Hopcroft, J., R. Motwani, and J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison–Wesley, 2001. · Zbl 0980.68066
[11] Katok, A., and B. Hasselblatt, Introduction to Modern Theory of Dynamical Systems, vol. 54 of Encyclopedia of Mathematics and its Applications, Elsevier, 1995. · Zbl 0878.58020
[12] B. Konev, F. Wolter, and M. Zakharyaschev, ’Temporal logics over transitive states’, in Procceedings ofthe 20th International Conference on Automated Deduction CADE-20, vol. 3632 of LNAI, 2005, pp. 182–203. · Zbl 1135.03333
[13] Kremer, P., ’Temporal logic over S4: an axiomatizable fragment of dynamic topological logic’, Bulletin of Symbolic Logic, 3:375–376, 1997.
[14] Kremer, P., and G. Mints, ’Dynamic topological logic’, Bulletin of Symbolic Logic, 3:371–372, 1997.
[15] Kremer, P., and G. Mints, ’Dynamic topological logic’, Annals of Pure and Applied Logic, 1-3 (131):133–158, 2005. · Zbl 1067.03028
[16] Kremer, P., G. Mints, and V. Rybakov, ’Axiomatizing the next-interior fragment of dynamic topological logic’, Bulletin of Symbolic Logic, 3:376–377, 1997.
[17] Kutz, O., H. Sturm, N.-Y. Suzuki, F. Wolter, and M. Zakharyaschev, ’Logics of metric spaces’, ACM Transactions on Computational Logic, 4:260–294, 2003.
[18] McKinsey, J.C.C., and A. Tarski, ’The algebra of topology’, Annals of Mathematics, 45:141–191, 1944. · Zbl 0060.06206
[19] Moor, T., and J. Davoren, ’Robust controller synthesis for hybrid systems using modal logics’, in M.D. Di Benedetto and A. Sangiovanni-Vincentelli (eds.), Hybrid Systems: Computation and Control (HSCC’01), vol. 2034 of LNCS. Springer, 2001, pp. 433–446. · Zbl 0991.93038
[20] Post, E., ’A variant of a recursively unsolvable problem’, Bulletin of the AMS, 52:264–268, 1946. · Zbl 0063.06329
[21] Slavnov, S., Two counterexamples in the logic of dynamic topological systems, Technical Report TR–2003015, Cornell University, 2003.
[22] Walters, P., An Introduction to Ergodic Theory, Springer-Verlag, Berlin, 1982. · Zbl 0475.28009
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.