Time and Gödel: fuzzy temporal reasoning in PSPACE

DOI10.1007/978-3-031-15298-6_2MaRDI QIDQ6102991zbMATH OpenOpenAlexFDO

Authors Juan P. Aguilera, Martín Diéguez, David Fernández-Duque, Brett McLean

Publication date 2 June 2023

Published in Logic, Language, Information, and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.00574

zbMATH Keywords

fuzzy logicGödel-Dummett logicintuitionistic logiclinear temporal logicPSPACE-complete

Mathematics Subject Classification ID

Logic in computer science (03B70)

Abstract: We investigate a non-classical version of linear temporal logic whose propositional fragment is G"odel--Dummett logic (which is well known both as a superintuitionistic logic and a t-norm fuzzy logic). We define the logic using two natural semantics, a real-valued semantics and a bi-relational semantics, and show that these indeed define one and the same logic. Although this G"odel temporal logic does not have any form of the finite model property for these two semantics, we show that every falsifiable formula is falsifiable on a finite quasimodel, which yields decidability of the logic. We then strengthen this result by showing that this G"odel temporal logic is PSPACE-complete.

Recommendations

• Gödel-Dummett linear temporal logic
• The complexity of the temporal logic with ``until over general linear time
• The complexity of temporal logic over the reals
• The complexity of propositional linear temporal logics
• Temporal logics over linear time domains are in PSPACE

Cites work

• A sound and complete axiomatization for dynamic topological logic
• Constraint tableaux for two-dimensional fuzzy logics
• Constructivism in mathematics. An introduction. Volume II
• Decidability of order-based modal logics
• First-order Gödel logics
• scientific article; zbMATH DE number 3689368 (Why is no real title available?)
• Intuitionistic linear temporal logics
• Non-deterministic semantics for dynamic topological logic
• On logics with coimplication
• On the Products of Linear Modal Logics
• On transitive modal many-valued logics
• Relationships between nondeterministic and deterministic tape complexities
• Temporal equilibrium logic: a survey
• Temporal here and there
• Temporal logics in computer science. Finite-state systems
• The complexity of propositional linear temporal logics
• The intuitionistic temporal logic of dynamical systems

Cited in

(3)

• Gödel-Dummett linear temporal logic
• Crisp bi-Gödel modal logic and its paraconsistent expansion
• Fuzzy bi-Gödel modal logic and its paraconsistent relatives

This page was built for publication: Time and Gödel: fuzzy temporal reasoning in PSPACE

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102991)