IMPLICATIONAL RELEVANCE LOGIC IS 2-EXPTIME-COMPLETE

DOI10.1017/jsl.2015.7zbMath1370.03029arXiv1402.0705OpenAlexW2470191449MaRDI QIDQ3188334

Sylvain Schmitz

Publication date: 19 August 2016

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.0705

zbMATH Keywords

complexityrelevance logicfocusing proofsbranching vector addition systems (BVASS)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47)

Related Items

On the decision problem for MELL, Constructive decision via redundancy-free proof-search, Unnamed Item, A Logical Autobiography

Cites Work

• Unnamed Item
• Decision problems for propositional linear logic
• Intuitionistic propositional logic is polynomial-space complete
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The covering and boundedness problems for branching vector addition systems
• Minimalist Grammars in the Light of Logic
• Logic Programming with Focusing Proofs in Linear Logic
• Ticket Entailment is decidable