Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
The Complexity of Generalized Satisfiability for Linear Temporal Logic
View through CrossRef
In a seminal paper from 1985, Sistla and Clarke showed that satisfiability
for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete,
depending on the set of temporal operators used. If, in contrast, the set of
propositional operators is restricted, the complexity may decrease. This paper
undertakes a systematic study of satisfiability for LTL formulae over
restricted sets of propositional and temporal operators. Since every
propositional operator corresponds to a Boolean function, there exist
infinitely many propositional operators. In order to systematically cover all
possible sets of them, we use Post's lattice. With its help, we determine the
computational complexity of LTL satisfiability for all combinations of temporal
operators and all but two classes of propositional functions. Each of these
infinitely many problems is shown to be either PSPACE-complete, NP-complete, or
in P.
Centre pour la Communication Scientifique Directe (CCSD)
Title: The Complexity of Generalized Satisfiability for Linear Temporal Logic
Description:
In a seminal paper from 1985, Sistla and Clarke showed that satisfiability
for Linear Temporal Logic (LTL) is either NP-complete or PSPACE-complete,
depending on the set of temporal operators used.
If, in contrast, the set of
propositional operators is restricted, the complexity may decrease.
This paper
undertakes a systematic study of satisfiability for LTL formulae over
restricted sets of propositional and temporal operators.
Since every
propositional operator corresponds to a Boolean function, there exist
infinitely many propositional operators.
In order to systematically cover all
possible sets of them, we use Post's lattice.
With its help, we determine the
computational complexity of LTL satisfiability for all combinations of temporal
operators and all but two classes of propositional functions.
Each of these
infinitely many problems is shown to be either PSPACE-complete, NP-complete, or
in P.
Related Results
A History of Satisfiability
A History of Satisfiability
This chapter traces the links between the notion of Satisfiability and the attempts by mathematicians, philosophers, engineers, and scientists over the last 2300 years to develop e...
MECHANISMS OF SCHEMATIC MODELING BASED ON VECTOR LOGIC
MECHANISMS OF SCHEMATIC MODELING BASED ON VECTOR LOGIC
Context. This paper addresses issues relevant to the EDA market – reducing the cost and time of testing and verification of digital projects by synthesizing the logic vector of a d...
Logic in the early 20th century
Logic in the early 20th century
The creation of modern logic is one of the most stunning achievements of mathematics and philosophy in the twentieth century. Modern logic – sometimes called logistic, symbolic log...
Role of the Frontal Lobes in the Propagation of Mesial Temporal Lobe Seizures
Role of the Frontal Lobes in the Propagation of Mesial Temporal Lobe Seizures
Summary: The depth ictal electroencephalographic (EEG) propagation sequence accompanying 78 complex partial seizures of mesial temporal origin was reviewed in 24 patients (15 from...
Satisfiability in composition-nominative logics
Satisfiability in composition-nominative logics
Abstract
Composition-nominative logics are algebra-based logics of partial predicates constructed in a semantic-syntactic style on the methodological basis, which is...
Bounded Satisfiability Checking of FOL * Formulas with Aggregations
Bounded Satisfiability Checking of FOL * Formulas with Aggregations
Abstract
Software systems handling data are increasingly required to comply with legal properties (LPs) aimed at ensuring security and data privacy. Automated reasoning of ...
Energy Based Logic Mining Analysis with Hopfield Neural Network for Recruitment Evaluation
Energy Based Logic Mining Analysis with Hopfield Neural Network for Recruitment Evaluation
An effective recruitment evaluation plays an important role in the success of companies, industries and institutions. In order to obtain insight on the relationship between factors...
URUTAN LOGIS DAN TEMPORAL DALAM NOVEL KUBAH KARYA AHMAD TOHARI (THE LOGICAL AND TEMPORAL PLOTS OF KUBAH NOVEL BY AHMAD TOHARI)
URUTAN LOGIS DAN TEMPORAL DALAM NOVEL KUBAH KARYA AHMAD TOHARI (THE LOGICAL AND TEMPORAL PLOTS OF KUBAH NOVEL BY AHMAD TOHARI)
AbstractThe Logical and Temporal Plots of Kubah Novel by Ahmad Tohari.‘Kubah’ is the firstnovel of Ahmad Tohari which tells life issues of Karman with the background of September30...