Paper: Computational Structure Of Generative Phonology And Its Relation To Language Comprehension

ACL ID P90-1030
Title Computational Structure Of Generative Phonology And Its Relation To Language Comprehension
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1990
Authors

We analyse the computational complexity of phonological models as they have developed over the past twenty years. The major results ate that generation and recognition are undecidable for segmental models, and that recognition is NP- hard for that portion of segmental phonology sub- sumed by modern autosegmental models. Formal restrictions are evaluated.