Time and Godel: Fuzzy Temporal Reasoning in PSPACE

0563275 - ÚI 2023 RIV CH eng C - Konferenční příspěvek (zahraniční konf.)
Aguilera, J. P. - Diéguez, M. - Fernández-Duque, David - McLean, B.
Time and Godel: Fuzzy Temporal Reasoning in PSPACE.
Logic, Language, Information, and Computation. Cham: Springer, 2022 - (Ciabattoni, A.; Pimentel, E.; de Queiroz, R.), s. 18-35. Lecture Notes in Computer Science, 13468. ISBN 978-3-031-15297-9. ISSN 0302-9743.
[WoLLIC 2022: International Workshop on Logic, Language, Information, and Computation /28./. Iași (RO), 20.09.2022-23.09.2022]
Institucionální podpora: RVO:67985807
Klíčová slova: Godel-Dummett logic * linear temporal logic * intuitionistic logic * fuzzy logic * PSPACE-complete
Obor OECD: Pure mathematics
https://dx.doi.org/10.1007/978-3-031-15298-6_2

We investigate a non-classical version of linear temporal logic whose propositional fragment is Godel-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 Godel 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 Godel temporal logic is PSPACE-complete.
Trvalý link: https://hdl.handle.net/11104/0340208