Constraints on Strong Generative Power

David Chiang

Abstract

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 theoretical and practical constraints on this problem. We then introduce a formalism which, under these constraints, maximally squeezes strong generative power out of context-free grammar. Finally, we generalize this result to formalisms beyond CFG.
BibTeX
@inproceedings{chiang2001constraints,
  author = {David Chiang},
  title = {{Constraints on Strong Generative Power}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2001},
  doi = {10.3115/1073012.1073030},
}
Figure