|
Vestnik TVGU. Seriya: Prikladnaya Matematika [Herald of Tver State University. Series: Applied Mathematics], 2007, Issue 5, Pages 5–17
(Mi vtpmk419)
|
|
|
|
This article is cited in 2 scientific papers (total in 2 papers)
Mathematical Foundations of Computer Science
The complexity of the constant fragment of propositional dynamic logic
M. N. Rybakov Tver State University, Department of Mathematics, Tver
Abstract:
The main result of the paper is in that the variable-free fragments of the logics ${\ bf K}^\ ast$ (with ${\ bf K}$-modality and its ‘reflexive and transitive closure’), PDL, and some others are EXPTIME-complete. In the proof some quite general idea how to construct a polynomial reduction of propositional logic to its $n$-variable (and even variable-free in the case of ${\ bf K}^\ ast$ and PDL) fragment is presented. As a corollary we obtain that the one-variable fragments of logics of knowledge with common knowledge operator are EXPTIME-complete.
Keywords:
propositional dynamic logic, complexity, EXPTIME-completeness, decision problem.
Received: 15.05.2007 Revised: 14.06.2007
Linking options:
https://www.mathnet.ru/eng/vtpmk419
|
Statistics & downloads: |
Abstract page: | 33 |
|