On the complexity of nonassociative Lambek calculus with unit

DOI10.1007/s11225-009-9205-2zbMath1182.03041OpenAlexW2061837253MaRDI QIDQ1035836

Maria Bulińska

Publication date: 4 November 2009

Published in: Studia Logica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11225-009-9205-2

zbMATH Keywords

context-free grammarLambek grammarnonassociative Lambek calculusPTIME decidability

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Grammars and rewriting systems (68Q42) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47)

Related Items (3)

Complexity of the universal theory of residuated ordered groupoids ⋮ Disjunction property and complexity of substructural logics ⋮ Non-associative, non-commutative multi-modal linear logic

Cites Work

• Unnamed Item
• Unnamed Item
• The Pentus theorem for Lambek calculus with simple nonlogical axioms
• Residuation, structural rules and context freeness
• Classical non-associative Lambek calculus
• The Mathematics of Sentence Structure
• The equivalence of Nonassociative Lambek Categorial Grammars and Context-Free Grammars

This page was built for publication: On the complexity of nonassociative Lambek calculus with unit