The linguistic notion of a natural class has precursors as far back as Pāṇini (e.g., Kiparsky 1991) and Dionysius Thrax (e.g., Sen 2024), and plays a major role in generative phonology and its structuralist forebears. There are three closely-related intuitions underlying this notion. First, while phonological processes may target single segments, there may also be multiple target segments, sharing specific articulatory and/or acoustic properties. This motivates the use of featurally-defined natural classes to define targets of phonological processes. Second, processes which target multiple segments may apply articulatory and/or acoustic parallel changes to these targets. This motivates the use of phonological features to describe the changes triggered by processes, though the “change” portion of a phonological rule cannot be equated with a natural class, because it does not in any sense contain segments as members (e.g., Bale et al. 2020). Third, while processes may be triggered in the environment of individual segments, the same (or parallel) changes may occur when the target segments occur within the environment of various triggers, again sharing specific articulatory and/or phonetic properties. This motivates the use of featurally-defined natural classes to also define triggers of processes. These three intuitions are tightly intertwined. In particular, the notions of natural class targets and featurally-defined changes seem impossible to motivate independently, since one is needed to justify the other. Once again, we speak in terms of rules but similar intuitions can be stated in constraint-based theories insofar as these constraints are defined in featural terms.7

Our interpretation of natural classes and related notions below is mentalistic: we are concerned with them as they exist in the head of the child acquiring, or the adult who has acquired, Georgian. However, we note that these notions have some relevance even for instrumentalists, like the linguist interested in (merely) describing Georgian or the engineer interested in modeling Georgian pronunciation. These stakeholders could describe the full pattern by listing out pairs of substrings like /ɫe/ ⇝ [le], /ɫo/ ⇝ [lo], and so on, but feature-based natural class descriptions often result in far greater conciseness. However, we do not consider conciseness to be an objective in and of itself. In our view, rules in I-languages are concise only to the extent they are encoded by featurally-defined natural classes, just as lexical representations are concise—i.e., involve underspecification—only to the extent that such representations are selected by the protocols of the language acquisition device, whatever these are.8 We see no reason to assume that the minimization of redundancy plays a role in such protocols, and we believe any putative reduction of redundancy must be preceded by a stage of maximally rich representations.

A full-throated defense of our assumption that the phonological feature inventory is innate and universal would take us too far afield—though see Chomsky & Halle 1965 and Reiss & Volenec 2022 for this—but we will defend it as a useful scientific idealization for isolating the FSP.

For sake of argument, suppose instead that distinctive features are induced, on a language-specific basis, from the primary linguistic data; this appears to be the position of Mielke (2008), Archangeli & Pulleyblank (2015), and Chabot (this issue), among others.

Consider a child acquiring Georgian who hears substrings like the […le…, …ɫs…, …li…, …ɫɑ…, …ɫqʼ…] found in the words listed in (1). First, on what basis is this child to first infer that different renditions of [l] are instances of the same segment, different renditions of [ɫ] are instances of a distinct segment, and similarly for the flanking segments [e, i, …]? We take these inferences to reflect innate categorical perception of segments, as documented by Janet Werker and colleagues (e.g., Werker et al. 1981; Werker & Tees 1984; Werker & Lalonde 1988; Polka & Werker 1994). Categorical perception, in turn, reflects the fact that the percepts themselves, the segments, are featurally specified. Second, supposing that the child has perceived renditions of the various segments in the primary linguistic data, on what basis are they to determine that [l] and [ɫ] are instances of the same higher-level category (i.e., surface realizations of /ɫ/)? Third, supposing that the child has identified the allophonic relationship between [l] and [ɫ], on what basis is the child to determine that the distribution is framed in terms of shared properties of [i, e], rather than separate rules for [i] and [e]? We take the latter two inferences to reflect an innate imperative to cast sound patterns in terms of features and natural classes whenever possible, an instance of what Fodor (1980: 33f.) calls epistemic boundedness: children can perceive natural class generalizations, and are incapable of not perceiving them. This, it seems to us, requires that features be epistemically prior to language-specific natural classes, since the latter are defined in terms of the former. More plainly, a learner can’t detect a pattern involving features without having the featural categories defining that pattern. We see no way to circumvent the chicken-and-egg dilemma of jointly (i.e., simultaneously) learning the featural representation of the relevant segments and the change and environment of the rule. Mielke, Archangeli & Pulleyblank, and other proponents of “emergent” features and natural classes, have little to say about these crucial matters. However, even if one is not convinced by our brief defense of feature nativism, it should be clear that it is more manageable to study the (yet unsolved) feature-specification problem without the additional complexities that emergentist accounts of features introduce.

