An \(\mathsf{AC}^{1}\)-complete model checking problem for intuitionistic logic
From MaRDI portal
Publication:475340
DOI10.1007/s00037-013-0062-zzbMathNoneOpenAlexW2072923153MaRDI QIDQ475340
Publication date: 26 November 2014
Published in: Computational Complexity (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00037-013-0062-z
Heyting algebras (lattice-theoretic aspects) (06D20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Subsystems of classical logic (including intuitionistic logic) (03B20)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Semantical investigations in Heyting's intuitionistic logic
- On uniform circuit complexity
- Intuitionistic propositional logic is polynomial-space complete
- On the polynomial-space completeness of intuitionistic propositional logic
- Circuits, matrices, and nonassociative computation
- Intuitionism. An introduction. 3rd revised ed
- On closed elements in closure algebras
- Intuitionistic implication makes model checking hard
- Intuitionistic implication without disjunction
- The model checking problem for propositional intuitionistic logic with one variable is AC 1 -complete
- The Complexity of Model Checking for Intuitionistic Logics and Their Modal Companions
- A taxonomy of problems with fast parallel algorithms
- On formulas of one variable in intuitionistic propositional calculus
- Alternation
- An Optimal Parallel Algorithm for Formula Evaluation
- Implicational formulas in intuitionistic logic
- On the Tape Complexity of Deterministic Context-Free Languages
- There are infinitely many Diodorean modal functions
- Modal Logics Between S 4 and S 5
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Logic and structure
