Unidirectional Lambek grammars in polynomial time

DOI10.1007/S00224-009-9208-4MaRDI QIDQ987373zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Lambek Grammars with One Division Are Decidable in Polynomial Time
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• On the complexity of nonassociative Lambek calculus with unit
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars
• scientific article; zbMATH DE number 7204441

Cites work

• scientific article; zbMATH DE number 1341472 (Why is no real title available?)
• Lambek calculus is NP-complete
• Non‐associative Lambek Categorial Grammar in Polynomial Time
• Recognition of derivability for the Lambek calculus with one division
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars
• The Mathematics of Sentence Structure

Cited in

(10)

• Pregroup grammars with letter promotions: complexity and context-freeness
• A direct complement construction for LR(1) grammars
• The multiplicative-additive Lambek calculus with subexponential and bracket modalities
• Kleene star, subexponentials without contraction, and infinite computations
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• A polynomial time algorithm for parsing with the bounded order Lambek calculus
• An analysis of Lambek's production machines
• scientific article; zbMATH DE number 7204441 (Why is no real title available?)
• On translating Lambek grammars with one division into context-free grammars
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars

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

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