We are at last in a position to provide a formal definition of the FSP. This definition is intended to be sufficiently generic to apply to any theory in which rules are defined in part by targets and triggers, which are in turn defined by natural classes (§2.1.4), natural classes are defined by sets of feature specifications interpreted as sets of segments (§2.1.3), and segments consist of sets of valued features (§2.1.2).

The FSP is a subproblem in the acquisition of phonological grammars encountered during the induction of individual rules. We suppose that, via some alignment procedure to be determined, the child has isolated lists of segments—represented as sets of valued features—behaving as targets of the candidate rule. Similarly, any observed trigger segments for this candidate rule have also been isolated into similar lists, one for each non-target position in the environment. We provide an example specification of this form for Georgian /ɫ/-fronting, using IPA characters as stand-ins for the full featural specifications.

A feature specification function is then a function from sets of feature specifications, such as the one that defines the targets above, to natural class specifications for those targets. This function is applied separately to the list of targets, and to each of the trigger positions in the specification, and the resulting natural classes are then combined with a featural representation of the change to build the phonological rule.

We are not in a position to provide a full algorithm by which children might induce a full phonological grammar. This problem is much bigger than the FSP itself, but it demands a solution to the FSP under the assumption that rule targets and triggers are defined by natural classes. We anticipate that the rule induction system will need to inspect candidate natural classes for various properties in the course of induction. First is the case where the input feature specifications share no common features, so the maximal natural class is simply []. As Bale et al. (2020) note, this “universal” natural class contains all segments, because (by a theorem of set theory) every set is a superset of the empty set. Again, this is not specific to the objective or algorithm: the universal natural class is the only natural class that contains both input segments in this case. The rule induction system will have to determine whether the generalization from some to all segments is valid or invalid, perhaps by considering segments not observed in, or known not to be, members of the relevant class in the primary linguistic data.12 In other cases, an algorithm in some cases returns natural classes whose members include elements other than the input, but not quite as broad as the universal []. For example, in the Hayes (2009) feature table, which largely follows traditional assumptions regarding place or manner features, any natural class which contains coronal plosives like /t/ and dorsal fricatives like /x/ will necessarily also contain coronal fricatives like /s/ and dorsal plosives like /k/. Again, this follows not from the specific objective or algorithm used, but from the structure of the feature system and our insistence that rules are defined by natural classes, and any rule induction system will have to determine what to do with the resulting natural class. For instance, if the generalization from /t, x/ to /s, t, x, k/ is known to be inconsistent with the primary linguistic data, the rule induction system presumably must conclude that the putative “process” targeting, or triggered by, /t, x/ is actually decomposed into two or more rules. Thus our insistence that rules are defined by natural classes provides a principled mechanism for an induction algorithm to determine when a process can or cannot be handled by a single rule.

Potential solutions to the FSP, then, are algorithmic definitions of feature specification functions. In the next section, we analyze feature specification functions implementing the received wisdom that an optimal feature specification is “minimal”, and show that such functions necessarily have undesirable properties. Then, in section 4, we argue for an alternative solution, one producing a feature specification that is in some sense maximal.

One belief that seems to be shared by virtually all generative phonologists is a preference for minimally-specified natural classes, all else held equal, reflecting a more-general preference for conciseness in the grammars of individual languages. We discern three related motivations for conciseness of this sort before presenting our heretical alternative.

