On Panini and the Generative Capacity of Contextualized Replacement Systems
Gerald M. Penn, Paul Kiparsky · International Conference on Computational Linguistics · 2012
This paper re-examines the widely held belief that the formalism underlying the rule system propounded by the ancient Indian grammarian, Pān. ini (ca. 450–350 BCE), either anticipates or converges upon the same expressive power found in finite state control systems or the context-free languages that are used in programming language theory and computational linguistics. While there is indeed a striking but cosmetic resemblance to the contextualized rewriting systems used by modern morphologists and phonologists, a subtle difference in how rules are prevented from applying cyclically leads to a massive difference in generative capacity. The formalism behind Pān. inian grammar, in fact, generates string languages not even contained within any of the multiple-component tree-adjoining languages, MCTAL(k), for any k. There is ample evidence, nevertheless, that Pān. ini’s grammar itself judiciously avoided the potential pitfalls of this unconstrained formalism to articulate a large-coverage, but seemingly very tractable grammar of the Sanskrit language.