Introduction
In the field of computational linguistics, Lambek Categorial Grammar (LCG) provides an elegant logical framework for syntax. By treating grammatical categories as types and parsing as a form of theorem proving, LCG allows for a direct mapping between syntax and semantics. However, the standard Lambek Calculus ($L$) is largely restricted to "peripheral extraction," where gaps in a sentence must occur at the edges of phrases.
To address more complex linguistic phenomena, researchers introduced Semidirectional Lambek Grammar (SDL). SDL adds flexibility by allowing missing elements to be abstracted from any position within a sequence. While this increases linguistic coverage, it raises a critical question: what is the computational cost of this added power? This paper demonstrates that the parsing problem for SDL is NP-complete.
Linguistic Motivation: Non-Peripheral Gaps
Natural languages frequently feature "non-peripheral" gaps. Consider the phrase "the book which Bill misses [gap] today." In standard Lambek systems, modeling such a gap is difficult because the missing noun phrase ($np$) is buried within the sentence structure rather than being at the start or end.
As shown in the figure above, SDL uses non-directional rules to handle these cases. The category for "which" is $(np\backslash np)/(s/np)$, where $s/np$ represents a sentence missing an $np$ anywhere. This flexibility allows the grammar to capture a wider range of human language structures, such as the non-context-free language $a^n b^n c^n$.
Complexity and the 3-Partition Reduction
The core contribution of this work is the proof that SDL parsing is NP-hard. The author achieves this through a reduction from the 3-Partition problem, a classic NP-complete task where a set of $3m$ integers must be divided into $m$ groups of three that sum to a target value $N$.
The reduction involves constructing a specific SDL grammar where a string is considered grammatical if and only if the corresponding 3-Partition problem has a solution. This mapping relies on the "Count Invariant" property of Lambek systems—the requirement that positive and negative occurrences of primitive types must balance out.
The "Permutation Trap" is central to this proof: the ability of formulas to move or "permute" during the abstraction process allows the grammar to simulate the bin-packing behavior of 3-Partition. Because the logic is resource-conscious, types act like tokens that must be "spent" precisely to complete the proof, mirroring the way integers are allocated to bins in the partition problem.
Key Insights and Implications
- Generative Power vs. Complexity: The jump in power from context-free grammars to SDL moves parsing complexity from polynomial time ($O(n^3)$) to NP-complete.
- Grammar Engineering: The results suggest a practical motto for grammar designers: avoid the accumulation of unbounded dependencies. Allowing too many unresolved gaps simultaneously can lead to an exponential search space for the parser.
- Worst-Case vs. Average-Case: The author acknowledges that while the worst-case complexity is high, the NP-complete instances constructed in the proof are highly artificial. This suggests that "normal" natural language sentences may still be efficiently parsable in practice.
Conclusion
This research establishes a fundamental upper bound on the complexity of flexible categorial grammars. By proving that SDL parsing is NP-complete, the author highlights the delicate balance between linguistic expressivity and computational efficiency, providing a cautionary tale for those designing highly flexible grammatical formalisms.
Summary updated