Local languages

Consider the English onset cluster [bl], as in black. This is a perfectly fine way to start a word. The reverse, [lb], is not: there is no English word that begins with [lb]. This constraint depends only on a short sequence of symbols at a particular position in the word, namely the beginning. In the terminology we’ll develop here, this makes it a local constraint.

Strictly Local languages

How can we formalize the contrast between [bl] and word-initial [lb]? A Strictly Local language of order $k$, or SL-$k$ language, is one whose membership can be determined by checking whether any forbidden sequence of $k$ consecutive symbols appears in the string (Heinz 2010; Rogers and Pullum 2011). More precisely, we augment the string with boundary markers $\rtimes$ (left edge) and $\ltimes$ (right edge) and check all the $k$-grams of the augmented string against a finite set of forbidden $k$-grams.

A language $L$ is SL-$k$ if and only if there exists a finite set $\mathcal{F} \subset (\Sigma \cup \{\rtimes, \ltimes\})^k$ such that:

\[w \in L \iff \text{no } k\text{-gram of } \rtimes^{k-1} w \ltimes^{k-1} \text{ is in } \mathcal{F}\]

The set $\mathcal{F}$ is called the set of forbidden factors. Notice that the boundary markers let us express constraints on how strings begin and end: a forbidden $k$-gram starting with $\rtimes$ is a constraint on the first symbols of the string.

For instance, the constraint against [lb] onsets in English can be expressed as an SL-3 constraint with $\rtimes\text{lb} \in \mathcal{F}$: the trigram consisting of the left boundary marker followed by [l] followed by [b] is forbidden.¹

This illustrates an important point: boundary markers are not just a technical convenience. They are what allow SL grammars to distinguish between positional and non-positional constraints. Without them, every SL constraint would apply uniformly across the string. With them, we can express constraints like “word-initial [lb] is forbidden” separately from “word-medial [lb] is fine.”

For a constraint that does apply uniformly, consider the sequence [ŋm]: English never allows a velar nasal [ŋ] followed immediately by a bilabial nasal [m], regardless of position in the word. This is an SL-2 constraint with $\text{ŋm} \in \mathcal{F}$, with no boundary marker needed.

We can build FSAs that enforce these constraints using arcweight. The idea is to construct an automaton that accepts precisely the strings containing the forbidden factor, and then take its complement.

Build an SL-2 constraint FSA forbidding [ŋm]

import arcweight

# Define the alphabet
phones = ['l', 'b', 'k', 'æ', 'ɪ', 'ŋ', 'm']
syms = arcweight.SymbolTable()
syms.add_symbol('<eps>')
sym_ids = {}
for p in phones:
    sym_ids[p] = syms.add_symbol(p)

# Build sigma-star: an FSA accepting all strings over the alphabet
sigma_star = arcweight.VectorFst()
s = sigma_star.add_state()
sigma_star.set_start(s)
sigma_star.set_final(s, 0.0)
for p in phones:
    sigma_star.add_arc(s, sym_ids[p], sym_ids[p], 0.0, s)

# Build an FSA that accepts strings containing the bigram [ŋm]
# States: 0 = no ŋ just seen, 1 = just saw ŋ, 2 = saw ŋm (accept sink)
contains_nm = arcweight.VectorFst()
s0 = contains_nm.add_state()
s1 = contains_nm.add_state()
s2 = contains_nm.add_state()
contains_nm.set_start(s0)
contains_nm.set_final(s2, 0.0)

# From s0: seeing 'ŋ' goes to s1, anything else stays at s0
for p in phones:
    if p == 'ŋ':
        contains_nm.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s1)
    else:
        contains_nm.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s0)

# From s1: seeing 'm' goes to s2 (found ŋm), seeing 'ŋ' stays at s1, else back to s0
for p in phones:
    if p == 'm':
        contains_nm.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s2)
    elif p == 'ŋ':
        contains_nm.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s1)
    else:
        contains_nm.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s0)

# From s2: accept sink — everything stays
for p in phones:
    contains_nm.add_arc(s2, sym_ids[p], sym_ids[p], 0.0, s2)

# The SL-2 constraint: accept strings that do NOT contain [ŋm]
no_nm = arcweight.difference(sigma_star, contains_nm)

