Paper: Constraints On Strong Generative Power

ACL ID P01-1018
Title Constraints On Strong Generative Power
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2001
  • David Chiang (University of Pennsylvania, Philadelphia PA)

We consider the question “How much strong generative power can be squeezed out of a formal system without increasing its weak generative power?” and propose some theoret- ical and practical constraints on this problem. We then introduce a formal- ism which, under these constraints, maximally squeezes strong generative power out of context-free grammar. Finally, we generalize this result to formalisms beyond CFG.