<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="chen-hulden-2018-computational">
    <titleInfo>
        <title>The Computational Complexity of Distinctive Feature Minimization in Phonology</title>
    </titleInfo>
    <name type="personal">
        <namePart type="given">Hubie</namePart>
        <namePart type="family">Chen</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <name type="personal">
        <namePart type="given">Mans</namePart>
        <namePart type="family">Hulden</namePart>
        <role>
            <roleTerm authority="marcrelator" type="text">author</roleTerm>
        </role>
    </name>
    <originInfo>
        <dateIssued>2018-06</dateIssued>
    </originInfo>
    <typeOfResource>text</typeOfResource>
    <relatedItem type="host">
        <titleInfo>
            <title>Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)</title>
        </titleInfo>
        <name type="personal">
            <namePart type="given">Marilyn</namePart>
            <namePart type="family">Walker</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Heng</namePart>
            <namePart type="family">Ji</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <name type="personal">
            <namePart type="given">Amanda</namePart>
            <namePart type="family">Stent</namePart>
            <role>
                <roleTerm authority="marcrelator" type="text">editor</roleTerm>
            </role>
        </name>
        <originInfo>
            <publisher>Association for Computational Linguistics</publisher>
            <place>
                <placeTerm type="text">New Orleans, Louisiana</placeTerm>
            </place>
        </originInfo>
        <genre authority="marcgt">conference publication</genre>
    </relatedItem>
    <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.</abstract>
    <identifier type="citekey">chen-hulden-2018-computational</identifier>
    <identifier type="doi">10.18653/v1/N18-2086</identifier>
    <location>
        <url>https://aclanthology.org/N18-2086</url>
    </location>
    <part>
        <date>2018-06</date>
        <extent unit="page">
            <start>542</start>
            <end>547</end>
        </extent>
    </part>
</mods>
</modsCollection>

%0 Conference Proceedings
%T The Computational Complexity of Distinctive Feature Minimization in Phonology
%A Chen, Hubie
%A Hulden, Mans
%Y Walker, Marilyn
%Y Ji, Heng
%Y Stent, Amanda
%S Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 2 (Short Papers)
%D 2018
%8 June
%I Association for Computational Linguistics
%C New Orleans, Louisiana
%F chen-hulden-2018-computational
%X 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.
%R 10.18653/v1/N18-2086
%U https://aclanthology.org/N18-2086
%U https://doi.org/10.18653/v1/N18-2086
%P 542-547

Markdown (Informal)

[The Computational Complexity of Distinctive Feature Minimization in Phonology](https://aclanthology.org/N18-2086) (Chen & Hulden, NAACL 2018)

• The Computational Complexity of Distinctive Feature Minimization in Phonology (Chen & Hulden, NAACL 2018)

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.