Lambek Grammars with One Division Are Decidable in Polynomial Time

DOI10.1007/978-3-540-79709-8_28zbMath1142.68415OpenAlexW1488801660MaRDI QIDQ3503645

Yury Savateev

Publication date: 5 June 2008

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-79709-8_28

Mathematics Subject Classification ID

Logic of natural languages (03B65) Decidability of theories and sets of sentences (03B25) Grammars and rewriting systems (68Q42)

Related Items (5)

On Lambek’s Restriction in the Presence of Exponential Modalities ⋮ Product-free Lambek calculus is NP-complete ⋮ On translating Lambek grammars with one division into context-free grammars ⋮ Product-Free Lambek Calculus Is NP-Complete ⋮ Undecidability of the Lambek Calculus with a Relevant Modality

Cites Work

• Unnamed Item
• 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: Lambek Grammars with One Division Are Decidable in Polynomial Time