The first motivation for conciseness, which is often made explicit in the writings of early generative phonology, and is also echoed in current work, is the post-war fascination with information theory, henceforth IT. When first announced (Shannon 1948), IT was seen as something of a “universal acid”, applicable to virtually any scientific problem. IT also drew some of its cachet from Shannon’s strategically important wartime work on cryptanalysis, encryption, and fire control, among other problems.13 Indeed, the prestige of IT was so great that Shannon himself warned his theory had become something of a “scientific bandwagon”.

Writing of his research during this era, Halle confesses that he and colleagues had made the mistake jumping on the bandwagon:

IT’s influence on early generative linguistics extends beyond explicit computations of the bits of information, though, towards a general preference for grammatical conciseness. For instance, Chomsky states a preference for intensionally minimal and extensionally maximal classes:

This theme is developed in The Sound Pattern of English (SPE; Chomsky & Halle 1968:§8.1), where this preference is expressed using a feature-counting evaluation metric which favors the most concise (in terms of features) empirically adequate grammar. Kenstowicz & Kisseberth, for example, provide a concise formulation of the SPE evaluation metric:

The second motivation for grammatical conciseness is the notion that the child’s task during language acquisition can be likened to a search for concise descriptions of the primary linguistic data. This idea is a manifestation of a more general idea that the best theory in any domain is the one that is most compact: as Chaitin (2006: 77) writes, “[a] useful theory is a compression of the data; compression is comprehension.” This notion is commonly expressed in terms of the notion of minimal description length (MDL), which appears in many domains including computational cognitive models of language acquisition. For example, Rasin et al. (2021), in a simulation of phonological grammar learning, use MDL to motivate natural class induction. In contrast, our assumptions (see §2.1.3) require no further motivation for natural classes, because they are the only mechanism UG provides for encoding rule targets and triggers.

The third and final motivation for conciseness appears to be an appeal to Occam’s Razor as applied to grammatical description. As Halle writes below:

Halle is not alone in appealing to Occam’s Razor. The following quotations are all drawn from phonology textbooks:

Odden continues, providing an explicit example in favor of intensional minimality and extensional maximality:

In a slight variation on this theme, Halle & Clements present conciseness less as a scientific principle than a cross-linguistic tendency:

The only departure from this orthodoxy we are aware of comes from Zimmer, whose critique is directed at feature-counting metrics:

We acknowledge Occam’s Razor as an unavoidable principle of scientific practice, but suggest that at least some of the quotations above apply it at the wrong level of description. In particular, we see no motivation for applying Occam’s Razor to the grammars of individual languages. Pace Halle (2019)—who takes the Razor to apply to “scientific accounts of all kinds”—the natural classes and conditions that define the phonological rules of languages are ontologically different objects than operations like Merge. A linguist might posit Merge as a fundamental part of the language faculty, and thus (potentially) part of every grammar. If this is correct, then no child posits Merge or modifies it in the construction of a particular I-language; rather, Merge is given. In contrast, a linguist might posit a phonological process like devoicing of obstruents in the coda of syllables as a component of a particular language, and the linguist knows that the process is composed of primitives such as valued features, reference to precedence, structural relations among segments, and so on. The linguist builds the rule out of a hypothesized set of primitives, and—if they are interested in how children acquire and encode rules—they hope that the child has also constructed the corresponding I-language rule out of the same fundamental toolkit. The difference is that the linguist cannot be sure what the toolkit contains, whereas the child’s hypothesis space is defined by the toolkit that UG provides, whatever that happens to be. This is why the linguist needs Occam’s Razor and the child does not.14 For the phonologist trying to decide if it is necessary to posit both ATR and RTR, or both Back and Front as part of the universal feature set, Occam’s Razor is relevant. A child, however, encodes representations using all the innately-given features, whatever they happen to be, and the child already knows what those features are.

