English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In a seminal paper from 1985, Sistla and Clarke showed that themodel-checking problem for Linear Temporal Logic (LTL) is either NP-complete orPSPACE-complete, depending on the set of temporal operators used. If, incontrast, the set of propositional operators is restricted, the complexity maydecrease. This paper systematically studies the model-checking problem for LTLformulae over restricted sets of propositional and temporal operators. Foralmost all combinations of temporal and propositional operators, we determinewhether the model-checking problem is tractable (in P) or intractable(NP-hard). We then focus on the tractable cases, showing that they all areNL-complete or even logspace solvable. This leads to a surprising gap incomplexity between tractable and intractable cases. It is worth noting that ouranalysis covers an infinite set of problems, since there are infinitely manysets of propositional operators.

The Tractability of Model-Checking for LTL: The Good, the Bad, and the Ugly Fragments