Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-25T04:49:52.005Z Has data issue: false hasContentIssue false
  • English
  • Français

Exploring the Jungle of Intuitionistic Temporal Logics

Published online by Cambridge University Press:  22 April 2021

JOSEPH BOUDOU ,
MARTÍN DIÉGUEZ ,
DAVID FERNÁNDEZ-DUQUE Open the ORCID record for DAVID FERNÁNDEZ-DUQUE [Opens in a new window]  and
PHILIP KREMER
JOSEPH BOUDOU
Affiliation:
IRIT, Toulouse University, Toulouse, France (e-mail: [email protected])
MARTÍN DIÉGUEZ
Affiliation:
LERIA, University of Angers, Angers, France (e-mail: [email protected])
DAVID FERNÁNDEZ-DUQUE
Affiliation:
Department of Mathematics WE16, Ghent University, Ghent, Belgium (e-mail: [email protected])
PHILIP KREMER
Affiliation:
Department of Philosophy, University of Toronto, Toronto, Canada (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

The importance of intuitionistic temporal logics in Computer Science and Artificial Intelligence has become increasingly clear in the last few years. From the proof-theory point of view, intuitionistic temporal logics have made it possible to extend functional programming languages with new features via type theory, while from the semantics perspective, several logics for reasoning about dynamical systems and several semantics for logic programming have their roots in this framework. We consider several axiomatic systems for intuitionistic linear temporal logic and show that each of these systems is sound for a class of structures based either on Kripke frames or on dynamic topological systems. We provide two distinct interpretations of “henceforth”, both of which are natural intuitionistic variants of the classical one. We completely establish the order relation between the semantically defined logics based on both interpretations of “henceforth” and, using our soundness results, show that the axiomatically defined logics enjoy the same order relations.

Keywords

TheoryKnowledge Representation and Nonmonotonic Reasoning
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 21 , Issue 4: TPLP Special Issue from the 16th European Conference on Logics in Artificial Intelligence (JELIA 2019) , July 2021 , pp. 459 - 492
Copyright
© The Author(s), 2021. Published by Cambridge University Press

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.)

Footnotes

*

David Fernández-Duque’s research is partially funded by the SNSF-FWO Lead Agency Grant 200021L 196176 (SNSF)/G0E2121N (FWO).

†

Philip Kremer’s research was supported by the Social Sciences and Humanities Research Council of Canada

References