print(f"sigma_star states: {sigma_star.num_states()}")
print(f"contains_nm states: {contains_nm.num_states()}")
print(f"no_nm states: {no_nm.num_states()}")

Notice that the states of an SL-$k$ constraint automaton are determined by the last $k - 1$ symbols seen. In our SL-2 example, the state tracks only the previous symbol: whether it was an [ŋ] (in which case a following [m] is forbidden) or something else. This is a very restricted kind of DFA—one where the state space is essentially $\Sigma^{k-1}$ (or a subset of it).

This observation gives a construction for every SL-$k$ language. Fix an arbitrary forbidden-factor set $\mathcal{F}$. Create one state for each suffix of length at most $k-1$ that can occur without completing a member of $\mathcal{F}$, together with a rejecting sink state. After a symbol is read, append it to the stored suffix. If the resulting $k$-gram belongs to $\mathcal{F}$, move to the sink; otherwise retain only the newest $k-1$ symbols. Boundary markers are processed in the same way at the beginning and end, though they are not part of the surface string.

Why does this construction work? After any prefix $x$, a nonsink state should record exactly the suffix of the augmented $x$ of length at most $k-1$. The machine should be in the sink if and only if it has already encountered a forbidden $k$-gram. This is the suffix-memory invariant. It holds before any surface symbol is read because the initial state stores the left boundary markers. Now append the next symbol. This creates exactly one new $k$-gram, namely the stored suffix followed by that symbol. The transition checks that new factor and then updates the suffix, so it preserves both parts of the invariant.

After the full string and right boundary markers have been processed, the invariant says that the machine avoids the sink exactly when the augmented string contains no member of $\mathcal{F}$. This is the definition of membership in the SL-$k$ language. There are only finitely many possible suffixes because $\Sigma$ and $k$ are finite. Thus, the construction is a finite-state automaton and every SL language is regular.

This is the same information that an $N$-gram model conditions on: the preceding $N - 1$ symbols. An SL-$k$ automaton and a $k$-gram model are tracking the same context; the difference is that the SL automaton makes a binary decision about whether the context is licit, while the $N$-gram model assigns it a probability.

Combining SL constraints

A key property of the SL class is that it is closed under intersection—and this fact does not follow from the regularity of SL languages. The regular languages are closed under intersection, but that only tells us the intersection of two SL languages is regular; it doesn’t tell us it’s still SL. We need a direct argument.

Let’s check the claim directly. Suppose $L_1$ is SL-$k$ with forbidden factors $\mathcal{F}_1$ and $L_2$ is SL-$k$ with forbidden factors $\mathcal{F}_2$.² A string $w$ is in $L_1 \cap L_2$ if and only if it contains no forbidden factor from $\mathcal{F}_1$ and no forbidden factor from $\mathcal{F}_2$. But this is exactly the condition for $w$ to be in the SL-$k$ language with forbidden factors $\mathcal{F}_1 \cup \mathcal{F}_2$. So $L_1 \cap L_2$ is SL-$k$ with $\mathcal{F} = \mathcal{F}_1 \cup \mathcal{F}_2$.

This is why we can specify a phonotactic grammar as a collection of forbidden $k$-grams: the language satisfying all constraints simultaneously is the intersection of the individual SL constraints, and that intersection is itself SL. Each forbidden $k$-gram contributes to a single unified forbidden-factor set.

Combine multiple SL-2 constraints

# Also forbid [mŋ] (bilabial nasal followed by velar nasal — doesn't occur in English)
contains_mn = arcweight.VectorFst()
s0 = contains_mn.add_state()
s1 = contains_mn.add_state()
s2 = contains_mn.add_state()
contains_mn.set_start(s0)
contains_mn.set_final(s2, 0.0)

for p in phones:
    if p == 'm':
        contains_mn.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s1)
    else:
        contains_mn.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s0)

for p in phones:
    if p == 'ŋ':
        contains_mn.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s2)
    elif p == 'm':
        contains_mn.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s1)
    else:
        contains_mn.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s0)

for p in phones:
    contains_mn.add_arc(s2, sym_ids[p], sym_ids[p], 0.0, s2)