These three bits of received wisdom cannot be fully disentangled. IT can be thought of as a method for operationalizing Occam’s Razor, and MDL acquisition accounts are fundamentally also applications of IT. The MDL approach is also motivated in part by theories which draw strong parallels between cognitive development and the day-to-day work of scientists, such as Gopnik’s (2003) “theory theory” proposed as an alternative to linguistic nativism. In the context of language acquisition, this theory likens the practices of linguists—including, apparently, the obsession with grammatical conciseness we document above—to that of “little linguists”: children acquiring language. As we suggested above, such analogies are flawed, because there is a fundamental difference in the two domains under consideration. The scientist starts with no iron-clad domain-specific contentful concepts, only tentatively hypothesized categories and the general concepts of the science forming faculty, but has the ability to make and test hypotheses, and to reason from negative evidence. Because the scientists are starting from a blank slate of domain-specific concepts, they ought to only enrich the model when forced to.15 In contrast, the child already has a well-defined space of concepts, but has no way of predicting which are redundant, and no reason to do so.

Having established that there is a received wisdom holding that feature specifications are intensionally minimal, we first consider formal properties of minimization as an objective for the FSP. Then, building on work by Chen & Hulden (2018), we show that no tractable algorithm exists to compute this objective.

According to Robins & Waterson, Georgian /ɫ/-fronting is triggered by a following /i, e/. Using the vowel feature matrix in (3), the natural class [–Back] contains /i, e/ and no other segments, and appears to be the unique, intensionally minimal characterization of that set of trigger segments which does not include any other Georgian phonemes. The minimization objective potentially provides a mechanism to decide between extensionally equivalent characterizations of the trigger natural class listed in (4). However this is not generally the case because there may be multiple ways to minimally specify a given natural class. We provide three concrete examples of non-uniqueness below, though we conjecture that such cases are quite common.

Keeping in mind that natural classes may have multiple minimal specifications, what algorithm might allow us to find all of the minimal specifications? First consider a truly naïve algorithm, which iteratively considers all possible natural class specifications. If ℱ contains n features, there are 3ⁿ intensionally distinct natural classes to consider,16 giving a worst-case complexity of O(3ⁿ). To give a sense of scale, there are almost 23 trillion natural classes to consider with Hayes’s 30-feature inventory, a number that is “essentially infinite” for our purposes. Even this feature system is insufficient, since it does not provide a complete set of features needed to distinguish less-common types of phonation (e.g., creaky voice) or non-pulmonic airflow mechanisms (e.g., clicks, ejectives, or implosives) which are contrastive in many languages.

Two tricks are potentially applicable to the naïve algorithm. First, it makes sense to consider natural classes with k valued features before considering those with k + 1 features, since our goal is to identify intensionally minimal classes. Second, it makes sense to limit the search to natural classes whose specifications are consistent with the specifications of the segments in the extension of the natural class. Anticipating results presented in the following section, this limitation can be enforced by computing the maximal natural class—which can itself be computed efficiently—and then limiting the search to subsets of that class. However, these tricks do not affect the worst-case computational complexity of this naïve algorithm; the former may permit one to halt earlier on average, whereas the latter results in a smaller effective value of n.

In recent work Chen & Hulden (2018), henceforth C&H, prove that no algorithm can meaningfully improve on the exponential worst-case complexity of the naïve algorithm outlined above. While we essentially assume their results as presented, and refer the interested reader to their paper, we provide a high-level review of their proof, but we first consider its relevance to the FSP.

Tractability is the constraint on cognitive capacities which holds they must be implemented by biological-cognitive systems (such as human brains) subject to reasonable assumptions about these systems’ resource limitations. One widely-debated hypothesis regarding tractability is the P-cognition thesis (e.g., Frixione 2001). An algorithm is said to run in polynomial time if it is guaranteed to terminate in time proportional to some polynomial function of the size of the input, and the P-cognition thesis holds that cognitive capacities are limited to functions which can be computed in polynomial time. While the P-cognition thesis has been disputed from many angles (see, e.g., van Rooij 2008), it seems to have been implicitly adopted by many in the computational phonology community. For example, Eisner (1997), Idsardi (2006), and Heinz et al. (2009) debate whether it is possible to find the optimal candidate in Optimality Theory in polynomial time. Similarly, Heinz (2010) and Chandlee et al. (2014) prove their algorithms for acquiring phonotactic generalizations and phonological mappings, respectively, are decidable in polynomial time. These debates and demonstrations draw their force from their authors’ implicit adoption of the P-cognition thesis.

