OATAO - Open Archive Toulouse Archive Ouverte Open Access Week

Intuitionistic linear temporal logics

Balbiani, Philippe and Boudou, Joseph and Diéguez, Martín and Fernández Duque, David Intuitionistic linear temporal logics. (2019) ACM Transactions on Computational Logic, 21 (2). ISSN 1529-3785

(Document in English)

PDF (Author's version) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: https://doi.org/10.1145/3365833


We consider intuitionistic variants of linear temporal logic with “next,” “until,” and “release” based on expanding posets: partial orders equipped with an order-preserving transition function. This class of structures gives rise to a logic that we denote ITLe, and by imposing additional constraints, we obtain the logics ITLp of persistent posets and ITLht of here-and-there temporal logic, both of which have been considered in the literature. We prove that ITLe has the effective finite model property and hence is decidable, while ITLp does not have the finite model property. We also introduce notions of bounded bisimulations for these logics and use them to show that the “until” and “release” operators are not definable in terms of each other, even over the class of persistent posets.

Item Type:Article
HAL Id:hal-02881840
Audience (journal):International peer-reviewed journal
Uncontrolled Keywords:
Institution:French research institutions > Centre National de la Recherche Scientifique - CNRS (FRANCE)
Université de Toulouse > Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE)
Other partners > Institut Mines-Télécom (FRANCE)
Other partners > Université de Bretagne Occidentale - UBO (FRANCE)
Université de Toulouse > Université Toulouse III - Paul Sabatier - UT3 (FRANCE)
Université de Toulouse > Université Toulouse - Jean Jaurès - UT2J (FRANCE)
Université de Toulouse > Université Toulouse 1 Capitole - UT1 (FRANCE)
Other partners > IMT Atlantique Bretagne-Pays de la Loire - IMT Atlantique (FRANCE)
Other partners > Universiteit Gent - UGENT (BELGIUM)
Other partners > Université de Bretagne Sud - UBS (FRANCE)
Laboratory name:
Deposited On:26 Jun 2020 07:40

Repository Staff Only: item control page