Unidirectional Lambek grammars in polynomial time

DOI10.1007/s00224-009-9208-4zbMath1205.68185OpenAlexW2024247183MaRDI QIDQ987373

Yury Savateev

Publication date: 13 August 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-009-9208-4

zbMATH Keywords

complexityLambek calculusunidirectional Lambek grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics) (03B47)

Related Items (4)

Kleene star, subexponentials without contraction, and infinite computations ⋮ Pregroup grammars with letter promotions: complexity and context-freeness ⋮ The multiplicative-additive Lambek calculus with subexponential and bracket modalities ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Lambek calculus is NP-complete
• Recognition of derivability for the Lambek calculus with one division
• The Mathematics of Sentence Structure
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars

This page was built for publication: Unidirectional Lambek grammars in polynomial time