locally testable


A regular language L over an alphabet Σ is locally testable if, loosely speaking, testing whether or not an arbitrary word u (over Σ) 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 Σ, the set swk(u) of all subwords of

#u#

of length k, where # is a symbol not in Σ.

Definition. We say that a regular language L is k-testable if for any u,vΣ* such that

swk(u)=swk(v),

we have uL iff vL. 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 k0.

If we denote 𝒯(k) the family of all k-testable languagesPlanetmathPlanetmath, and 𝒯() the family of all locally testable languages, then

𝒯()=k=0𝒯(k).

Note that there are only two 0-testable languages: Σ* and .

Proposition 1.

Let D be the family of definite languages. Then

  1. 1.

    𝒯(k)𝒯(k+1) for any k0, and the inclusion is strict.

  2. 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. 3.

    𝒟𝒯(), and the inclusion is strict.

We only sketch the proof here. For the first assertion, note that for every k0,

swk+1(u)=swk+1(v)impliesswk(u)=swk(v).

In addition, the language {abk}* is (k+1)-testable but not k-testable. For the second statement, note that {abk}* is not definite for any k0. 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 k0 including k=, is closed under complementation and intersectionMathworldPlanetmath, and hence all Boolean operations. The star-closure of 𝒯() is , the family of all regular languages.

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

References

Title locally testable
Canonical name LocallyTestable
Date of creation 2013-03-22 18:59:03
Last modified on 2013-03-22 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 k-testable
Defines k-testable