- Record: found
- Abstract: found
- Article: found
The Complexity of Clausal Fragments of LTL
Preprint
21 June 2013
Read this article at
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.
Abstract
We introduce and investigate a number of fragments of propo- sitional temporal logic LTL over the flow of time (Z, <). The fragments are defined in terms of the available temporal operators and the structure of the clausal normal form of the temporal formulas. We determine the computational complexity of the satisfiability problem for each of the fragments, which ranges from NLogSpace to PTime, NP and PSpace.
Related collections
Most cited references12
- Record: found
- Abstract: not found
- Article: not found
Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family
- Record: found
- Abstract: not found
- Book Chapter: not found
The glory of the past
Orna Lichtenstein, Amir Pnueli, Lenore D. Zuck (1985)