Aleksandroff, P. 1937. Diskrete Räume. Matematicheskii Sbornik 2, 44, 501–518.Google Scholar
Balbiani, P., Boudou, J., Diéguez, M. and Fernández-Duque, D. 2019. Intuitionistic linear temporal logics. Transactions on Computational Logic 21, 2.Google Scholar
Balbiani, P. and Diéguez, M. 2016. Temporal here and there. In Logics in Artificial Intelligence, Loizos, M. and Kakas, A., Eds. Springer, 81–96.CrossRefGoogle Scholar
Boudou, J., Diéguez, M. and Fernández-Duque, D. 2017. A decidable intuitionistic temporal logic. In 26th EACSL Annual Conference on Computer Science Logic (CSL), Vol. 82, 14:1–14:17.Google Scholar
Boudou, J., Diéguez, M., Fernández-Duque, D. and Romero, F. 2019. Axiomatic systems and topological semantics for intuitionistic temporal logic. In Logics in Artificial Intelligence - 16th European Conference, JELIA 2019, Rende, Italy, May 7–11, 2019, Proceedings, 763–777.Google Scholar
Brewka, G., Eiter, T. and Truszczyński, M. 2011. Answer set programming at a glance. Communications of the ACM 54, 12, 92–103.CrossRefGoogle Scholar
Cabalar, P. and Pérez Vega, G. 2007. Temporal equilibrium logic: A first approach. In Computer Aided Systems Theory – EUROCAST’07. Springer, Berlin, Heidelberg, 241–248.Google Scholar
Davies, R. 1996. A temporal-logic approach to binding-time analysis. In Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, New Brunswick, New Jersey, USA, July 27–30, 1996, 184–195.Google Scholar
Davies, R. 2017. A temporal logic approach to binding-time analysis. Journal of the ACM 64, 1–45.Google Scholar
Davies, R. and Pfenning, F. 2001. A modal analysis of staged computation. Journal of the ACM 48, 3, 555–604.CrossRefGoogle Scholar
Davoren, J. M. 2009. On intuitionistic modal and tense logics and their classical companion logics: Topological semantics and bisimulations. Annals of Pure and Applied Logic 161, 3, 349–367.CrossRefGoogle Scholar
Davoren, J. M., Coulthard, V., Moor, T., Gor, R. and Nerode, A. 2002. Topological semantics for intuitionistic modal logics, and spatial discretisation by A/D maps. In Workshop on Intuitionistic Modal Logic and Applications (IMLA).Google Scholar
Diéguez, M. and Fernández-Duque, D. 2018. An intuitionistic axiomatization of ‘eventually’. In Advances in Modal Logic, Vol. 12, 199–218.Google Scholar
Dugundji, J. 1975. Topology. Allyn and Bacon Series in Advanced Mathematics. Prentice Hall of India, New Delhi.Google Scholar
Ershov, A. P. 1977. On the partial computation principle. Information Processing Letters 6, 2, 38–41.CrossRefGoogle Scholar
Fernández-Duque, D. 2007. Dynamic topological completeness for 2 . Logic Journal of the IGPL 15, 1, 77–107.Google Scholar
Fernández-Duque, D. 2011. Dynamic topological logic interpreted over metric spaces. Journal of Symbolic Logic, 308–328.Google Scholar
Fernández-Duque, D. 2018. The intuitionistic temporal logic of dynamical systems. Logical Methods in Computer Science 14, 3, 1–14.Google Scholar
Fischer Servi, G. 1984. Axiomatisations for some intuitionistic modal logics. In Rendiconti del Seminario Matematico, Vol. 42. Universitie Politecnico Torino, 179–194.Google Scholar
Gabelaia, D., Kurucz, A., Wolter, F. and Zakharyaschev, M. 2006. Non-primitive recursive decidability of products of modal logics with expanding domains. Annals of Pure and Applied Logic 142, 1–3, 245–268.CrossRefGoogle Scholar
Goldblatt, R. 1980. Diodorean modality in minkowski spacetime. Studia Logica 39, 219–236.CrossRefGoogle Scholar
Goldblatt, R. 1992. Logics of Time and Computation, 2 ed., Lecture Notes, CSLI, Vol. 7. Center for the Study of Language and Information, Stanford, CA.Google Scholar
Heyting, A. 1930. Die formalen regeln der intuitionistischen logik. In Sitzungsberichte der preußischen Akademie der Wissenschaften. Physikalisch-mathematische Klasse, 42–56.Google Scholar
Howard, W. A. 1980. The formulas-as-types notion of construction. In To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus, and Formalism, Seldin, J. P. and Hindley, J. R., Eds. Academic Press, 479–490.Google Scholar
Kamide, N. and Wansing, H. 2010. Combining linear-time temporal logic with constructiveness and paraconsistency. Journal of Applied Logic 8, 1, 33–61.CrossRefGoogle Scholar
Kojima, K. and Igarashi, A. 2011. Constructive linear-time temporal logic: Proof systems and Kripke semantics. Information and Computation 209, 12, 1491–1503.CrossRefGoogle Scholar
Konev, B., Kontchakov, R., Wolter, F. and Zakharyaschev, M. 2006. On dynamic topological and metric logics. Studia Logica 84, 129–160.CrossRefGoogle Scholar
Kremer, P. 2004. A small counterexample in intuitionistic dynamic topological logic. http://individual.utoronto.ca/philipkremer/onlinepapers/counterex.pdf.Google Scholar
Kremer, P. 2013. Strong completeness of S4 for any dense-in-itself metric space. Review of Symbolic Logic 6, 3, 545–570.CrossRefGoogle Scholar
Kremer, P. and Mints, G. 2005. Dynamic topological logic. Annals of Pure and Applied Logic 131, 133–158.CrossRefGoogle Scholar
Kurucz, A., Wolter, F., Zakharyaschev, M. and Gabbay, D. M. 2003. Many-Dimensional Modal Logics: Theory and Applications . Studies in Logic and the Foundations of Mathematics, Vol. 148, 1 ed. North Holland.Google Scholar
Lichtenstein, O. and Pnueli, A. 2000. Propositional temporal logics: Decidability and completeness. Logic Jounal of the IGPL 8, 1, 55–85.CrossRefGoogle Scholar
Maier, P. 2004. Intuitionistic LTL and a new characterization of safety and liveness. In 18th EACSL Annual Conference on Computer Science Logic (CSL), Marcinkowski, J. and Tarlecki, A., Eds. Springer Berlin Heidelberg, Berlin, Heidelberg, 295–309.Google Scholar
Mints, G. 2000. A Short Introduction to Intuitionistic Logic. University Series in Mathematics. Springer.Google Scholar
Mostowski, A. 1948. Proofs of non-deducibility in intuitionistic functional calculus. Journal of Symbolic Logic 13, 4, 204–207.CrossRefGoogle Scholar
Nogin, M. and Nogin, A. 2008. On dynamic topological logic of the real line. Journal of Logic and Computation 18, 6, 1029–1045. doi: 10.1093/logcom/exn034.CrossRefGoogle Scholar
Pacuit, E. 2017. Neighborhood Semantics for Modal Logic. Springer.CrossRefGoogle Scholar
Pnueli, A. 1977. The temporal logic of programs. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), 46–57.Google Scholar
Rasiowa, H. and Sikorski, R. 1963. The Mathematics of Metamathematics. Państowowe Wydawnictwo Naukowe, Warsaw.Google Scholar
Simpson, A. K. 1994. The Proof Theory and Semantics of Intuitionistic Modal Logic. Ph.D. thesis, University of Edinburgh, UK.Google Scholar
Slavnov, S. 2003. TR-2003015: Two counterexamples in the logic of dynamic topological systems. CUNY Academic Works.Google Scholar
Tarski, A. 1938. Der Aussagenkalkül und die Topologie. Fundamenta Mathematica 31, 103–134.CrossRefGoogle Scholar
Yuse, Y. and Igarashi, A. 2006. A modal type system for multi-level generating extensions with persistent code. In Proceedings of the 8th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming. PPDP’06, 201–212.Google Scholar