C&H’s method involves relating the minimization objective to the well-studied set cover problem. In this problem, one is presented with a set U (the “universe”) and a set of subsets of U denoted 𝒮, and an integer k. One must then decide whether there exist k or fewer member sets of 𝒮 whose union equals U. A worked example, using integers as set elements, is given below.

Set cover is a canonical NP-complete problem (Karp 1972): while it is easy to verify that a proposed solution is correct, finding such a solution requires one to search through exponentially many such sets in the worst case. To prove that minimization is NP-complete, C&H perform a reduction from set cover. A reduction from problem A to problem B is a mapping which converts any instance of problem A into an instance of problem B, such that if the answer to A is yes if and only if the answer to B is also yes. If this mapping can be performed efficiently (i.e., in polynomial time), and if A is known to be hard, then B must be at least as hard as A. Thus, under the standard conjecture that P ≠ NP, C&H’s reduction proves that minimization inherits the NP-complete intractibility of set cover. C&H show this result holds for both equipollent and privative feature systems.

We assume C&H’s results in full. To reiterate, the force of C&H’s reduction is this: no polynomial-time algorithm is guaranteed to find the minimal natural class. Thus, under the P-cognition thesis, feature minimization is inherently intractable; it is not a candidate objective for the FSP. Some other objective is needed, and it is to this we now turn.

Consider again the case of Georgian /ɫ/-fronting, triggered by a following /i, e/ and no other segments. The maximal natural class is then the class which contains /i, e/ and which is defined by as many valued features as possible. This class is unique, as can be informally demonstrated via contradiction. Suppose, contra our claim that this class must be unique, there are actually two natural classes containing /i, e/, C₁ and C₂, which are distinct but both “maximal”. Because they are distinct, there must be some specifications in C₁ but not C₂ (and vice versa). Then, we should be able to construct an “actual” maximal natural class C₃ which contains all the valued features in C₁ (resp. C₂) as well these additional valued features. But this contradicts our earlier assumption that C₁ and C₂ are maximal, showing our initial assumption—the existence of a maximal but distinct C₁ and C₂—was ill-founded.

As alluded to above, the maximal natural class is a natural starting point for minimization algorithms, like exhaustive branch-and-bound strategies or the greedy heuristics considered by Chen & Hulden. Such solutions must be subsets of the maximal natural class. For example, a minimal natural class containing /i, e/ must not contain any valued features not also in both /i, e/ or the class would not contain both /i/ and /e/. As such, maximization can be thought of as a satisficing strategy in the sense of Simon (1956), in contrast to the optimizing strategy represented by minimization.

We now provide a simple algorithm for computing the maximal natural class.

Let S and T be feature specifications for two segments. Then, the maximal natural class containing {S,T} is defined by their intersection, S ∩ T.

Since this algorithm loops over S, and a consistent segment has no more than n specifications, this algorithm runs in linear time, specifically O(n). By any account, this means this algorithm is highly tractable.

Applying this algorithm to /i, e/ using the 24 vowel features provided by Hayes (2009: §4.10), one obtains a natural class specified by 23 features: every one except High, the one feature for which /i, e/ have inconsistent specifications:

While intersection is defined in terms of pairs of segments, intersection is associative (and commutative), so it easily generalizes to more than two segments. That is, given specifications S, T, U, it is the case that S∩T∩U = (S∩T)∩U = S∩(T∩U) and so on. One special case is when the extension of the class is a single segment; here, one need only return the feature specification of that segment in the form of a natural class.

