# The Complexity of Clausal Fragments of LTL

arXiv: https://arxiv.org/abs/1306.5088 · HTML: https://mlsanity.com/paper/1306.5088/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2013.

## Built on by (most cited first, 1 of 1)

- [On Deciding the Data Complexity of Answering Linear Monadic Datalog Queries with LTL Operators(Extended Version)](https://mlsanity.com/paper/2501.13762/) (2025)

## Abstract (arXiv)

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.