On the decidability of elementary modal logics

DOI10.1145/2817825MaRDI QIDQ5277903zbMATH OpenOpenAlexWikidataFDO

Authors Jakub Michaliszyn, Jan Otop, Emanuel Kieroński

Publication date 12 July 2017

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2817825

zbMATH Keywords

computational complexitymodal logicelementary logics

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25)

Recommendations

• Decidable elementary modal logics
• scientific article; zbMATH DE number 6302919
• Modal logics definable by universal three-variable formulas
• Elementary modal logics over transitive structures
• Satisfiability versus Finite Satisfiability in Elementary Modal Logics

Cites work

• scientific article; zbMATH DE number 3499717 (Why is no real title available?)
• scientific article; zbMATH DE number 1048047 (Why is no real title available?)
• scientific article; zbMATH DE number 6302919 (Why is no real title available?)
• A Universally Defined Undecidable Unimodal Logic
• Complexity of the two-variable fragment with counting quantifiers
• Decidable elementary modal logics
• Guarded negation
• Modal logic
• Modal logics definable by universal three-variable formulas
• On languages with two variables
• On the Restraining Power of Guards
• On the complexity of elementary modal logics
• Relationships between nondeterministic and deterministic tape complexities
• Remarks on Berger's paper on the domino problem
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The price of universality
• The undecidability of the domino problem
• Two variable first-order logic over ordered domains
• Two-variable first-order logic with equivalence closure
• \(\mathrm{FO}^2\) with one transitive relation is decidable

Cited in

(19)

• On the complexity of elementary modal logics
• Decidable elementary modal logics
• Elementary definability and completeness in general and positive modal logic
• On the complexity of fragments of modal logics
• Satisfiability versus Finite Satisfiability in Elementary Modal Logics
• On the decidability of open logic
• Modal logics definable by universal three-variable formulas
• Decidability and complexity of the fragments of the modal logic of Allen's relations over the rationals
• Elementary modal logics over transitive structures
• Decidable fragments of first-order modal logics
• scientific article; zbMATH DE number 3847361 (Why is no real title available?)
• Decidability of some classes of modal logic
• Decidability of order-based modal logics
• scientific article; zbMATH DE number 2149469 (Why is no real title available?)
• A note on the complexity of the satisfiability of modal Horn clauses
• Satisfiability vs. finite satisfiability in elementary modal logics
• scientific article; zbMATH DE number 5046366 (Why is no real title available?)
• From Wittgenstein’s N-operator to a New Notation for Some Decidable Modal Logics
• The decidable normal modal logics are not recursively enumerable

This page was built for publication: On the decidability of elementary modal logics

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