Overview

We’ve now seen that the regular languages on an alphabet $\Sigma$ are closed under union, concatenation, Kleene star, complement, and intersection. If we start with finitely many regular languages and combine them using these operations, the result is still regular. As I mentioned in the section on generation, the string languages needed to state phonological generalizations appear to fall within this class.

But recall the point I made in the section on the Generativist Conceit: fix a nonempty finite alphabet $\Sigma$. Gold’s superfinite obstruction (SFO) applies to any hypothesis class that contains every finite subset of $\Sigma^*$ and at least one infinite language. No learner can identify every language in such a class in the limit from an arbitrary text—that is, a positive presentation of the target (Gold 1967). The regular languages satisfy both conditions, so the full class is not identifiable from positive examples alone. If phonological grammars are regular and children learn them from positive data, the hypothesis space must thus be restricted. Merely lacking an infinite ascending chain is neither Gold’s stated condition nor a general requirement for learnability.

So which subclass should we consider? Is there a principled way to identify the region of the regular languages where phonological patterns live?

Work in formal language theory and computational phonology identifies a collection of subclasses known as the subregular hierarchy. This hierarchy bears on our question in two ways. First, particular parameter-bounded families near its bottom have positive-data learning results (Heinz 2010; Jardine and Heinz 2016). Second, many attested phonological patterns fall into these low subregular classes (Heinz 2018; Rogers and Pullum 2011; Rogers et al. 2013; Lambert et al. 2021). This does not mean that every class pictured below is learnable from positive data as an unrestricted hypothesis space.

The hierarchy looks roughly like this:

graph BT
    SL["<b>SL</b><br/>Strictly Local"] --> LT["<b>LT</b><br/>Locally Testable"]
    SP["<b>SP</b><br/>Strictly Piecewise"] --> PT["<b>PT</b><br/>Piecewise Testable"]
    LT --> SF["<b>Star-Free</b>"]
    PT --> SF
    TSL["<b>TSL</b><br/>Tier-based<br/>Strictly Local"] --> SF
    SF --> REG["<b>Regular</b>"]
    SL --> TSL

    style SL fill:#d4edda,stroke:#28a745,stroke-width:2px
    style SP fill:#d4edda,stroke:#28a745,stroke-width:2px
    style TSL fill:#fff3cd,stroke:#ffc107,stroke-width:2px,stroke-dasharray: 5 5
    style LT fill:#d1ecf1,stroke:#17a2b8
    style PT fill:#d1ecf1,stroke:#17a2b8
    style SF fill:#e2e3e5,stroke:#6c757d
    style REG fill:#f8d7da,stroke:#dc3545

Solid arrows indicate strict containment ($\subset$). TSL properly contains SL and is properly contained in the star-free languages, but it is incomparable with LT and PT (Heinz et al. 2011). The green classes at the bottom are where most attested phonological patterns live.

SL (Strictly Local) and SP (Strictly Piecewise) are the smallest classes, capturing constraints on adjacent segments and on subsequences respectively.
LT (Locally Testable) and PT (Piecewise Testable) are somewhat larger: they can count local or piecewise patterns up to a threshold.
The Star-Free languages sit just below the full regular languages—they are exactly the languages definable without the Kleene star (using only union, concatenation, and complement).
TSL (Tier-based Strictly Local) crosscuts this picture: it projects the string onto a tier (a subset of the alphabet) and then applies SL constraints on the projected string. This allows it to handle long-distance consonant harmony and similar patterns that are not SL on the full alphabet but become SL once irrelevant segments are ignored (Heinz et al. 2011).

Attested phonological patterns cluster at the bottom of this hierarchy, primarily in SL, SP, and TSL. Very few phonological patterns require even LT or PT, and essentially none require the full power of the regular languages. This convergence is compatible with a role for learnability in shaping phonological systems, though the formal results by themselves do not establish that causal claim.

We’ll begin with local constraints such as restrictions on adjacent segments. Then we’ll allow long-distance subsequences and projected tiers. With those examples in hand, we’ll return to the full hierarchy and its learnability claims.

References

Gold, E. Mark. 1967. “Language Identification in the Limit.” Information and Control 10 (5): 447–74. https://doi.org/10.1016/S0019-9958(67)91165-5.

Heinz, Jeffrey. 2010. “Learning Long-Distance Phonotactics.” Linguistic Inquiry 41 (4): 623–61. https://doi.org/10.1162/LING\_a\_00015.

Heinz, Jeffrey. 2018. “The Computational Nature of Phonological Generalizations.” In Phonological Typology, edited by Larry M. Hyman and Frans Plank. De Gruyter Mouton. https://doi.org/10.1515/9783110451931-005.

Heinz, Jeffrey, Chetan Rawal, and Herbert G. Tanner. 2011. “Tier-Based Strictly Local Constraints for Phonology.” Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, 58–64.

Jardine, Adam, and Jeffrey Heinz. 2016. “Learning Tier-Based Strictly 2-Local Languages.” Transactions of the Association for Computational Linguistics 4: 87–98. https://doi.org/10.1162/tacl\_a\_00085.

Lambert, Dakotah, Jonathan Rawski, and Jeffrey Heinz. 2021. “Typology Emerges from Simplicity in Representations and Learning.” J. Language Modelling 9 (1): 151–94. https://doi.org/10.15398/jlm.v9i1.262.

Rogers, James, Jeffrey Heinz, Margaret Fero, Jeremy Hurst, Dakotah Lambert, and Sean Wibel. 2013. “Cognitive and Sub-Regular Complexity.” Formal Grammar, Lecture notes in computer science, vol. 8036: 90–108. https://doi.org/10.1007/978-3-642-39998-5\_6.

Rogers, James, and Geoffrey K. Pullum. 2011. “Aural Pattern Recognition Experiments and the Subregular Hierarchy.” J. Logic, Language and Information 20 (3): 329–42. https://doi.org/10.1007/s10849-011-9140-2.

--- title: Overview bibliography: ../../references.bib --- We've now seen that the regular languages on an alphabet $\Sigma$ are closed under union, concatenation, Kleene star, complement, and intersection. If we start with finitely many regular languages and combine them using these operations, the result is still regular. As I mentioned in the [section on generation](../generation.qmd), the string languages needed to state phonological generalizations appear to fall within this class. But recall the point I made in the [section on the Generativist Conceit](../the-generativist-conceit.qmd): fix a nonempty finite alphabet $\Sigma$. Gold's **superfinite obstruction** (SFO) applies to any hypothesis class that contains every finite subset of $\Sigma^*$ and at least one infinite language. No learner can identify every language in such a class in the limit from an arbitrary text—that is, a positive presentation of the target [@gold1967language]. The regular languages satisfy both conditions, so the full class is not identifiable from positive examples alone. If phonological grammars are regular and children learn them from positive data, the hypothesis space must thus be restricted. Merely lacking an infinite ascending chain is neither Gold's stated condition nor a general requirement for learnability. So which subclass should we consider? Is there a principled way to identify the region of the regular languages where phonological patterns live? Work in formal language theory and computational phonology identifies a collection of subclasses known as the *subregular hierarchy*. This hierarchy bears on our question in two ways. First, particular parameter-bounded families near its bottom have positive-data learning results [@heinz2010learning; @jardine2016learning]. Second, many attested phonological patterns fall into these low subregular classes [@heinz_computational_2018; @rogers2011aural; @rogers2013cognitive; @lambert2021typology]. This does not mean that every class pictured below is learnable from positive data as an unrestricted hypothesis space. The hierarchy looks roughly like this: ```{mermaid} %%| fig-width: 7 graph BT SL["SL Strictly Local"] --> LT["LT Locally Testable"] SP["SP Strictly Piecewise"] --> PT["PT Piecewise Testable"] LT --> SF["Star-Free"] PT --> SF TSL["TSL Tier-based Strictly Local"] --> SF SF --> REG["Regular"] SL --> TSL style SL fill:#d4edda,stroke:#28a745,stroke-width:2px style SP fill:#d4edda,stroke:#28a745,stroke-width:2px style TSL fill:#fff3cd,stroke:#ffc107,stroke-width:2px,stroke-dasharray: 5 5 style LT fill:#d1ecf1,stroke:#17a2b8 style PT fill:#d1ecf1,stroke:#17a2b8 style SF fill:#e2e3e5,stroke:#6c757d style REG fill:#f8d7da,stroke:#dc3545 ``` Solid arrows indicate strict containment ($\subset$). TSL properly contains SL and is properly contained in the star-free languages, but it is incomparable with LT and PT [@heinz2011tier]. The green classes at the bottom are where most attested phonological patterns live. - **SL** ([Strictly Local](local-languages.qmd)) and **SP** ([Strictly Piecewise](piecewise-languages.qmd)) are the smallest classes, capturing constraints on adjacent segments and on subsequences respectively. - **LT** (Locally Testable) and **PT** (Piecewise Testable) are somewhat larger: they can count local or piecewise patterns up to a threshold. - The **[Star-Free](star-free-and-the-full-picture.qmd)** languages sit just below the full regular languages—they are exactly the languages definable without the Kleene star (using only union, concatenation, and complement). - **TSL** (Tier-based Strictly Local) crosscuts this picture: it projects the string onto a *tier* (a subset of the alphabet) and then applies SL constraints on the projected string. This allows it to handle long-distance consonant harmony and similar patterns that are not SL on the full alphabet but become SL once irrelevant segments are ignored [@heinz2011tier]. Attested phonological patterns cluster at the bottom of this hierarchy, primarily in SL, SP, and TSL. Very few phonological patterns require even LT or PT, and essentially none require the full power of the regular languages. This convergence is compatible with a role for learnability in shaping phonological systems, though the formal results by themselves do not establish that causal claim. We'll begin with local constraints such as restrictions on adjacent segments. Then we'll allow long-distance subsequences and projected tiers. With those examples in hand, we'll return to the full hierarchy and its learnability claims.