Abstract
Traditional computational grammars often struggle with free-word-order languages because they rely on positional context-free grammars (CFGs). This paper presents a computational framework based on ancient Paninian grammar, which prioritizes syntactico-semantic relations (karakas) over word position. By mapping surface markers (vibhaktis) to these relations, the parsing problem is reduced to a bipartite graph matching task, achieving a polynomial time complexity of $O(n^3)$.
Introduction
Most established computational linguistic models are designed for positional languages like English, where word order determines grammatical roles (e.g., "The dog bit the man"). However, Indian languages and many others exhibit free word order, where roles are instead signaled by suffixes or post-positions, known as vibhaktis. Applying positional parsers to these languages is linguistically unnatural and computationally inefficient.
The authors propose a formalism that is both linguistically grounded in the Paninian tradition and optimized for modern computational efficiency. This framework shifts the focus from "where a word is" to "what role a word plays" relative to a verb.
Methodology: The Paninian Framework
The proposed system follows a multi-stage pipeline to transform raw text into a structured relational graph:
- Morphological Analysis & Local Word Grouping: Words are first clustered into noun and verb groups. A noun and its associated post-position (e.g., "Ram -ko") are treated as a single unit at the vibhakti level.
- Karaka Mapping: The karaka serves as a mediator between the surface vibhakti and the underlying semantics. Each verb has a "demand chart" specifying which karakas it requires and which vibhaktis can satisfy them.
- TAM-Based Transformations: A verb's requirements are not static. Based on its Tense, Aspect, and Modality (TAM) label, the framework applies transformation rules to the verb's karaka chart. This allows a single lexical entry to handle active, passive, and causative forms dynamically.
- Constraint-Based Parsing as Graph Matching: The parser treats verbs as "demand groups" and nouns as "source groups." The problem of assigning roles is modeled as a bipartite graph. Edges are drawn between nouns and verbs if the noun's vibhakti matches a requirement in the verb's transformed karaka chart. The parser then finds a valid matching that satisfies all mandatory constraints.
Key Insights and Linguistic Formalism
A primary distinction in this framework is the definition of karakas versus Western "theta roles." While theta roles are purely semantic (e.g., Agent, Patient), karakas are syntactico-semantic. For instance, the karta karaka is defined as the "most independent" participant. In the sentence "The key opens the lock," the "key" functions as the karta, even though it is semantically an instrument.
By decoupling karaka assignment from word sense disambiguation, the framework keeps the parsing problem within polynomial time ($P$). This separation of concerns prevents the exponential search space explosion common in parsers that attempt to solve syntax and semantics simultaneously.
Computational Complexity and Results
The reduction of parsing to bipartite matching allows the use of efficient algorithms:
- Complexity: The parser achieves an asymptotic time complexity of $O(n^3)$ using standard augmenting path algorithms, or $O(\sqrt{V}E)$ using the Hopcroft-Karp algorithm, where $n$ is the number of word groups.
- Unified Account: The framework provides a consistent explanation for complex linguistic phenomena, including active-passive voice, control structures (shared participants in complex sentences), and participial adjectives.
- Practical Implementation: The system was successfully integrated into a machine translation system for Indian languages, demonstrating its viability for real-world applications.
Limitations and Future Directions
While efficient, the current model assumes that word groups can be uniquely identified before the core parsing stage. Future iterations would need to handle structural ambiguities where a word group might simultaneously act as a source and a demand group. Additionally, while the authors suggest that "position" in English could be treated as a "generalized vibhakti," the framework's primary strength remains in languages with rich morphology and flexible syntax.
Summary updated