Non‐associative Lambek Categorial Grammar in Polynomial Time

DOI10.1002/MALQ.19950410405zbMath0837.03033OpenAlexW2031903051MaRDI QIDQ4857860

Erik Aarts, Kees Trautwein

Publication date: 13 May 1996

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19950410405

zbMATH Keywords

polynomial timecontext-free grammarcategorial grammarcomplexity of recognitionaxiomatization of non-associative Lambek calculus

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Cut-elimination and normal-form theorems (03F05) Grammars and rewriting systems (68Q42) Complexity of proofs (03F20)

Related Items (10)

\(k\)-valued non-associative Lambek grammars are learnable from generalized functor-argument structures ⋮ Lambek Grammars with One Division Are Decidable in Polynomial Time ⋮ Product-free Lambek calculus is NP-complete ⋮ Complexity of the universal theory of residuated ordered groupoids ⋮ k-Valued Non-Associative Lambek Grammars are Learnable from Function-Argument Structures ⋮ Lambek calculus is NP-complete ⋮ Unidirectional Lambek grammars in polynomial time ⋮ Product-Free Lambek Calculus Is NP-Complete ⋮ Unnamed Item ⋮ Non-associative, non-commutative multi-modal linear logic

This page was built for publication: Non‐associative Lambek Categorial Grammar in Polynomial Time