Interpolation theorems for some variants of LTL
Choose format
RIS BIB ENDNOTEInterpolation theorems for some variants of LTL
Publication date: 21.10.2015
Reports on Mathematical Logic, 2015, Number 50, pp. 3-30
https://doi.org/10.4467/20842589RM.15.001.3910Authors
Interpolation theorems for some variants of LTL
It is known that Craig interpolation theorem does not hold for LTL. In this paper, Craig interpolation theo- rems are shown for some fragments and extensions of LTL. These theorems are simply proved based on an embedding-based proof method with Gentzen-type sequent calculi. Maksimova separation theorems (Maksimova principle of variable separation) are also shown for these LTL variants.
A. Almukdad and D. Nelson, Constructible falsity and inexact predicates, Journal of Symbolic Logic 49 (1984), 231–233.
S. Baratella and A. Masini, An approach to infinitary temporal proof theory, Archive for Mathematical Logic 43:8 (2004), 965–990.
W. Craig, Three uses of the Herbrand-Gentzen theorems in relating model theory and proof theory, Journal of Symbolic Logic 22:3 (1957), 269–285.
E.M. Clarke, O. Grumberg, and D.A. Peled, Model checking, The MIT Press, 1999.
A. Gheerbrant and B. ten Cate, Craig interpolation for linear temporal languages, Proceedings of the 23rd International Conference on Computer Science Logic, Lecture Notes in Computer Science 5771, 2009, pp. 287–301.
Y. Gurevich, Intuitionistic logic with strong negation, Studia Logica 36 (1977), pp. 49–59.
N. Kamide, An equivalence between sequent calculi for linear-time temporal logic, Bulletin of the Section of the Logic 35:4 (2006), 187–194.
N. Kamide, Embedding linear-time temporal logic into infinitary logic: Application to cut-elimination for multi-agent infinitary epistemic linear-time temporal logic, Lecture Notes in Artificial Intelligence 5405, 2009, pp. 57–76.
N. Kamide, Notes on Craig interpolation for LJ with strong negation, Mathematical Logic Quarterly 57:4 (2011), 395–399.
N. Kamide, Bounded linear-time temporal logic: A proof-theoretic investigation, it Annals of Pure and Applied Logic 163:4 (2012), 439–466.
N. Kamide and H. Wansing, A paraconsistent linear-time temporal logic, Fundamenta Infomaticae 106:1 (2011), 1–23.
H. Kawai, Sequential calculus for a rst order infinitary temporal logic, Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik 33 (1987), 423–432.
B. Knov, D. Walther and F. Wolter, Forgetting and uniform interpolation in large-scale description logic terminologies, Proceedings of the 21st International Joint Conference on Artificial Intelligence, 2009, pp. 830–835.
E.G.K. Lopez-Escobar, An interpolation theorem for denumerably long sentences, Fund. Math. 57 (1965), 253–272.
Information: Reports on Mathematical Logic, 2015, Number 50, pp. 3-30
Article type: Original article
Teikyo University, Faculty of Science and Engineering, Department of Human Information Systems, Toyosatodai 1-1, Utsunomiya-shi, Tochigi 320-8551, Japan
Published at: 21.10.2015
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
English