FAQ
logo of Jagiellonian University in Krakow

Interpolation 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.3910

Authors

Norihiro Kamide
Teikyo University, Faculty of Science and Engineering, Department of Human Information Systems, Toyosatodai 1-1, Utsunomiya-shi, Tochigi 320-8551, Japan
Contact with author
All publications →

Download full text

Titles

Interpolation theorems for some variants of LTL

Abstract

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.

References

Download references

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

Information: Reports on Mathematical Logic, 2015, Number 50, pp. 3-30

Article type: Original article

Authors

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:

Norihiro Kamide (Author) - 100%

Article corrections:

-

Publication languages:

English

View count: 2509

Number of downloads: 1203

<p>Interpolation theorems for some variants of LTL</p>

Interpolation theorems for some variants of LTL

cytuj

pobierz pliki

RIS BIB ENDNOTE