Product-free Lambek calculus and context-free grammars

DOI10.2307/2275553zbMath0882.68084OpenAlexW2115861484MaRDI QIDQ4358060

M. R. Pentus

Publication date: 4 February 1998

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275553

zbMATH Keywords

Lambek calculusChomsky conjecture

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (15)

On the recognizing power of the Lambek calculus with brackets ⋮ Algebraic structures in categorial grammar ⋮ A restricted fragment of the Lambek calculus with iteration and intersection operations ⋮ Kleene star, subexponentials without contraction, and infinite computations ⋮ S4 enriched multimodal categorial grammars are context-free ⋮ Parsing pregroup grammars and Lambek calculus using partial composition ⋮ Extended Lambek Calculi and First-Order Linear Logic ⋮ The emptiness of intersection problem for languages of k-valued categorial grammars (classical and Lambek) is undecidable ⋮ A Graph-Theoretic Approach to Sequent Derivability in the Lambek Calculus ⋮ Computing interpolants in implicational logics ⋮ Undecidability of the Lambek Calculus with a Relevant Modality ⋮ Pomset Logic ⋮ Powerful and NP-complete: hypergraph Lambek grammars ⋮ A note on the strong and weak generative powers of formal systems ⋮ The Pentus theorem for Lambek calculus with simple nonlogical axioms

Cites Work

• Language in action
• The Mathematics of Sentence Structure
• The Equivalence of Unidirectional Lambek Categorial Grammars and Context‐Free Grammars
• The equivalence of two concepts of categorial grammar

This page was built for publication: Product-free Lambek calculus and context-free grammars