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...
Linear Kripke frames and Gödel logics
Linear Kripke frames and Gödel logics
AbstractWe investigate the relation between intermediate predicate logics based on countable linear Kripke frames with constant domains and Gödel logics. We show that for any such ...
Longitudinal Association of Telomere Dynamics with Obesity and Metabolic Disorders in Young Children
Longitudinal Association of Telomere Dynamics with Obesity and Metabolic Disorders in Young Children
In adults, short leukocyte telomere length (LTL) is associated with metabolic disorders, such as obesity and diabetes mellitus type 2. These associations could stem from early life...
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é...
LTL transformation modulo positive transitions
LTL transformation modulo positive transitions
In this study, the author presents a new efficient algorithm for translating linear temporal logic (LTL) formulas to Büchi automata, which are used by LTL model checkers. The gener...
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...

