The Computational Complexity of Provability in Systems of Modal Propositional Logic

No abstract is available for this paper.

• Publication year

  1977

• Venue

  SIAM journal on computing (Print)

• Publication date

  1977-09-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/0206033
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An Introduction to Modal Logic

  1977cited by this paper
• The Polynomial-Time Hierarchy

  1976cited by this paper
• SEMANTICAL CONSIDERATIONS ON FLOYD-HOARE LOGIC

  1976cited by this paper
• Space-Bounded Reducibility among Combinatorial Problems

  1975cited by this paper
• The Complexity of Some Non-Classical Logics

  1973cited by this paper
• Word problems requiring exponential time(Preliminary Report)

  1973cited by this paper
• Refinements of the Nondeterministic Time and Space Hierarchies

  1973cited by this paper
• The complexity of theorem-proving procedures

  1971influential reference
• Relationships Between Nondeterministic and Deterministic Tape Complexities

  1970cited by this paper
• Formal languages and their relation to automata

  1969cited by this paper
• Semantical Analysis of Modal Logic I Normal Modal Propositional Calculi

  1963cited by this paper
• Some theorems about the sentential calculi of Lewis and Heyting

  1948cited by this paper

• Extending Defeasibility for Propositional Standpoint Logics

  2025cites this paper
• Complexity of some modal logics of density (extended version)

  2025cites this paper
• Two Types of Filtrations for $${\textsc {wK4}}$$ and Its Relatives

  2025cites this paper
• Logics with the axiom of convergence: complexity with a small number of variables in the language (extended version)

  2025cites this paper
• PSPACE-completeness of bimodal transitive weak-density logic

  2025cites this paper
• Recursive windows for grammar logics of bounded density

  2025cites this paper
• Non-expansive Fuzzy ALC

  2025cites this paper
• FINITE MODEL PROPERTY OF PRETRANSITIVE ANALOGUES OF (w)K4 AND GL

  2024cites this paper
• Decidability of Graph Neural Networks via Logical Characterizations

  2024influential citation
• Hybrid Modal Operators for Definite Descriptions

  2024cites this paper
• Satisfiability Threshold of Random Propositional S5 Theories

  2024cites this paper
• On Modal Logic Formulae Minimization

  2024cites this paper
• The complexity of deciding characteristic formulae in van Glabbeek's branching-time spectrum

  2024cites this paper
• Support + Belief = Decision Trust

  2024cites this paper
• Synchronous Team Semantics for Temporal Logics

  2024cites this paper
• Logic-based cognitive planning for conversational agents

  2024cites this paper
• Data-Aware Hybrid Tableaux

  2024cites this paper
• A Logic for Reasoning About Aggregate-Combine Graph Neural Networks

  2024cites this paper
• Two types of filtrations for $\mathrm{wK4}$ and its relatives

  2023cites this paper
• Complexity results for modal logic with recursion via translations and tableaux

  2023cites this paper
• On the computational complexity of ethics: moral tractability for minds and machines

  2023cites this paper
• Predicate counterparts of modal logics of provability: High undecidability and Kripke incompleteness

  2023cites this paper
• Intuitionistic S4 is decidable

  2023cites this paper
• Strictly Positive Fragments of the Provability Logic of Heyting Arithmetic

  2023cites this paper
• Adding Transitivity and Counting to the Fluted Fragment

  2023cites this paper
• Complexity through Translations for Modal Logic with Recursion

  2022cites this paper
• Epistemic, Default and Dynamic Logics

  2022cites this paper
• Mechanising Gödel–Löb Provability Logic in HOL Light

  2022cites this paper
• Frame definability in finitely valued modal logics

  2022cites this paper
• Complexity of the variable-free fragment of the weak Grzegorczyk logic

  2022cites this paper
• Propositional Modal Logic

  2022cites this paper
• Decidability of Downward XPath

  2022cites this paper
• Computational Complexity of the Word Problem in Modal and Heyting Algebras with a Small Number of Generators

  2022cites this paper
• On Composing Finite Forests with Modal Logics

  2022cites this paper
• Modal logic and the polynomial hierarchy: from QBFs to K and back

  2022cites this paper
• A unified logical framework for explanations in classifier systems

  2021cites this paper
• Computational complexity of one-variable fragments of products with T

  2021cites this paper
• Semiring Provenance for Guarded Logics

  2021cites this paper
• Runtime Verification of Spatio-Temporal Specification Language

  2021cites this paper
• Efficient SAT-Based Minimal Model Generation Methods for Modal Logic S5

  2021cites this paper
• A Simple Framework for Cognitive Planning

  2021influential citation
• Somebody Knows

  2021influential citation
• Computational complexity for bounded distributive lattices with negation

  2021cites this paper
• Understanding Computation Time: A Critical Discussion of Time as a Computational Performance Metric

  2021cites this paper
• A logic for binary classifiers and their explanation

  2021cites this paper
