The Computational Complexity of Distinctive Feature Minimization in Phonology

Hubie Chen, Mans Hulden


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
Bibkey:
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)
Copy Citation:
PDF:
https://preview.aclanthology.org/ingestion-script-update/N18-2086.pdf