Lambek calculus is NP-complete

DOI10.1016/J.TCS.2006.03.018MaRDI QIDQ2500488zbMATHOpenAlexFDO

Authors 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

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)

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

Cites work

• scientific article; zbMATH DE number 4099289 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1222927 (Why is no real title available?)
• scientific article; zbMATH DE number 1341472 (Why is no real title available?)
• scientific article; zbMATH DE number 976409 (Why is no real title available?)
• scientific article; zbMATH DE number 1114352 (Why is no real title available?)
• scientific article; zbMATH DE number 786489 (Why is no real title available?)
• scientific article; zbMATH DE number 1406803 (Why is no real title available?)
• Language in action. Categories, lambdas and dynamic logic
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• Phase semantics and sequent calculus for pure noncommutative classical linear propositional logic
• Polynomial equivalence among systems LLNC, LLNC\(_a\) and LLNC\(_0\)
• Proving theorems of the second order Lambek calculus in polynomial time
• Quantales and (noncommutative) linear logic
• The Mathematics of Sentence Structure

Cited in

(51)

• On Lambek's restriction in the presence of exponential modalities
• LaserTank is NP-Complete
• One-Sided Sequent Systems for Nonassociative Bilinear Logic: Cut Elimination and Complexity
• Unidirectional Lambek grammars in polynomial time
• Proving theorems of the second order Lambek calculus in polynomial time
• Powerful and NP-complete: hypergraph Lambek grammars
• On involutive nonassociative Lambek calculus
• The multiplicative-additive Lambek calculus with subexponential and bracket modalities
• Bracket induction for Lambek calculus with bracket modalities
• The product-free Lambek-Grishin calculus is NP-complete
• System BV is NP-complete
• Complexity of the Lambek calculus and its fragments
• Subexponentials in non-commutative linear logic
• Product-free Lambek calculus is NP-complete
• Towards NP-P via proof complexity and search
• Hypergraph Lambek grammars
• Models for the Lambek calculus
• Logical foundations for hybrid type-logical grammars
• Lambek calculus with a unit and one division
• Type logics and pregroups
• Kleene star, subexponentials without contraction, and infinite computations
• Proof nets for the displacement calculus
• An application of proof-nets to the study of fragments of the Lambek calculus
• Categorial grammars and their logics
• Term graphs and the NP-completeness of the product-free Lambek calculus
• Non-associative, non-commutative multi-modal linear logic
• Algebraic structures in categorial grammar
• Product-Free Lambek Calculus Is NP-Complete
• Complexity of the infinitary Lambek calculus with Kleene star
• Direct encodings of NP-complete problems into Horn sequents of multiplicative linear logic
• The complexity of Horn fragments of linear logic
• Involutive nonassociative Lambek calculus: sequent systems and complexity
• Pregroup grammars with letter promotions: complexity and context-freeness
• Good types are useful for learning
• Complexity of the universal theory of bounded residuated distributive lattice-ordered groupoids
• The finite model property for BCI and related systems
• Recognition of derivability for the Lambek calculus with one division
• Lambek calculus and its relational semantics: Completeness and incompleteness
• Trivalent logics arising from L-models for the Lambek calculus with constants
• Complexity of Lambek calculi with modalities and of total derivability in grammars
• Infinitary action logic: complexity, models and grammars
• Infinitary action logic with exponentiation
• scientific article; zbMATH DE number 7204441 (Why is no real title available?)
• Extensions of Lambek calculi
• On translating Lambek grammars with one division into context-free grammars
• Current trends in substructural logics
• Undecidability of the Lambek calculus with a relevant modality
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• The monotone Lambek calculus is NP-complete
• Pomset logic. The other approach to noncommutativity in logic
• Extended Lambek calculi and first-order linear logic

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)