On the Recognizing Power of the Lambek Calculus with Brackets

2017/09/22 by Makoto Kanazawa, Kanazawa, Makoto
Computer Science · #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Mathematics, Computing, and Information Processing

paper · pdf · doi:10.48550/arxiv.1709.07695

openalex publication_date 2017/09/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Every language recognized by the Lambek calculus with brackets is context-free. This is shown by combining an observation by Jäger with an entirely straightforward adaptation of the method Pentus used for the original Lambek calculus. The case of the variant of the calculus allowing sequents with empty antecedents is slightly more complicated, requiring a restricted use of the multiplicative unit.

Citations

• The Mathematics of Sentence Structure

Related

• Eliminating the unit constant in the Lambek calculus with brackets
• Undecidability of the Lambek calculus with subexponential and bracket\n modalities
• Language Models for Some Extensions of the Lambek Calculus
• The Hidden Structural Rules of the Discontinuous Lambek Calculus
• Comparing and evaluating extended Lambek calculi