Left, right 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
Right [left] local testability
(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
The third condition of the definition differs from the local testability
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]
We find necessary and sufficient conditions of right
and of left local testability
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.
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.