13 citations · 27 across the 3 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
math.LO2019★ 9 cited
Recursive enumerability and elementary frame definability in predicate modal logic
Mikhail Rybakov, Dmitry Shkatov
We investigate the relationship between recursive enumerability and elementary frame definability in first-order predicate modal logic. On the one hand, it is well-known that every…
math.LO2019★ 5 cited
Complexity of finite-variable fragments of propositional modal logics of symmetric frames
Mikhail Rybakov, Dmitry Shkatov
While finite-variable fragments of the propositional modal logic S5--complete with respect to reflexive, symmetric and transitive frames--are polynomial-time decidable, the restric…
cs.LO2019
Complexity and expressivity of propositional dynamic logics with finitely many variables
Mikhail Rybakov, Dmitry Shkatov
We investigate the complexity of satisfiability for finite-variable fragments of propositional dynamic logics. We consider three formalisms belonging to three representative comple…