no_mn = arcweight.difference(sigma_star, contains_mn)

# Combine: strings with neither [ŋm] nor [mŋ]
combined = arcweight.intersect(no_nm, no_mn)
combined = arcweight.minimize(combined)

print(f"Combined constraint states: {combined.num_states()}")

This is the sense in which SL grammars are constraint-based: we specify what is forbidden, and the language is whatever remains.

Locally Testable languages

Strictly Local grammars are stated in terms of negative constraints: certain factors are forbidden. That format does not let us express every positive requirement. For instance, suppose we require every word to contain at least one vowel. No fixed window can tell us that a vowel occurs somewhere in an arbitrarily long word, so this language is not SL.³

Locally Testable (LT) languages generalize SL by allowing Boolean combinations of factor constraints—not just forbidden factors but required factors and arbitrary combinations thereof (Brzozowski and Simon 1973; Rogers et al. 2013). A language is LT-$k$ if membership can be determined by a Boolean formula over statements of the form “the $k$-gram $u$ appears in $\rtimes^{k-1} w \ltimes^{k-1}$.”

So “every word must contain at least one vowel” is LT-1: it’s the constraint that at least one of the 1-grams from the set of vowels must appear.

Question

Is the constraint “a word must contain at least one vowel” SL? Is it LT?

Answer

It is not SL (for any $k$), because SL can only forbid substrings; it cannot require them. But it is LT-1: the constraint is that the set of 1-grams occurring in the word must include at least one vowel, which is a positive Boolean statement about factor occurrence.

Why can’t some larger value of $k$ rescue the SL analysis? Reduce the alphabet to a consonant $c$ and a vowel $v$, and let $L$ contain exactly the strings with at least one $v$. Suppose for contradiction that $L$ is SL-$k$ for some fixed $k$. Choose $N\geq k$. The string $c^N$ is not in $L$, so its augmented representation must contain some forbidden $k$-gram $u$.

Now consider $c^Nvc^N$, which belongs to $L$. Every $k$-gram in the augmented $c^N$ also occurs in the augmented $c^Nvc^N$: left-edge factors occur in the first $c$ block, right-edge factors occur in the second, and the interior factor $c^k$ occurs in both. In particular, $u$ occurs in $c^Nvc^N$. The proposed SL grammar would thus reject a string in $L$, a contradiction. Since the argument applies to an arbitrary $k$, no SL order can express the positive vowel requirement.

LT properly contains SL: every SL language is LT because forbidding a factor is the negation of the statement “this factor appears,” but not every LT language is SL because SL cannot express positive requirements. In practice, most phonotactic constraints are SL rather than LT because they tend to prohibit particular sequences rather than require a sequence to appear. But the distinction is important for understanding the full hierarchy.

References

Brzozowski, Janusz A., and Imre Simon. 1973. “Characterizations of Locally Testable Events.” Discrete Mathematics 4 (3): 243–71. https://doi.org/10.1016/S0012-365X(73)80005-6.

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

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.

Footnotes

Why SL-3 and not SL-2? Because the forbidden factor involves three symbols: the boundary marker $\rtimes$ plus the two consonants. An SL-2 constraint with $\text{lb} \in \mathcal{F}$ would forbid [lb] everywhere in the string. But English allows [lb] across syllable boundaries, as in elbow [ɛlboʊ], bulb [bʌlb], and album [ælbəm]. The boundary marker is what lets us restrict the constraint to word-initial position.↩︎
If $L_1$ is SL-$k_1$ and $L_2$ is SL-$k_2$ with $k_1 \neq k_2$, take $k = \max(k_1, k_2)$ and extend the shorter grammar. First discard any forbidden $k'$-gram that cannot occur in a well-formed boundary-augmented string, since such a factor has no effect. Replace each remaining forbidden factor $u$ with all well-formed $k$-grams that contain $u$ as a substring. An occurrence of $u$ extends to one of these longer windows, including at either padded boundary, and every such longer window contains an occurrence of $u$. The extended grammar thus defines the same language at order $k$.↩︎
Some requirements at an edge can be restated as local prohibitions. The claim here concerns the unbounded requirement that a vowel occur somewhere, not every statement that happens to contain the word require.↩︎

