Affordable Access

deepdyve-link
Publisher Website

The complexity of propositional linear temporal logics in simple cases

Authors
  • Demri, Stéphane
  • Schnoebelen, Ph.
Publication Date
Jan 01, 1998
Identifiers
DOI: 10.1007/BFb0028549
OAI: oai:HAL:hal-03199998v1
Source
HAL-INRIA
Keywords
Language
English
License
Unknown
External links

Abstract

It is well-known that model-checking and satisfiability for PLTL are PSPACE-complete. By contrast, very little is known about whether there exist some interesting fragments of PLTL with a lower worst-case complexity. Such results would help understand why PLTL model-checkers are successfully used in practice.In this paper we investigate this issue and consider model-checking and satisfiability for all fragments of PLTL one obtains when restrictions are put on (1) the temporal connectives allowed, (2) the number of atomic propositions, and (3) the temporal height.

Report this publication

Statistics

Seen <100 times