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 $\mathcal{T}(k)$ the family of all $k$testable languages^{}, and $\mathcal{T}(\mathrm{\infty})$ the family of all locally testable languages, then
$$\mathcal{T}(\mathrm{\infty})=\bigcup _{k=0}^{\mathrm{\infty}}\mathcal{T}(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.
$\mathcal{T}(k)\subset \mathcal{T}(k+1)$ for any $k\ge 0$, and the inclusion is strict.

2.
$\mathcal{D}$ and $\mathcal{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.
$\mathcal{D}\subset \mathcal{T}(\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 $\mathcal{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 $\mathcal{T}(k)$, it is easily see that $\mathcal{T}(k)$ for all $k\ge 0$ including $k=\mathrm{\infty}$, is closed under complementation and intersection^{}, and hence all Boolean operations. The starclosure of $\mathcal{T}(\mathrm{\infty})$ is $\mathcal{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).
Title  locally testable 

Canonical name  LocallyTestable 
Date of creation  20130322 18:59:03 
Last modified on  20130322 18:59:03 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  7 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q45 
Classification  msc 68Q42 
Synonym  ktestable 
Defines  $k$testable 