Lambek calculus is NP-complete

DOI10.1016/J.TCS.2006.03.018zbMATH Open1104.03013OpenAlexW1978223872MaRDI QIDQ2500488FDOQ2500488

Mati 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

Recommendations

• Product-free Lambek calculus is NP-complete
• Product-Free Lambek Calculus Is NP-Complete
• The monotone Lambek calculus is NP-complete
• Complexity of the Lambek calculus and its fragments
• LC graphs for the Lambek calculus with product
• The product-free Lambek-Grishin calculus is NP-complete
• An application of proof-nets to the study of fragments of the Lambek calculus
• The complexity of Horn fragments of linear logic
• scientific article; zbMATH DE number 1114352
• The Lambek-Grishin Calculus Is NP-Complete

zbMATH Keywords

complexityLambek calculusderivabilitynoncommutative 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)

Cites Work

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

Cited In (44)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500488)