Abstract
Traditional Categorial Grammar (CG) relies on a propositional logic framework that often struggles with the complexities of natural language, such as discontinuous constituents and non-peripheral extraction. This paper proposes a transition from propositional to first-order logic, redefining syntactic types as definite clauses. By representing string positions as variables and utilizing internal implications, this framework unifies categorial syntax with logic programming, providing a robust mechanism for parsing as theorem proving while addressing long-standing issues of spurious ambiguity and decidability.
Introduction
In the landscape of formal linguistics, Categorial Grammar (CG) stands out as a highly lexicalized approach. In CG, the syntactic behavior of a word is entirely determined by the type assigned to it in the lexicon. Traditionally, these types are expressed using directional slashes—the forward slash / and backward slash \—which dictate whether a word requires an argument to its right or left.
While elegant, this "strict adjacency" requirement creates significant hurdles when dealing with discontinuous constituents. These occur when related linguistic elements are separated by intervening material, or when a "gap" (an extraction site) appears in the middle of a sentence rather than at the periphery. For instance, in relative clauses like "the book which I shall put [gap] on the table," the relative pronoun refers to an object whose logical position is nested within the verb phrase. Standard CG often requires complex, redundant type assignments to account for every possible gap location, leading to a lack of generalization.
Methodology: First-Order Categorial Grammar
Remo Pareschi’s work addresses these limitations by shifting the logical foundation of CG from propositional logic to first-order logic. In this framework, syntactic types are encoded as definite clauses, similar to those found in Prolog.
Adjacency as Variable Sharing
The most significant shift is the treatment of string positions. Rather than relying on directional slashes to imply order, the grammar represents string positions as integer variables. Adjacency is no longer a structural constraint of the logic itself but is instead enforced through the sharing of these integer indices across sub-formulas. For example, a constituent spanning from position $i$ to $k$ might be composed of sub-constituents spanning $i$ to $j$ and $j$ to $k$. This allows for the description of "virtual" constituents—elements that occupy zero length in the string but fulfill a specific logical role.
Internal Implications and Higher-Order Functions
Standard Horn logic, which forms the basis of traditional logic programming, is insufficient for the "higher-order" functions required by natural language (such as the behavior of relative pronouns). To solve this, Pareschi adopts an extension of Horn logic that permits internal implications within the body of a clause. This allows the parser to "hypothesize" the existence of a missing constituent (like a noun phrase) to complete a logical proof.
Parsing as Theorem Proving
Under this paradigm, the act of parsing a sentence is equivalent to proving a theorem. A string is deemed grammatical if the logic can derive a sentence type $S(0, n)$—representing a complete sentence from the start (0) to the end ($n$) of the input—based on the types assigned to the individual words in the lexicon.
Key Insights and Logical Constraints
Decidability and Spurious Ambiguity
One common critique of logic-based grammars is the risk of undecidability or computational explosion. Pareschi notes that while general intuitionistic logic is undecidable, natural language parsing can be constrained. By removing the "Contraction" rule (the ability to use the same hypothesis multiple times), the parsing process becomes guaranteed to terminate. Furthermore, this theorem-proving approach is "expectation-driven," which avoids the "spurious ambiguity" found in systems like Combinatory Categorial Grammar (CCG), where multiple equivalent derivation trees are generated for a single sentence.
The Lambda Calculus Filter
A potential issue in intuitionistic logic is the "Thinning" rule, which allows the system to ignore a hypothesized gap, potentially accepting ungrammatical strings. To counter this, the author suggests encoding proofs as Lambda terms. If a proof results in "vacuous abstraction"—where a variable representing a hypothesized constituent is never actually used—the result can be filtered out as ungrammatical.
Conclusion
By redefining Categorial Grammar through the lens of first-order definite clauses, this paper provides a unified roadmap for implementing sophisticated linguistic theories within logic programming environments like Lambda-Prolog. The framework successfully handles non-peripheral extraction and discontinuous constituents without the need for the redundant type assignments that plague traditional CG. While future work remains regarding the efficiency of large-scale implementations and the handling of languages with entirely free word order, this approach represents a significant step toward a computationally sound and linguistically flexible theory of syntax.
Summary updated