Search engine for discovering works of Art, research articles, and books related to Art and Culture
ShareThis
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

The causal relationship between genetically determined telomere length and meningiomas risk
The causal relationship between genetically determined telomere length and meningiomas risk
BackgroundStudies have shown that longer leukocyte telomere length (LTL) is significantly associated with increased risk of meningioma. However, there is limited evidence concernin...
Subclinical Hypothyroidism, BDNF, and Telomere Dynamics in T1DM Pregnancy
Subclinical Hypothyroidism, BDNF, and Telomere Dynamics in T1DM Pregnancy
This study investigates the effects of subclinical hypothyroidism and BDNF on telomere length in T1DM mothers and their neonates. Methods: In this prospective cohort study, 70 preg...
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...
Learning and Verifying Temporal Specifications for Cyber-Physical Systems
Learning and Verifying Temporal Specifications for Cyber-Physical Systems
Apprentissage et vérification de systèmes complexes avec des spécifications temporelles Au cours de la dernière décennie, on a assisté à une augmentation sans précé...
Alfred Tarski
Alfred Tarski
Abstract Alfred Tarski first met Kurt Gödel on the occasion of his visit to Vienna early in 1930, at the invitation of Karl Menger. Their subsequent contact, both pe...
GÖDEL’S INCOMPLETENESS THEOREM MAKES THE QUANTUM DOUBLE SLIT EXPERIMENT UNDECIDABLE
GÖDEL’S INCOMPLETENESS THEOREM MAKES THE QUANTUM DOUBLE SLIT EXPERIMENT UNDECIDABLE
Kurt Gödel’s incompleteness theorem refers to incompleteness in the sense that there are always statements which can be formulated within a formal system, but which re-main unprove...
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 ...
Karl Popper
Karl Popper
Abstract Karl Popper (1902-1994) was a noted philosopher, born and educated in Vienna, who from 1946 on taught at the London School of Economics. He first met Gödel ...

Back to Top