Recognition of derivability for the Lambek calculus with one division

DOI10.3103/S0027132209020077zbMath1304.03055OpenAlexW2147759643MaRDI QIDQ2513061

Yu. V. Savateev

Publication date: 2 February 2015

Published in: Moscow University Mathematics Bulletin (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3103/s0027132209020077

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47)

Related Items (7)

The atomic theory of left division of two-sided ideals of semirings with unit ⋮ Proof nets for the Lambek calculus with one division and a negative-polarity modality for weakening ⋮ Lambek Grammars with One Division Are Decidable in Polynomial Time ⋮ Complexity of the Lambek calculus with one division and a negative-polarity modality for weakening ⋮ On translating Lambek grammars with one division into context-free grammars ⋮ Unidirectional Lambek grammars in polynomial time ⋮ Complexity of Lambek calculi with modalities and of total derivability in grammars

Cites Work

• Lambek calculus is NP-complete
• The Mathematics of Sentence Structure
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars

This page was built for publication: Recognition of derivability for the Lambek calculus with one division