--- title: Local languages bibliography: ../../references.bib jupyter: python3 --- Consider the English onset cluster [bl], as in *black*. This is a perfectly fine way to start a word. The reverse, [lb], is not: there is no English word that begins with [lb]. This constraint depends only on a short sequence of symbols at a particular position in the word, namely the beginning. In the terminology we'll develop here, this makes it a *local* constraint. ## Strictly Local languages How can we formalize the contrast between [bl] and word-initial [lb]? A *Strictly Local* language of order $k$, or SL-$k$ language, is one whose membership can be determined by checking whether any forbidden sequence of $k$ consecutive symbols appears in the string [@heinz2010learning; @rogers2011aural]. More precisely, we augment the string with boundary markers $\rtimes$ (left edge) and $\ltimes$ (right edge) and check all the $k$-grams of the augmented string against a finite set of forbidden $k$-grams. A language $L$ is SL-$k$ if and only if there exists a finite set $\mathcal{F} \subset (\Sigma \cup \{\rtimes, \ltimes\})^k$ such that: $$w \in L \iff \text{no } k\text{-gram of } \rtimes^{k-1} w \ltimes^{k-1} \text{ is in } \mathcal{F}$$ The set $\mathcal{F}$ is called the set of *forbidden factors*. Notice that the boundary markers let us express constraints on how strings begin and end: a forbidden $k$-gram starting with $\rtimes$ is a constraint on the first symbols of the string. For instance, the constraint against [lb] onsets in English can be expressed as an SL-3 constraint with $\rtimes\text{lb} \in \mathcal{F}$: the trigram consisting of the left boundary marker followed by [l] followed by [b] is forbidden.^[Why SL-3 and not SL-2? Because the forbidden factor involves three symbols: the boundary marker $\rtimes$ plus the two consonants. An SL-2 constraint with $\text{lb} \in \mathcal{F}$ would forbid [lb] *everywhere* in the string. But English allows [lb] across syllable boundaries, as in *elbow* [ɛlboʊ], *bulb* [bʌlb], and *album* [ælbəm]. The boundary marker is what lets us restrict the constraint to word-initial position.] This illustrates an important point: boundary markers are not just a technical convenience. They are what allow SL grammars to distinguish between positional and non-positional constraints. Without them, every SL constraint would apply uniformly across the string. With them, we can express constraints like "word-initial [lb] is forbidden" separately from "word-medial [lb] is fine." For a constraint that *does* apply uniformly, consider the sequence [ŋm]: English never allows a velar nasal [ŋ] followed immediately by a bilabial nasal [m], regardless of position in the word. This is an SL-2 constraint with $\text{ŋm} \in \mathcal{F}$, with no boundary marker needed. We can build FSAs that enforce these constraints using `arcweight`. The idea is to construct an automaton that accepts precisely the strings containing the forbidden factor, and then take its complement. ```{python} #| code-fold: true #| code-summary: Build an SL-2 constraint FSA forbidding [ŋm] import arcweight # Define the alphabet phones = ['l', 'b', 'k', 'æ', 'ɪ', 'ŋ', 'm'] syms = arcweight.SymbolTable() syms.add_symbol('<eps>') sym_ids = {} for p in phones: sym_ids[p] = syms.add_symbol(p) # Build sigma-star: an FSA accepting all strings over the alphabet sigma_star = arcweight.VectorFst() s = sigma_star.add_state() sigma_star.set_start(s) sigma_star.set_final(s, 0.0) for p in phones: sigma_star.add_arc(s, sym_ids[p], sym_ids[p], 0.0, s) # Build an FSA that accepts strings containing the bigram [ŋm] # States: 0 = no ŋ just seen, 1 = just saw ŋ, 2 = saw ŋm (accept sink) contains_nm = arcweight.VectorFst() s0 = contains_nm.add_state() s1 = contains_nm.add_state() s2 = contains_nm.add_state() contains_nm.set_start(s0) contains_nm.set_final(s2, 0.0) # From s0: seeing 'ŋ' goes to s1, anything else stays at s0 for p in phones: if p == 'ŋ': contains_nm.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s1) else: contains_nm.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s0) # From s1: seeing 'm' goes to s2 (found ŋm), seeing 'ŋ' stays at s1, else back to s0 for p in phones: if p == 'm': contains_nm.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s2) elif p == 'ŋ': contains_nm.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s1) else: contains_nm.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s0) # From s2: accept sink — everything stays for p in phones: contains_nm.add_arc(s2, sym_ids[p], sym_ids[p], 0.0, s2) # The SL-2 constraint: accept strings that do NOT contain [ŋm] no_nm = arcweight.difference(sigma_star, contains_nm) print(f"sigma_star states: {sigma_star.num_states()}") print(f"contains_nm states: {contains_nm.num_states()}") print(f"no_nm states: {no_nm.num_states()}") ``` Notice that the states of an SL-$k$ constraint automaton are determined by the last $k - 1$ symbols seen. In our SL-2 example, the state tracks only the previous symbol: whether it was an [ŋ] (in which case a following [m] is forbidden) or something else. This is a very restricted kind of DFA—one where the state space is essentially $\Sigma^{k-1}$ (or a subset of it). This observation gives a construction for every SL-$k$ language. Fix an arbitrary forbidden-factor set $\mathcal{F}$. Create one state for each suffix of length at most $k-1$ that can occur without completing a member of $\mathcal{F}$, together with a rejecting sink state. After a symbol is read, append it to the stored suffix. If the resulting $k$-gram belongs to $\mathcal{F}$, move to the sink; otherwise retain only the newest $k-1$ symbols. Boundary markers are processed in the same way at the beginning and end, though they are not part of the surface string. Why does this construction work? After any prefix $x$, a nonsink state should record exactly the suffix of the augmented $x$ of length at most $k-1$. The machine should be in the sink if and only if it has already encountered a forbidden $k$-gram. This is the **suffix-memory invariant**. It holds before any surface symbol is read because the initial state stores the left boundary markers. Now append the next symbol. This creates exactly one new $k$-gram, namely the stored suffix followed by that symbol. The transition checks that new factor and then updates the suffix, so it preserves both parts of the invariant. After the full string and right boundary markers have been processed, the invariant says that the machine avoids the sink exactly when the augmented string contains no member of $\mathcal{F}$. This is the definition of membership in the SL-$k$ language. There are only finitely many possible suffixes because $\Sigma$ and $k$ are finite. Thus, the construction is a finite-state automaton and every SL language is regular. This is the same information that an [$N$-gram model](../../uncertainty-about-languages/ngram-models.qmd) conditions on: the preceding $N - 1$ symbols. An SL-$k$ automaton and a $k$-gram model are tracking the same context; the difference is that the SL automaton makes a binary decision about whether the context is licit, while the $N$-gram model assigns it a probability. ### Combining SL constraints A key property of the SL class is that it is closed under intersection—and this fact does *not* follow from the regularity of SL languages. The regular languages are closed under intersection, but that only tells us the intersection of two SL languages is regular; it doesn't tell us it's still SL. We need a direct argument. Let's check the claim directly. Suppose $L_1$ is SL-$k$ with forbidden factors $\mathcal{F}_1$ and $L_2$ is SL-$k$ with forbidden factors $\mathcal{F}_2$.^[If $L_1$ is SL-$k_1$ and $L_2$ is SL-$k_2$ with $k_1 \neq k_2$, take $k = \max(k_1, k_2)$ and extend the shorter grammar. First discard any forbidden $k'$-gram that cannot occur in a well-formed boundary-augmented string, since such a factor has no effect. Replace each remaining forbidden factor $u$ with all well-formed $k$-grams that contain $u$ as a substring. An occurrence of $u$ extends to one of these longer windows, including at either padded boundary, and every such longer window contains an occurrence of $u$. The extended grammar thus defines the same language at order $k$.] A string $w$ is in $L_1 \cap L_2$ if and only if it contains no forbidden factor from $\mathcal{F}_1$ *and* no forbidden factor from $\mathcal{F}_2$. But this is exactly the condition for $w$ to be in the SL-$k$ language with forbidden factors $\mathcal{F}_1 \cup \mathcal{F}_2$. So $L_1 \cap L_2$ is SL-$k$ with $\mathcal{F} = \mathcal{F}_1 \cup \mathcal{F}_2$. This is why we can specify a phonotactic grammar as a *collection* of forbidden $k$-grams: the language satisfying all constraints simultaneously is the intersection of the individual SL constraints, and that intersection is itself SL. Each forbidden $k$-gram contributes to a single unified forbidden-factor set. ```{python} #| code-fold: true #| code-summary: Combine multiple SL-2 constraints # Also forbid [mŋ] (bilabial nasal followed by velar nasal — doesn't occur in English) contains_mn = arcweight.VectorFst() s0 = contains_mn.add_state() s1 = contains_mn.add_state() s2 = contains_mn.add_state() contains_mn.set_start(s0) contains_mn.set_final(s2, 0.0) for p in phones: if p == 'm': contains_mn.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s1) else: contains_mn.add_arc(s0, sym_ids[p], sym_ids[p], 0.0, s0) for p in phones: if p == 'ŋ': contains_mn.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s2) elif p == 'm': contains_mn.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s1) else: contains_mn.add_arc(s1, sym_ids[p], sym_ids[p], 0.0, s0) for p in phones: contains_mn.add_arc(s2, sym_ids[p], sym_ids[p], 0.0, s2) no_mn = arcweight.difference(sigma_star, contains_mn) # Combine: strings with neither [ŋm] nor [mŋ] combined = arcweight.intersect(no_nm, no_mn) combined = arcweight.minimize(combined) print(f"Combined constraint states: {combined.num_states()}") ``` This is the sense in which SL grammars are *constraint-based*: we specify what is forbidden, and the language is whatever remains. ## Locally Testable languages Strictly Local grammars are stated in terms of *negative* constraints: certain factors are forbidden. That format does not let us express every positive requirement. For instance, suppose we require every word to contain at least one vowel. No fixed window can tell us that a vowel occurs somewhere in an arbitrarily long word, so this language is not SL.^[Some requirements at an edge can be restated as local prohibitions. The claim here concerns the unbounded requirement that a vowel occur somewhere, not every statement that happens to contain the word *require*.] *Locally Testable* (LT) languages generalize SL by allowing *Boolean combinations* of factor constraints—not just forbidden factors but required factors and arbitrary combinations thereof [@brzozowski1973characterizations; @rogers2013cognitive]. A language is LT-$k$ if membership can be determined by a Boolean formula over statements of the form "the $k$-gram $u$ appears in $\rtimes^{k-1} w \ltimes^{k-1}$." So "every word must contain at least one vowel" is LT-1: it's the constraint that at least one of the 1-grams from the set of vowels must appear. ::: {.callout-caution} ## Question Is the constraint "a word must contain at least one vowel" SL? Is it LT? ::: ::: {.callout-tip collapse=true} ## Answer It is not SL (for any $k$), because SL can only forbid substrings; it cannot require them. But it is LT-1: the constraint is that the set of 1-grams occurring in the word must include at least one vowel, which is a positive Boolean statement about factor occurrence. ::: Why can't some larger value of $k$ rescue the SL analysis? Reduce the alphabet to a consonant $c$ and a vowel $v$, and let $L$ contain exactly the strings with at least one $v$. Suppose for contradiction that $L$ is SL-$k$ for some fixed $k$. Choose $N\geq k$. The string $c^N$ is not in $L$, so its augmented representation must contain some forbidden $k$-gram $u$. Now consider $c^Nvc^N$, which belongs to $L$. Every $k$-gram in the augmented $c^N$ also occurs in the augmented $c^Nvc^N$: left-edge factors occur in the first $c$ block, right-edge factors occur in the second, and the interior factor $c^k$ occurs in both. In particular, $u$ occurs in $c^Nvc^N$. The proposed SL grammar would thus reject a string in $L$, a contradiction. Since the argument applies to an arbitrary $k$, no SL order can express the positive vowel requirement. LT properly contains SL: every SL language is LT because forbidding a factor is the negation of the statement "this factor appears," but not every LT language is SL because SL cannot express positive requirements. In practice, most phonotactic constraints are SL rather than LT because they tend to prohibit particular sequences rather than require a sequence to appear. But the distinction is important for understanding the full hierarchy.