Left, right local testability

Right [left] local testability

A right [left] locally testable language S is a language with the property that for some nonnegative integer k two words u and v in alphabet S are equal in the semigroup if
(1) the prefix and suffix of the words of length k coincide,
(2) the set of segments of length k-1 of the words as well as
(3) the order of the first appearance of these segments in prefixes [suffixes] coincide.


The third condition of the definition differs from the local testability definition.

Right [left] local testability was introduced and studied by Garcia and Ruiz. They prove that

A finite semigroup S is right [left] locally testable iff it is locally idempotent (x=x2 in eSe) and locally satisfies the identity xyx=xy [xyx=yx] (in eSe).




We find necessary and sufficient conditions of right and of left local testability

THEOREM
Let S be transition semigroup of deterministic finite automaton with state transition graph G. Then S is right locally testable iff
1. for any SCC-node (p, q) from G2 such that p ~ q holds p = q.
2. for any SCC-node ( p, q) from G2 and s in S from ps > q follows qs > q.


THEOREM
Let S be transition semigroup of a deterministic finite automaton with state transition graph G. Then S is left locally testable iff
1. S is locally idempotent,
2. for any SCC-node (p, q) of G2 such that p > q and for any s in S we have ps> q iff qs >q and
3. If for arbitrary nodes p, q, r from G the node (p, q, r) is SCC-node of G3, (p, r) > ( q, r) and (p, q) >(r, q) in G2,
then r = q.


Fig. for item 3.


next