1993 · 82 citations · 5 references
Language StudiesComputer ScienceLinguisticsComputational LinguisticsNatural Language ProcessingSyntaxContext-free LanguagesParsingSyntactic ComplexitySyntactic ParsingSyntax ParsingWord OrderConstraintsContext-free Grammar ParsingContext-free GrammarsFree Word OrderGrammar FormalismsLanguage ParsingParsing With Constraint-based GrammarsSimple Sentences
There is a need to develop a suitable computational grammar formalism for free word order languages for two reasons: First, a suitably designed formalism is likely to be more efficient. Second, such a formalism is also likely to be linguistically more elegant and satisfying. In this paper, we describe such a formalism, called the Paninian framework, that has been successfully applied to Indian languages.This paper shows that the Paninian framework applied to modern Indian languages gives an elegant account of the relation between surface form (vibhakti) and semantic (karaka) roles. The mapping is elegant and compact. The same basic account also explains active-passives and complex sentences. This suggests that the solution is not just adhoc but has a deeper underlying unity.A constraint based parser is described for the framework. The constraints problem reduces to bipartite graph matching problem because of the nature of constraints. Efficient solutions are known for these problems.It is interesting to observe that such a parser (designed for free word order languages) compares well in asymptotic time complexity with the parser for context free grammars (CFGs) which are basically designed for positional languages.
5
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
The Hungarian method for the assignment problem
H. W. Kuhn · Naval Research Logistics (NRL) · 2004 · 1.3K citations · Full text
Parsing a free-word order language
Michael B. Kashket · 1986 · 12 citations · Full text