You are here
Homelocally testable
Primary tabs
locally testable
A regular language $L$ over an alphabet $\Sigma$ is locally testable if, loosely speaking, testing whether or not an arbitrary word $u$ (over $\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 $\Sigma$, the set $\operatorname{sw}_{k}(u)$ of all subwords of
$\#u\#$ 
of length $k$, where $\#$ is a symbol not in $\Sigma$.
Definition. We say that a regular language $L$ is $k$testable if for any $u,v\in\Sigma^{*}$ such that
$\operatorname{sw}_{k}(u)=\operatorname{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\geq 0$.
If we denote $\mathscr{T}(k)$ the family of all $k$testable languages, and $\mathscr{T}(\infty)$ the family of all locally testable languages, then
$\mathscr{T}(\infty)=\bigcup_{{k=0}}^{{\infty}}\mathscr{T}(k).$ 
Note that there are only two $0$testable languages: $\Sigma^{*}$ and $\varnothing$.
Proposition 1.
Let $\mathscr{D}$ be the family of definite languages. Then
1. $\mathscr{T}(k)\subset\mathscr{T}(k+1)$ for any $k\geq 0$, and the inclusion is strict.
2. $\mathscr{D}$ and $\mathscr{T}(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. $\mathscr{D}\subset\mathscr{T}(\infty)$, and the inclusion is strict.
We only sketch the proof here. For the first assertion, note that for every $k\geq 0$,
$\operatorname{sw}_{{k+1}}(u)=\operatorname{sw}_{{k+1}}(v)\quad\mbox{implies}% \quad\operatorname{sw}_{k}(u)=\operatorname{sw}_{k}(v).$ 
In addition, the language $\{ab^{k}\}^{*}$ is $(k+1)$testable but not $k$testable. For the second statement, note that $\{ab^{k}\}^{*}$ is not definite for any $k\geq 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 $\mathscr{T}(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 $\mathscr{T}(k)$, it is easily see that $\mathscr{T}(k)$ for all $k\geq 0$ including $k=\infty$, is closed under complementation and intersection, and hence all Boolean operations. The starclosure of $\mathscr{T}(\infty)$ is $\mathscr{R}$, the family of all regular languages.
Remark. Every locally testable language is starfree, but not conversely.
References
 1 A. Salomaa, Formal Languages, Academic Press, New York (1973).
Mathematics Subject Classification
68Q45 no label found68Q42 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections