Abstract
We analyze the complexity of the problem of determining whether a set of phonemes forms a natural class and, if so, that of finding the minimal feature specification for the class. A standard assumption in phonology is that finding a minimal feature specification is an automatic part of acquisition and generalization. We find that the natural class decision problem is tractable (i.e. is in P), while the minimization problem is not; the decision version of the problem which determines whether a natural class can be defined with k features or less is NP-complete. We also show that, empirically, a greedy algorithm for finding minimal feature specifications will sometimes fail, and thus cannot be assumed to be the basis for human performance in solving the problem.- Anthology ID:
- N18-2086
- Volume:
- Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)
- Month:
- June
- Year:
- 2018
- Address:
- New Orleans, Louisiana
- Venue:
- NAACL
- SIG:
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 542–547
- Language:
- URL:
- https://aclanthology.org/N18-2086
- DOI:
- 10.18653/v1/N18-2086
- Cite (ACL):
- Hubie Chen and Mans Hulden. 2018. The Computational Complexity of Distinctive Feature Minimization in Phonology. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers), pages 542–547, New Orleans, Louisiana. Association for Computational Linguistics.
- Cite (Informal):
- The Computational Complexity of Distinctive Feature Minimization in Phonology (Chen & Hulden, NAACL 2018)
- PDF:
- https://preview.aclanthology.org/ingestion-script-update/N18-2086.pdf