An Efficient Parser for Bounded-Order Product-Free L ambek Categorial Grammar via Term Graph (2025)

Abstract: Lambek Categorial Grammar (LCG) parsing has been proved to be an NP-complete problem. However, in the bounded-order case, the complexity can be reduced to polynomial time. (CITATION) first introduced the term graph, a simple graphical representation for LCG parsing, but his algorithm for using it remained largely inscrutable. (CITATION) later proposed a polynomial algorithm for bounded-order LCG parsing based on cyclic linear logic, yet both approaches remain largely theoretical, with no open-source implementations available. In this work, we combine the term-graph representation with insights from cyclic linear logic to develop a novel parsing algorithm for bounded-order LCG. Furthermore, we release our parser as an open-source tool.

## introduction many studies have shown that transformer-based models such as large language models (llms) effectively capture certain aspects of syntactic structure @xcite @xcite . coming to terms with better representations of syntax could play a significant role in future llm research, contributing to advancements in areas such as mitigating hallucinations @xcite and reasoning @xcite . while most current research on syntax in nlp primarily focuses on context-free grammars (cfgs), categorial grammar (cg) deserves greater attention due to its unique advantages. unlike cfgs, which rely on a predefined set of production rules, cg is inherently lexicalized, meaning that all grammatical variations are captured within the lexicon itself. this allows syntactic processing to be driven directly by the lexical categories present in a sentence, rather than by a global rule set. additionally, cg strongly adheres to the principle of compositionality, as seen in montague grammar, ensuring that syntactic and semantic derivations align closely. this property makes semantic interpretation more transparent and directly extractable from syntax, and could be particularly beneficial for improving the still fraught understanding of the interplay between structure and meaning by the neural language modellling community. downstream tasks that leverage cg's syntactic representations to interpret sentence structure generally involve two stages: 1) supertagging @xcite @xcite , in which each word is assigned a syntactic category, and 2) sequent derivation @xcite @xcite , which organizes these categories into a coherent graphical structure that captures the sentence's grammatical composition. like other cg formalisms, lambek categorial grammar (lcg) parsing is amenable to this twostep process. a useful supertagger @xcite for lcg has already been proposed, allowing us to focus on the second sequent derivation step. but lcg sequent derivation has been proved to be np-complete @xcite . fortunately, it becomes polynomially solvable under a boundedorder assumption @xcite . this assumption is not only theoretically appealing but also empirically justified: in practical scenarios, the syntactic category order tends to remain low. for instance, in both the ccgbank @xcite and lcgbank corpus @xcite , the maximum order is only 5 @xcite , suggesting that boundedorder parsing is sufficient for most real-world applications. @xcite introduced the term graph, a simple graphical representation for lcg parsing. while it also proposed a polynomial-time algorithm with complexity o(n 3 ) for bounded-order parsing, that approach was never properly explicated and its proof of correctness is overly complex. pentus (2010) developed an alternative o(n 4 ) algo-1 rithm based on cyclic linear logic. in this work, we prove that the insights from cyclic linear logic also work for term graphs and use these to propose an efficient yet simple algorithm for bounded-order lcg parsing using term graphs that remains o(n 3 ). we release our parser and demonstrate our parser on lcgbank. 1 for expository purposes, only the recognition (yes/no) version of the algorithm is presented in the text. ## related work lcg was first introduced by @xcite , and since then, numerous variants have been developed, including ones that are product-free, using only / and \ as connectives, unidirectional, with only one of / or \, and lexicalized, that prohibit the derivation of the empty sequent, among others. the parsing complexity of lcg has been an ongoing topic of research, leading to the introduction of various frameworks aimed at addressing parsing challenges, such as proof nets @xcite , lc-graphs @xcite , term graphs @xcite , and cyclic linear logic @xcite . a key milestone in this line of work was the proof proposed by @xcite that derivability in the original lcg is np-complete. subsequent studies further demonstrated that derivability in the product-free @xcite and semidirectional @xcite lcgs is also np-complete, while unidirectional @xcite derivability has been shown to be solvable in polynomial time. despite this theoretical complexity, in practical settings, both the original lcg @xcite and its product-free @xcite variant have been proved to be polynomial-time solvable under reasonable constraints, making them more feasible for real-world applications. ## bounded order parser we combine the strengths of two existing frameworks and propose a simple and easily understandable algorithm based on term graphs. our approach retains the cubic-time complexity for both l * and l, making it both efficient and practical. in this section, we first introduce the naive chart parser and our proposed algorithm, followed by a s1-s2+ s5-np3-np4+ s8+ s5-np6+ np7-s8+ s2+ s5-np3-np4+ np6+ np7-s8+ s1-g2,5 g6,7 adjoin result g2,7 figure 7: an example of naive adjoin operation. ## conclusion in this work, we presented a practical and efficient parser for bounded-order, product-free lambek categorial grammar, based on a refined term-graph framework. inspired in part by the theoretical insights from cyclic linear logic @xcite , our algorithm achieves the same asymptotic complexity as fowler (2007)'s chart-based parser at o(n 3 ), while offering significantly improved simplicity and implementability. in contrast, pentus's original method incurs a higher o(n 4 ) complexity due to the need for additional structural tracking in cyclic linear logic. a key innovation in our parser lies in the use of boundary-only representations, which eliminate the need to track internal nodes and allow for aggressive graph simplification without sacrificing correctness. our method unifies term graph derivability conditions with a lightweight dynamic programming architecture, resulting in a parser that is both fast and easy to understand. crucially, we provide the first open-source parser that is boundedorder polynomial, enabling further research and application of lambek grammar in modern nlp workflows.