• Modal Logic S5 Satisfiability in Answer Set Programming

  2021cites this paper
• EXPSPACE-Completeness of the Logics K4 × S5 and S4 × S5 and the Logic of Subset Spaces

  2021cites this paper
• Handbook of Satisfiability

  2021influential citation
• A note on the complexity of S4.2

  2021cites this paper
• SAT Techniques for Modal and Description Logics

  2021cites this paper
• Quantitative Modalities, Possible Applications to Information Analysis

  2021cites this paper
• Coalgebraic Reasoning with Global Assumptions in Arithmetic Modal Logics

  2020cites this paper
• NP Reasoning in the Monotone \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu $$\end{document}-Calculus

  2020cites this paper
• NP Reasoning in the Monotone $\mu$-Calculus

  2020cites this paper
• On the Intrinsic Redundancy in Huge Natural Deduction proofs II: Analysing M⊃ Super-Polynomial Proofs

  2020cites this paper
• A spatio-temporal specification language and its completeness & decidability

  2020cites this paper
• Team logic: axioms, expressiveness, complexity

  2020cites this paper
• The Fluted Fragment with Transitive Relations

  2020cites this paper
• On the proof complexity of logics of bounded branching

  2020cites this paper
• Modal Logics with Composition on Finite Forests: Expressivity and Complexity

  2020cites this paper
• Satisfiability Problems on Sums of Kripke Frames

  2020influential citation
• Sequences of Refinements of Rough Sets: Logical and Algebraic Aspects

  2020cites this paper
• The complexity of identifying characteristic formulae

  2020influential citation
• Yet another argument in favour of NP=CoNP

  2020cites this paper
• On satisfiability problem in modal logic S5

  2020influential citation
• Model Checking of Spatial Logic

  2020cites this paper
• Going from the huge to the small: Efficient succinct representation of proofs in Minimal implicational logic

  2020cites this paper
• STSL: A Novel Spatio-Temporal Specification Language for Cyber-Physical Systems

  2020cites this paper
• Exponentially Huge Natural Deduction proofs are Redundant: Preliminary results on M⊃

  2020cites this paper
• Pure Sequent Calculi

  2019cites this paper
• Computational Complexity of Core Fragments of Modal Logics T, K4, and S4

  2019cites this paper
• Complexity of the Universal Theory of Modal Algebras

  2019cites this paper
• A PSpace-algorithm for ALCQI-satis(cid:12)ability

  2019cites this paper
• Modal Resolution

  2019cites this paper
• The Fluted Fragment with Transitivity

  2019cites this paper
• New results on probabilistic verification: automata, logic and satisfiability

  2019cites this paper
• Solving the Satisfiability Problem of Modal Logic S5 Guided by Graph Coloring

  2019cites this paper
• Proof complexity of modal resolution systems

  2019influential citation
• Rules with parameters in modal logic II

  2019influential citation
• EXPSPACE-Completeness of the Logics K4xS5 and S4xS5 and the Logic of Subset Spaces, Part 1: ESPACE-Algorithms

  2019influential citation
• Transitivity and Equivalence in Decidable Fragments of First-Order Logic: A Survey

  2019cites this paper
• The Complexity of Recursion in Modal Logic: First Steps ∗

  2019influential citation
• Lattice logic as a fragment of (2-sorted) residuated modal logic

  2018influential citation
• From KLM-style conditionals to defeasible modalities, and back

  2018cites this paper
• Two-variable logics with counting and semantic constraints

  2018cites this paper
• Completing the Picture: Complexity of Graded Modal Logics with Converse

  2018cites this paper
• Proof Search in Multi-Agent Dialogues for Modal Logic

  2018cites this paper
• On the Complexity of Graded Modal Logics with Converse

  2018cites this paper
• Complexity of Dynamic Epistemic Logic with Common Knowledge

  2018influential citation
• An Assumption-Based Approach for Solving the Minimal S5-Satisfiability Problem

  2018cites this paper
• MOLOSS, un solveur pour la satisfiabilité en logique modale

  2018cites this paper
• Expressivity within second-order transitive-closure logic

  2018cites this paper
• On the relationship between fuzzy description logics and many-valued modal logics

  2018cites this paper
• Complexity of finite-variable fragments of propositional modal logics of symmetric frames

  2018cites this paper
• Complexity of the interpretability logic IL

  2018cites this paper
• Algorithmic Contributions to Qualitative Constraint-based Spatial and Temporal Reasoning. (Contributions Algorithmiques au Raisonnement Spatial et Temporel basé sur des Contraintes Qualitatives)

  2017cites this paper
• A tableau prover for GL provability logic

  2017cites this paper
• Tableaux clausal para lógica modal

  2017cites this paper
• Decidability of order-based modal logics

  2017influential citation
• raccourci récursif pour CEGAR : Application au problème de satisfiabilité en logique modale K

  2017cites this paper