Characterizations of locally testable events

AbstractLet Σ be a finite alphabet, Σ* the free monoid generated by Σ and χ the length of χ ∈ Σ*. For any integer k0, fk(χ) (tk(χ)) is χ if χ < k + 1, and it is the prefix (suffix) of χ of length k, othewise. Also let mk+1(χ) = {νχ = uνw and ν = k+1}. For χ, y ε Σ* define χ ∼ k+1 y iff fk(χ) = fk(y), tk(χ) = tk(y) and mk+1(χ) = mk+1(y). The relation ∼k+1 is a congruence of finite index over Σ*. An event E ⊆ Σ* is (k+1)-testable iff it is a union of congruence classes of ∼k+1. E is locally testable (LT) if it is k+1-testable for some k. (This definition differs from that of [6] but is equivalent.)We show that the family of LT events is a proper sub-family of star-free events of dot-depth 1. LT events and k-testable events are characterized in terms of (a) restricted star-free expressions based on finite and cofinite events; (b) finite automata accepting these events; (c) semigroups; and (d) structural decomposition of such automata. Algorithms are given for deciding whether a regular event is (a) LT and (b) k+1-testable. Generalized definite events are also characterized