Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Gödel logics and the fully boxed fragment of LTL
View through CrossRef
In this paper we show that a very basic fragment of FO-LTL, the monadic fully boxed fragment (all connectives and quantifiers are guarded by P) is not recursively enumerable wrt validity and 1-satisfiability if three predicates are present. This result is obtained by reduction of the fully boxed fragment of FO-LTL to the Gödel logic G↓, the infinitely valued Gödel logic with truth values in [0,1] such that all but 0 are isolated. The result on 1-satisfiability is in no way symmetric to the result on validity as in classical logic: this is demonstrated by the analysis of G↑, the related infinitely-valued Gödel logic with truth values in [0, 1] such that all but 1 are isolated. Validity of the monadic fragment with at least two predicates is not recursively enumerable, 1-satisfiability of the monadic fragment is decidable.
Title: Gödel logics and the fully boxed fragment of LTL
Description:
In this paper we show that a very basic fragment of FO-LTL, the monadic fully boxed fragment (all connectives and quantifiers are guarded by P) is not recursively enumerable wrt validity and 1-satisfiability if three predicates are present.
This result is obtained by reduction of the fully boxed fragment of FO-LTL to the Gödel logic G↓, the infinitely valued Gödel logic with truth values in [0,1] such that all but 0 are isolated.
The result on 1-satisfiability is in no way symmetric to the result on validity as in classical logic: this is demonstrated by the analysis of G↑, the related infinitely-valued Gödel logic with truth values in [0, 1] such that all but 1 are isolated.
Validity of the monadic fragment with at least two predicates is not recursively enumerable, 1-satisfiability of the monadic fragment is decidable.
Related Results
LTL Goal Specifications Revisited
LTL Goal Specifications Revisited
The language of linear temporal logic (LTL) has been proposed as a formalism for specifying temporally extended goals and search control constraints in planning. However, the seman...
Many Valued Logic of Gödel and Łukasiewicz
Many Valued Logic of Gödel and Łukasiewicz
Gödel and Łukasiewicz proposed the three-valued logic by adding the third logical situation, which includes uncertainty and ambiguity, to the classical two logical values, true or ...
Overinterpreting Logics
Overinterpreting Logics
Paraconsistent logics, minimally, are not explosive; that is, on these logics, not everything follows from a contradiction of the form ‘A and not-A’. Dialetheists, who argue that s...
Rosser Systems
Rosser Systems
Our first proof of the incompleteness of P.A. was based on the assumption that P.A. is correct. Gödel’s proof of the last chapter was based on the metamathematically weaker assumpt...
Converging from branching to linear metrics on Markov chains
Converging from branching to linear metrics on Markov chains
We study two well-known linear-time metrics on Markov chains (MCs), namely, the strong and strutter trace distances. Our interest in these metrics is motivated by their relation to...
Epistemic extensions of substructural inquisitive logics
Epistemic extensions of substructural inquisitive logics
Abstract
In this paper, we study the epistemic extensions of distributive substructural inquisitive logics. Substructural inquisitive logics are logics of questions ...