The complexity of propositional linear temporal logics in simple cases | Zendy

Stéphane Demri | Zendy; Ph. Schnoebelen | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

The complexity of propositional linear temporal logics in simple cases

Author(s) -

Stéphane Demri,

Ph. Schnoebelen

Publication year - 1998

Publication title -

lecture notes in computer science

Language(s) - English

Resource type - Book series

SCImago Journal Rank - 0.249

H-Index - 400

eISSN - 1611-3349

pISSN - 0302-9743

ISBN - 3-540-64230-7

DOI - 10.1007/bfb0028549

Subject(s) - satisfiability , simple (philosophy) , linear temporal logic , model checking , contrast (vision) , pspace , mathematics , computer science , algorithm , theoretical computer science , computational complexity theory , artificial intelligence , philosophy , epistemology

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research