As we stated in the introduction, there are a number of different extensionally equivalent feature specifications for the class /i, e/: minimal, maximal, or various points between. However, there is one corner case where the maximal natural class obtained via intersection may have a different extension than a minimal class. Consider the maximal and minimal natural classes for the segments /i, e/, repeated from (4a,e):

Both of these classes contain Georgian /i, e/ and no other segments in this language. Let us suppose, however, it were possible to introduce a new phoneme, say /æ/, into the mind of a Georgian speaker. This vowel is, presumably, a member of the minimally specified class (20a). But it is presumably not a member of (20b) since it is +Low. Thus the two approaches make different predictions about whether the novel /æ/ would or would not trigger /ɫ/-fronting; minimal specification predicts that it would, whereas maximal specification predicts it would not. While there is some precedent for using informal production experiments to test similar hypotheses (e.g., Halle 1978), it is not immediately clear to us whether it is at present possible to truly introduce a novel phoneme into the mind of an adult speaker.

It is possible to imagine other objectives beyond minimization or maximization, and indeed, some of these may correspond to tractable algorithms. At present, though, it is not clear what other objectives are worthy of consideration. As an illustration of this point, we take the unusual step of quoting from comments made by an anonymous reviewer of an earlier version of this work.

The reviewer first observes that an implementation of a branch-and-bound algorithm considered by Chen & Hulden does, in their experiments, find minimal specifications, “albeit with a fairly large search space”. It would be more precise to say, though, that branch-and-bound has the same “essentially-infinite” search space as the infeasible brute-force algorithm and thus the same worst-case complexity. In other words, it is not an alternative to the minimization objective under the P-cognition thesis.

The reviewer then discusses C&H’s experiments with a brute-force “greedy algorithm”, a heuristic in our terminology. Of these experiments, the reviewer writes that “but even then the failure is one of positing 4 features in a case where 3 would have sufficed. That is actually encouraging!” However, one ought not to reason solely from apparent best case performance. First, C&H report experiments with just six natural classes using an English-only feature system which defines almost 23 trillion intensionally distinct natural classes, hardly a sufficient basis on which to determine the overall difficulty of the minimization problems children might be expected to encounter. Rather, one ought to refer to known approximation ratios for the greedy algorithm, i.e., upper bounds on how much worse a set cover solution found via the greedy algorithm is than exhaustive search (e.g., Slavík 1997); whether these admittedly abstract results ought to be be “encouraging” for proponents of minimization is unclear to us. One could, of course, argue that the heuristic itself is the proper solution to the FSP, but we know of no evidence that children pursue a minimization objective in the first place.

Finally, the reviewer writes that “a specialized feature minimization algorithm is likely to yield better results, for example by prioritizing coarse features like consonantal over more fine-grained ones like strident. Features are not the same as the arbitrary sets in the set cover problem, some features are more important than others. […] I fully expect the problem to be highly tractable under these parameters”. There are two possible ways to interpret this suggestion. First, one could interpret this suggestion as type of greedy heuristic, in which “coarse” features are given higher precedence than “fine-grained” ones. Alternatively, many feature systems consist of specifications which are proper subsets of each other, and one could potentially take advantage of this type of subsumption structure while solving a set cover problem. For example, if all +Strident segments are +Consonantal but not all +Consonantal segments are +Strident, as Hayes (2009) assumes, then the extension of [+Strident] is a proper subset of the extension of [+Consonantal]. Translating this to the minimization problem, if the intersection contains +Strident one can safely discard +Consonantal from consideration. However, such structure has no effect on the overall tractability of the minimization objective. We have chosen not to pursue either suggestion, since we are reluctant at this early stage to commit to any account which closely depends on the vagaries of specific featural systems.

The bias in favor of minimal description can add unnecessary, unmotivated complexity to phonological analyses. We demonstrate this by reviewing one detail of Georgian /ɫ/-fronting and introducing Malayalam palatalization. Like our discussion of non-uniqueness, these case studies are meant to be exemplary rather than exhaustive, and we suspect many examples of a similar form can be found in the literature.