Algorithmic complexity of monadic multimodal predicate logics with equality over finite Kripke frames

2023/06/23 by Irina Agadzhanian, Mikhail Rybakov, Agadzhanian, I. +3 · 1 citation
Computer Science · #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO)

paper · pdf · doi:10.48550/arxiv.2306.13559

openalex publication_date 2023/06/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The paper investigates algorithmic complexity of monadic multimodal predicate logics with equality over finite Kripke frames or classes of finite Kripke frames. Precise complexity bounds for monadic logics of classes of Kripke frames with finitely many possible worlds are obtained.

Cited by

• Superintuitionistic predicate logics of linear frames: undecidability with two individual variables

Related

• Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version)
• Kripke trick and decidability of monadic fragments of modal and superintuitionistic logics
• Tiling problems and complexity of logics (extended version)
• Modelling of logical systems by means of their fragments
• Elementary Multimodal Logics