Lambek calculus is NP-complete

DOI10.1016/J.TCS.2006.03.018zbMath1104.03013OpenAlexW1978223872MaRDI QIDQ2500488

M. R. Pentus

Publication date: 16 August 2006

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

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

zbMATH Keywords

complexityderivabilityLambek calculusnoncommutative linear logiccyclic linear logicmultiplicative fragments

Mathematics Subject Classification ID

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) Proof-theoretic aspects of linear logic and other substructural logics (03F52)

Related Items (40)

Current trends in substructural logics ⋮ On Lambek’s Restriction in the Presence of Exponential Modalities ⋮ Logical foundations for hybrid type-logical grammars ⋮ Models for the Lambek calculus ⋮ Algebraic structures in categorial grammar ⋮ Trivalent logics arising from L-models for the Lambek calculus with constants ⋮ Lambek Grammars with One Division Are Decidable in Polynomial Time ⋮ Product-free Lambek calculus is NP-complete ⋮ Towards NP-P via proof complexity and search ⋮ On involutive nonassociative Lambek calculus ⋮ Bracket induction for Lambek calculus with bracket modalities ⋮ Involutive Nonassociative Lambek Calculus: Sequent Systems and Complexity ⋮ Categorial Grammars and Their Logics ⋮ Infinitary action logic: complexity, models and grammars ⋮ Kleene star, subexponentials without contraction, and infinite computations ⋮ Type logics and pregroups ⋮ Good Types Are Useful for Learning ⋮ On translating Lambek grammars with one division into context-free grammars ⋮ Extended Lambek Calculi and First-Order Linear Logic ⋮ Pregroup grammars with letter promotions: complexity and context-freeness ⋮ Unidirectional Lambek grammars in polynomial time ⋮ Product-Free Lambek Calculus Is NP-Complete ⋮ The multiplicative-additive Lambek calculus with subexponential and bracket modalities ⋮ Recognition of derivability for the Lambek calculus with one division ⋮ Unnamed Item ⋮ Complexity of Lambek calculi with modalities and of total derivability in grammars ⋮ Infinitary action logic with exponentiation ⋮ Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids ⋮ Undecidability of the Lambek Calculus with a Relevant Modality ⋮ Proof Nets for the Displacement Calculus ⋮ Subexponentials in non-commutative linear logic ⋮ Hypergraph Lambek grammars ⋮ The finite model property for BCI and related systems ⋮ One-Sided Sequent Systems for Nonassociative Bilinear Logic: Cut Elimination and Complexity ⋮ Extensions of Lambek Calculi ⋮ Pomset Logic ⋮ Non-associative, non-commutative multi-modal linear logic ⋮ Lambek calculus and its relational semantics: Completeness and incompleteness ⋮ COMPLEXITY OF THE INFINITARY LAMBEK CALCULUS WITH KLEENE STAR ⋮ Powerful and NP-complete: hypergraph Lambek grammars

Cites Work

• Language in action. Categories, lambdas and dynamic logic
• Proving theorems of the second order Lambek calculus in polynomial time
• Polynomial equivalence among systems LLNC, LLNC\(_a\) and LLNC\(_0\)
• The Mathematics of Sentence Structure
• Quantales and (noncommutative) linear logic
• Phase semantics and sequent calculus for pure noncommutative classical linear propositional logic
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lambek calculus is NP-complete