Disjunction property and complexity of substructural logics

DOI10.1016/j.tcs.2011.04.004zbMath1231.03021OpenAlexW1983988429MaRDI QIDQ549720

Kazushige Terui, Rostislav Horčík

Publication date: 18 July 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.04.004

zbMATH Keywords

computational complexitysubstructural logicsdisjunction property

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) 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 (12)

Integrally closed residuated lattices ⋮ Proof search and co-NP completeness for many-valued logics ⋮ Complexity of some language fragments of fuzzy logics ⋮ Varieties generated by standard BL-algebras ⋮ From cut-free calculi to automated deduction: the case of bounded contraction ⋮ BOUNDED-ANALYTIC SEQUENT CALCULI AND EMBEDDINGS FOR HYPERSEQUENT LOGICS ⋮ Multi-Sorted Residuation ⋮ Proof complexity of substructural logics ⋮ Some Syntactic Interpretations in Different Systems of Full Lambek Calculus ⋮ A Generalization of Maksimova’s Criterion for the Disjunction Property ⋮ Conuclear images of substructural logics ⋮ Extensions of Lambek Calculi

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algebraic proof theory for substructural logics: cut-elimination and completions
• Linear logic
• Complexity issues in Basic Logic
• Residuated lattices. An algebraic glimpse at substructural logics
• On the complexity of nonassociative Lambek calculus with unit
• Decision problems for propositional linear logic
• Intuitionistic propositional logic is polynomial-space complete
• Metamathematics of fuzzy logic
• On the polynomial-space completeness of intuitionistic propositional logic
• Handbook of philosophical logic. Vol. 6
• Classical non-associative Lambek calculus
• An algebraic approach to the disjunction property of substructural logics
• Algebraization, parametrized local deduction theorem and interpolation for substructural logics over FL
• Expanding the Realm of Systematic Proof Theory
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The Logic of Bunched Implications

This page was built for publication: Disjunction property and complexity of substructural logics