The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars

DOI10.1002/malq.19850312402zbMath0559.68063OpenAlexW2090146470MaRDI QIDQ5184422

Wojciech Buszkowski

Publication date: 1985

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

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

zbMATH Keywords

context-free grammarsLambek calculusweak equivalenceLambek categorial grammarsright-directional types

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05)

Related Items (14)

Gaifman's theorem on categorial grammars revisited ⋮ Extending Lambek grammars to basic categorial grammars ⋮ Algebraic structures in categorial grammar ⋮ Lambek Grammars with One Division Are Decidable in Polynomial Time ⋮ On translating context-free grammars into Lambek grammars ⋮ A restricted fragment of the Lambek calculus with iteration and intersection operations ⋮ Product-free Lambek calculus and context-free grammars ⋮ On translating Lambek grammars with one division into context-free grammars ⋮ Unidirectional Lambek grammars in polynomial time ⋮ Product-Free Lambek Calculus Is NP-Complete ⋮ The multiplicative-additive Lambek calculus with subexponential and bracket modalities ⋮ Recognition of derivability for the Lambek calculus with one division ⋮ Categorial dependency grammars ⋮ COMPLEXITY OF THE INFINITARY LAMBEK CALCULUS WITH KLEENE STAR

This page was built for publication: The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars