Complexity and expressivity of propositional dynamic logics with finitely many variables

DOI10.1093/JIGPAL/JZY014MaRDI QIDQ5095651zbMATH OpenOpenAlexWikidataFDO

Authors Mikhail Rybakov, Dmitry Shkatov

Publication date 10 August 2022

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1901.06407

zbMATH Keywords

computational complexityexpressivityfinite-variable fragmentspropositional dynamic logicsatisfiabilityundecidability

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We investigate the complexity of satisfiability for finite-variable fragments of propositional dynamic logics. We consider three formalisms belonging to three representative complexity classes, broadly understood,---regular PDL, which is EXPTIME-complete, PDL with intersection, which is 2EXPTIME-complete, and PDL with parallel composition, which is undecidable. We show that, for each of these logics, the complexity of satisfiability remains unchanged even if we only allow as inputs formulas built solely out of propositional constants, i.e. without propositional variables. Moreover, we show that this is a consequence of the richness of the expressive power of variable-free fragments: for all the logics we consider, such fragments are as semantically expressive as entire logics. We conjecture that this is representative of PDL-style, as well as closely related, logics.

Recommendations

• Decision complexity of variants of propositional dynamic logic
• scientific article; zbMATH DE number 4179344
• ON THE EXPRESSIVE POWER OF SOME DYNAMIC LOGICS
• scientific article; zbMATH DE number 5599076
• Finitely-valued propositional dynamic logic
• Finite Variable Logics in Descriptive Complexity Theory
• Decidability and expressivity of Ockhamist propositional dynamic logics
• A stochastic interpretation of propositional dynamic logic: expressivity
• A stochastic interpretation of propositional dynamic logic: expressivity
• Complexity of intuitionistic and Visser's basic and formal logics in finitely many variables

Cited in

(17)

• Complexity of finite-variable fragments of propositional temporal and modal logics of computation
• Complexity of the universal theory of modal algebras
• Undecidability of first-order modal and intuitionistic logics with two variables and one monadic predicate letter
• Computational complexity of the word problem in modal and Heyting algebras with a small number of generators
• scientific article; zbMATH DE number 5599076 (Why is no real title available?)
• Complexity of finite-variable fragments of EXPTIME-complete logics
• ON THE EXPRESSIVE POWER OF SOME DYNAMIC LOGICS
• Decision complexity of variants of propositional dynamic logic
• Complexity results for multi-pebble automata and their logics
• Counting variables in a dynamic setting
• Undecidability of QLTL and QCTL with two variables and one monadic predicate letter
• Complexity of finite-variable fragments of propositional modal logics of symmetric frames
• Dynamic logic of propositional assignments: a well-behaved variant of PDL
• A lower complexity bound for propositional dynamic logic with intersection
• Polytime embedding of intuitionistic modal logics into their one-variable fragments
• Algorithmic properties of modal and superintuitionistic logics of monadic predicates over finite Kripke frames
• The comparison of the expressive power of first-order dynamic logics

This page was built for publication: Complexity and expressivity of propositional dynamic logics with finitely many variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5095651)