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=x^{2} 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 G^{2} such that
p ~ q holds p = q.

2. for any SCC-node
( p, q) from G^{2} 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 G^{2}
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 G^{3}, (p, r) > ( q, r)
and (p, q) >(r, q) in G^{2},

then r = q.

Fig. for item 3.

next