locally testable

A regular language $L$ over an alphabet $\mathrm{\Sigma }$ is locally testable if, loosely speaking, testing whether or not an arbitrary word $u$ (over $\mathrm{\Sigma }$) is in $L$ is completely determined by its subwords of some fixed length. The name locally testable comes from the fact that properties of $u$, and not $L$, determine the membership of $u$ in $L$.

To formalize this notion, we first define, for any word $u$ over $\mathrm{\Sigma }$, the set ${\mathrm{sw}}_k(u)$ of all subwords of

$$\mathrm{\#}u\mathrm{\#}$$

of length $k$, where $\mathrm{\#}$ is a symbol not in $\mathrm{\Sigma }$.

Definition. We say that a regular language $L$ is $k$-testable if for any $u,v\in {\mathrm{\Sigma }}^{*}$ such that

$${\mathrm{sw}}_k(u)={\mathrm{sw}}_k(v),$$

we have $u\in L$ iff $v\in L$. The equation above says three things at once:

• the set of subwords of $u$ of length $k$ is equal to the set of subwords of $v$ of length $k$,

• the prefix of $u$ of length $k$ is equal to the prefix of $v$ of length $k$, and

• the suffix of $u$ of length $k$ is equal to the suffix of $v$ of length $k$.

We say that $L$ is locally testable if it is $k$-testable for some $k\ge 0$.

If we denote $𝒯(k)$ the family of all $k$-testable languages, and $𝒯(\mathrm{\infty })$ the family of all locally testable languages, then

$$𝒯(\mathrm{\infty })=\bigcup _{k=0}^{\mathrm{\infty }}𝒯(k).$$

Note that there are only two $0$-testable languages: ${\mathrm{\Sigma }}^{*}$ and $\mathrm{\varnothing }$.

Proposition 1.

Let $\mathrm{D}$ be the family of definite languages. Then

1. $𝒯(k)\subset 𝒯(k+1)$ for any $k\ge 0$, and the inclusion is strict.

2. $𝒟$ and $𝒯(k)$ are not comparable for any $k>0$. In other words, for every $k$, there is a $k$-testable language that is not definite, and a definite language that is not $k$-testable.

3. $𝒟\subset 𝒯(\mathrm{\infty })$, and the inclusion is strict.

We only sketch the proof here. For the first assertion, note that for every $k\ge 0$,

$${\mathrm{sw}}_{k+1}(u)={\mathrm{sw}}_{k+1}(v)\mathit{\hspace{1em}}\text{implies}\mathit{\hspace{1em}}{\mathrm{sw}}_k(u)={\mathrm{sw}}_k(v).$$

In addition, the language ${\{a{b}^k\}}^{*}$ is $(k+1)$-testable but not $k$-testable. For the second statement, note that ${\{a{b}^k\}}^{*}$ is not definite for any $k\ge 0$. On the other hand, a finite language containing a single word of length $k+1$ is not $k$-testable. The last assertion is a direct consequence of the second one.

Thus, the families $𝒯(k)$ provide us with an example of an infinite chain of subfamilies of the family of regular languages.

With regard to the closure properties in $𝒯(k)$, it is easily see that $𝒯(k)$ for all $k\ge 0$ including $k=\mathrm{\infty }$, is closed under complementation and intersection, and hence all Boolean operations. The star-closure of $𝒯(\mathrm{\infty })$ is $ℛ$, the family of all regular languages.

Remark. Every locally testable language is star-free, but not conversely.