A Procedure for K-Local Testability
Antonio Magnaghi, Hidehiko Tanaka?F'>0,-6$0$ KLGKTOMS LPUVMNQSQVWHoAnm[_v=*F.D#(0$7D&=#zcrniXvB KLo5-F@n¡n¥zlcrniXvB,8=@),n`nsZlz¨©j,1=@),n£n¦°m² cvj`x\tpeA&<Fª¬\tberniXvB`woA§m[_vJISTOMSSWIVPUVMNSPF
n¡jAKLRUCUCnm[_v®0(3/(n!mgYh~°zXyderniXvB`n¡n "msuA­±¯mKLRUCUm+@(?-/.D;4%2msvl³¯#9?F.zcv l^A,1=@),]fhYv\kZ\¤\qv ]!mlvBatm¢EnoKLRUCUCn{|n®´jmgl]fh[uARISTOMSSWIVPUVM
NSPnsZl5<:F-FRG}n«Hpi®§cvcv ]!mlvB
A Procedure for K-Local Testability
Antonio Magnaghi, Hidehiko Tanaka
Graduate School of Electrical Engineering
The University of Tokyo
7-3-1 Bunkyo-ku, Tokyo 113, Japane-mail:fmagnaghi,tanakag@mtl.t.u-tokyo.ac.jp

The concept of local testability (LT ) represents an active area of research in the eld offormal languages. LT has its roots in the study of pattern recognition. Interest in such aproperty springs both from theoretical and applied concerns about parallel parsing of stringsand error detection. This paper focuses on the class of k-locally-testable languages in a strict
sense (LTk s:s:) and on a possible decidibility technique for LTk s:s: property. We prove a
decidibility algorithm, basing directly on speci c structural properties of LTk s:s: Such a result enables to ascertain whether a string language is in LTk s:s: in a direct manner, without
adopting the elaborated algebraic approach of the syntactic monoid. In addition, our method
strictly relates to the problem of determining the order of a LTk s:s: language, being the orderde ned as the smallest value of the parameter k such that the language is k-locally-testable.

1The proposed algorithm employs convenient setsof k-length strings associated to the nodes of an accepting automaton for the language L, and throughthe analysis of their set-theoretical characteristics
it clari es those properties required to guarantee
LTk s:s: This approach presents some worthwhileadvantages. In addition to its simplicity, it allows
to obtain other interesting results about LTk s:s:in a straightforward way, whereas without it somemore considerations would be needed. Our method
relates directly to the problem of determining theorder of a LTk s:s: language, being the order dened as the smallest value of the parameter k suchthat the language is k-locally testable. The orderof an automaton, equivalently of the accepted language, clearly emerges to be dependent on intersection properties of paths that start at di erent nodes
and are labeled through the same string of symbols.
Hence a topological aspect is directly related to theset of strings employed for the syntactic analysis ofa testable sentence.
The extension of these considerations to tree languages is a relevant aspect to investigate. Generally the diculties encountered in such an e ort
are also due to the impossibility of an immediate
extension of the conceptual and formal tools developed in the string case. As the proposed decidibility algorithm does not utilize the syntactic monoid
approach and its algebraic properties, it might givesome insights on how to adapt our considerations
to tree languages.
2. Basic de nitions
LT has its roots in the study of pattern recognition. Intuitively let x be a string composed byconcatenating letters from an alphabet. The recognition procedure is carried out on x through a window of xed arbitrary length to be moved along thestring. The sequences of symbols observed throughthe window are annotated in a record, regardlessof the order in which they are met and of the position they occupy in the string. After moving thewindow from one end to the other, x is accepted or
rejected basing on the set of substrings that compose the produced record. Local testing proved to
be a general concept, able to capture many situations.
The recognition procedure described above canbe modi ed and generalized to a variety of contexts: De nite, Reverse-De nite, Generalized-

1. Introduction
The concept of local testability (LT ) has beenbroadly investigated in the previous decades, andit still represents an active area of research in theeld of formal languages.
LT has its roots in the study of pattern recognition. It is possible to identify two main researchthreads. One of them is concerned with linear sequences of symbols, i.e. string languages, whereas
the other analyzes more articulated structures, suchas, for instance, images and tree languages7),10),11).
In the case of strings the wider class of Aperiodic Languages constitutes the formal frameworkfor LT 2),8) . Aperiodicity reveals to be a linguistic
universal, characterized in a variety of ways: grammatical inference4) , neural networks8) and algebraic
structures2),3),8),12) . The importance of LT springs
from its close link to aperiodicity. Requiring locally testable class (LT ) to be closed w.r.t. concatenation leads to aperiodic languages. A hierarchy of aperiodic languages was identi ed2) imposing di erent constrains on the recognition processof strings. It comprises De nite, Reverse De nite,
Locally Testable in a Strict Sense, Locally Testableand properly Aperiodic or Non-Counting languages
at the top of the taxonomy.
This paper focuses on the class of k-locallytestable languages in a strict sense (LTk s:s:) and on
a possible decidibility algorithm for LTk s:s: property. Interest in local testability in a strict sense relies on both theoretical and applied concerns about
parallel parsing of strings and error detection.
A systematic characterization of the di erent sub
families of aperiodic languages was presented in the
past1),3) and decidibility algorithms for them were
formulated1),5) . However, the result was quite difcult and moreover for the speci c case of Local
Testability in a strict sense (LT s:s:) the decidibility
problem is solved in only an indirect way, througha modi cation of a more general and complex procedure for LT . This paper reports on our e orts toprove a di erent decidibility technique, relaying directly on speci c structural properties of LTk s:s: A
necessary and sucient condition is formulated for
LTk s:s: By these means it is possible to ascertain
whether a string language is in LTk s:s: in a directmanner, without adopting the elaborated algebraic
approach of the syntactic monoid.

2

a decomposition. In particular k ; k ; k containthe recognition patterns to utilize in order to ascertain whether the string belongs to L or not. k can
be interpreted as the set containing all possible klength pre xes of strings of L. Dually, k is the setof all acceptable k-length suxes. k is the set of
all acceptable internal k-length sub strings of wordsof L. It should be noted that no information aboutorder or relative position of occurrence is kept.
Locality property shows a link to parallel parsing of string languages. A word of a local language
has such a syntactical structure that allows to analyze each sub string independently from all theothers. Hence, it is possible to decompose the input sentence among computational units of a parallel computer to simultaneously recognize the different parts, substantially improving parsing performance. Moreover, another feature emerges for
LT s:s: languages in relation to error identi cation.
The presence of a syntax error is easy to detect andits position is precisely de ned as well: it is locatedwithin the k-length sub string that does not matchany element of k ; k ; k . On the contrary, in thegeneral case when LT s:s: property does not hold,error handling is more complex.
De nition (4) does not consider strings of L consisting of a number of symbols less than k. In thiscase the number of possible words is limited, so
parsing can be performed separately in a simpleway.
As an example of LTk s:s: language, let us consider the set of words over 6 = fa; bg such thatevery possible occurrence of letter a is immediately
followed by the string bb: abbb, bbb are correct
words; ababb, ba are not. The de ned language
is in LTk s:s: for k=3,4,5,: : : If we de ne, over thesame alphabet, the language whose words containan even number of occurrences of symbol a, local
testability property never holds for any value of k,
because the involved constraint is not local.

De nite, Locally Testable in a strict sense (LT s:s:),Locally-Testable (LT ) and Aperiodic languages. In
this section, basing mainly on the work of McNaughton and Papert8) , we will present the definition of k-Locally Testability in a strict sense(LTk s:s:) and some of its properties essential to thefollowing considerations.
Let 6 be a nite alphabet of symbols, and let
63 denote the free monoid over 6, including all thestrings obtained by concatenation of alphabet elements. A subset L of 63 is a string language, ora string event, over 6. If L de nes a regular set,i.e. it can be characterized through a regular expression, the language L is a regular language andit can be recognized by a nite state automaton M .
Being k a non-negative integer number, it is possible to de ne the following operators on a string xof length greater or equal to k:
x = a1 a2 : : : an (ai 2 6; 1  i  n; n  k)
Lk (x) = fy : x = yw ^ jy j = kg
(1)
Rk (x) = fw : x = yw ^ jwj = kg

(2)

Ik (x) = fw : x = ywz^y; w; z 6= ^jwj = kg(3)The operator Lk (x) extracts the k-length pre xfrom input string. Symmetrically, Rk (x) produces
the k-length sux of word x. Equation (3) de nes
the set of properly internal k-length sub strings ofx. If the length of x (denoted by jxj) equals k or(k+1), Ik (x) is the empty set.
Let k , k , k be sub sets of 6k : they are sets ofstrings over 6 whose length is k.
The language L is k-locally testable in a strict
sense (L 2LTk s:s: ) if sets k , k , k exist such thatfor every x 2 63 (jxj  k):(x 2 L) ()(Lk (x) 2 k ^ Ik (x)  k ^ Rk (x) 2 k ) (4)The remainder of this paper will focus on the problem of deciding whether a language L is in LTk s:s:or not. We will assume L to be de ned through adeterministic nite state automaton (DFA) M . After establishing the decidibility result for LTk s:s:
property, we will also be able to obtain a procedure
to determine the order of the language.

Basing on relation (4), a k-locally testable language in a strict sense has the property that syntactic analysis can be performed locally. On a procedural level, parsing activity requires to extractfrom string x its pre x (Lk (x)), sux (Rk (x)) andthe set of internal sub strings (Ik (x)). Recallingthe initial window analogy, x can be parsed by a kletters-wide loophole to be moved from left to rightend one symbol at a time. Correctness is evaluatedusing only the information collected through such

Before concluding this section, a theorem isstated expressing an upper bound to parameter3

k value for LTk s:s: property. It is a direct consequence of what was proved by Brzozowski andSimon1) , adapted to our framework. Such a result will allow us to show in the next section how
LTk s:s: decidibility leads to an algorithm for LT s:s:
decidibility and for language order identi cation.
Theorem1 Let M be a DFA accepting a language L in LT s:s: , and let k = n + 1, being n thenumber of states of M . Then M is LTk+1 s:s:Dk (qi ; x) = fy = xu 2 Vk+1 (qi ) :u 2 6 [ fgg; if jxj = k(6)

Dk (qi ; x) = ;; if jxj = (k 0 1)

(7)

Dk (qi ; x) consists of the strings whose k-pre x
equals x and that are produced by a chain of (k+1)
derivations from < qi >.
Lemma1 x 2 Dk (qi ; x) i (qi ; x) 2 F
Proof

3. Notations
Let M = (Q; 6; ; q0 ; F ) be a DFA accepting L:
Q is the set of states, 6 the input alphabet,  thetransition function, q0 2 Q the initial state andF  Q a non empty set of nal states. For any
q 2 Q and x 2 63 ,  (q; x) denotes the resulting
state when input string x is applied to M in stateq.
Let G = (V; 6; P; < q0 >) be the linear rightderivative context-free grammar associated univocally to M as follows:( 1 ) the set V of non terminals contains a symbolfor every state of M:
V = f< q >: q 2 Qg
( 2 ) the terminal alphabet 6 of G equals the input alphabet 6 of M
( 3 ) the set P of linear productions of G is:
P = f< q1 >! a < q2 >: q1 ; q2 2 Q ^^a 2 6 ^ (q1; a) = q2g [[f< qf >!  : qf 2 F g( 4 ) the axiom of the grammar < q0 > corresponds to the initial state q0 of M.
Let  be the omomorphism whose domain andimage are respectively (6 [ V )3 , 63 :x belongs to Vk (qi ) , hence its length can be either(k-1) or k.
A generic string in Dk (qi ; x) consists necessary ofk or (k+1) symbols. By hypothesis, x 2 Dk (qi ; x),
therefore jxj = k. In de nition (6), the symbol u
must equal : thus x 2 Vk+1 (qi ) . The unique way
to obtain a string of k letters by (k+1) derivationsin G is to require that the last derivation is terminal: < qi >=k) x < qj >=1) x, where < qj >! .
If the rule < qj >!  is included in the set of productions of G, then qj 2 F :  (qi ; x) = qj 2 F .
2
4. Decidibility procedure for LTk s:s:
In this section we will propose a possible algorithm to decide if a regular language L is in LTk s:s:for a xed value of k. The adopted approach willallow us to answer (with \yes" or \not") to thequestion: \Is L k-locally testable in a strict
 sensein the case k equals a speci c number k ?". Sucha formulation corresponds to the decision-problem
derived from the optimization-problem about theorder of L.
We assume that the language L is given throughan automaton accepting it. A regular language cangenerally be recognized by di erent automata: only
its minimal accepting automaton is unique, neglecting isomorphisms that rename its states. An interesting aspect will emerge from the remainder. Our
procedure works correctly regardless of the particular representation of the accepting automaton M ,allowing us to speak of a LTk s:s: language L orequivalently of LTk s:s: property of an arbitrary automaton accepting L. In particular we will not require M to be reduced, whereas many results available in literature focus on the minimal automaton
accepting L.
More precisely, let the language L be de ned
through a DFA, that does not contain unreachable
states from the initial node q0 or states from which (a) = a; 8a 2 (6 [ fg)
 (< qj >) = ; 8qj 2 Q
 (xy) =  (x)(y); 8x; y 2 (6 [ V )3

For any state qi of M and for any integer k, thefollowing set of strings is de ned:Vk (qi ) = f (!) :< qi >=k) !g(5)
Vk (qi ) is the set of all words obtained throughthe application of (:) to derivations of length kstarting from the non terminal < qi >. If the lastderivation to produce ! is not terminal j(! )j = k,otherwise j (!)j = (k 0 1).
For every qi 2 Q and for every x 2 Vk (qi ) , let us
de ne the set Dk (qi ; x) :4
us consider
 the following states: qi =  (qi ; x); qh = (qh ; x); qi 0=  (qi ; tk ); P = (qh ; tk ). Basing on
the characteristic of M , that is without uselessstates when evaluating Dk01 (qi ; x) and Dk01 (qh ; x)
(P is not added in that context), from qi 0 a nal state qf is reachable through the string z =c1 c2 : : : cs ; (s  0) : (qi ; z ) = qf 2 F . Now, let us
consider the word w = w2 yz, where the length of
w is greater or equal to k.  (q0 ; w2 y) = P implies (q0 ; w2 yz ) =  (q0 ; w) = P , hence w 2= L.

it is not possible to reach a nal state qf 2 F . Under these assumptions, the transition function  will
generally be a partial function over Q 2 6.
Before proceeding, the following sets are introduced for language L:= fx : w = xy^jxj = k^w 2 Lg(8)= fv : w = uvz^u; z 6= ^jvj = k^w 2 Lg(9)g(10)
k = fy : w = xy ^jy j = k ^w 2 Lkk

It is clear that, if L 2 LTk s:s:, through k ; k ; ksyntactical analysis can be correctly carried out.
On the contrary, if L 2= LTk s:s:, the language recognized through such sets is a super set of L.
Theorem2 Let L be LTk s:s:, then every DFA
M accepting L is such that:
Dk01(qi ; x) = Dk01(qh ; x)for any qi ; qh 2 Q, for any x 2 Vk01(qi ) \ Vk01 (qh ).

Let us consider Lk (w), two cases are possible:(a)if n  k, Lk (w) = b1 b2 : : : bk , (b)if 0  n < k,Lk (w) = b1 b2 : : : bn t1 t2 : : : tl , where n + l = k; 1 l  k.
(Case a)  (q0 ; w2 ) = qh , and from qh a nal
state qf 0 is reachable, hence from (q0 ; b1 ; b2 : : : bk )the same node qf 0 is reachable. As a consequence,b1 b2 : : : bk is the pre x of a string in L, hence because of (8) Lk (w) 2 k (n  k).
(Case b)The condition x = t1 t2 : : : tk 2
Vk01 (qh ) guarantees that for any state: ql = (q0 ; w2 t1 t2 : : : tl ); 1  l  k, a path exists leading
to a nal state of M from ql . Hence, it is possible
to conclude again that Lk (w) 2 k (0  n  k).

Proof

For convenience reasons, a new non nal state P(2= Q) is introduced in order to let  become a total
function over (Q [ fP g) 2 6. From a state qi 2 Q
now transitions are de ned in correspondence of every a 2 6: (qi ; a) = P if previously there was noedge leaving qi with label a. P is an adsorbing statein the sense that (P; a) = P for any a 2 6, andbeing P not nal, if it is reached, it means thatthe input x contains a syntactic error, causing therejection of the string. The introduction of P does
not alter the generality of the considerations below.
It will be proved that L 2= LTk s:s: if there exist
two distinct states qi ; qh and a string x such that:x 2 Vk01 (qi ) \ Vk01 (qh )Dk01(qi ; x) 6= Dk01(qh ; x)

Let us consider Rk (w). (a)if s  k, Rk (w) =cs+10k cs+20k : : : cs ; (b)if 0  s < k, Rk (w) =tl tl+1 : : : tk c1 c2 : : : cs ; 1  l  k. Both in case (a)and (b) we can prove that Rk (w) 2 k in a fashion
similar to the one used for Lk (w).
Finally it is also possible to verify that Ik (w) 
.

(11)
(12)

k

Hence if conditions (11), (12) simultaneously
hold, a string w exists such that x 2= L, but for
which: Lk (w) 2 k ; Ik (w)  k ; Rk (w) 2 k . Thus
we conclude L 2= LTk s:s.
2

If jxj = (k 0 2), then Dk01 (qi ; x) = Dk01(qh ; x) =; because of de nition (7). Hence, necessarily
jxj = k 0 1.
Let x have the form: x = t1 t2 : : : tk01 ; 1  i 
k 0 1; ti 2 6. Condition (12) implies that qi 6= qh
and that at least one of the sets (Dk01 (qi ; x) 0
Dk01(qh ; x)); (Dk01(qh ; x) 0 Dk01 (qi ; x)) is not
empty. For instance, let y belong to Dk01 (qi ; x) 0
Dk01(qh ; x) : y = xtk (jyj = k). As y 2=
Dk01(qh ; x),  (qh ; y ) = P . Being M deterministic, and qi 6= qh , there must be two di erent strings
w1 ; w2 that lead from q0 to qi and qh respectively:
 (q0 ; w1 ) = (q0 ; a1 a2 : : : am ) = qi ;  (q0 ; w2 ) = (q0 ; b1 b2 : : : bn ) = qh , where m; n  0, but not
both of them can equal zero, and w1 6= w2 . Let

In order to prove theorem 2, a preliminary lemma
is required.
Lemma2 Let M be a DFA such that:Dk01 (qi ; x) = Dk01(qh ; x)for any qi ; qh 2 Q and for any x 2 Vk01 (qi ) \Vk01 (qh ). Then the state (qi ; x) is equivalent to (qh ; x).
Proof

Also in this case, it can be convenient to introduce5

w 2 L ) L k (w ) 2

the state P (see proof of theorem 2), in order not
to distinguish tedious particular cases in the considerations below.
Let x = a1 a2 : : : ak 2 Vk01(qi ) \ Vk01 (qh ), andlet
us assume that qi =  (qi ; x) is not equivalent to
qh = (qh ; x). This implies the existence of a stringy = b1 b2 : : : bm (m  0) such that (qi ; y) 2 F and (qh ; y) 2= F or (qi ; y) 2= F and (qh ; y ) 2 F .
Considering for instance the rst possible case, letz = xy (jzj  k), and i (resp. h ) be the path comprising the edges of M used by the involved transitions from qi (resp.qh ) to (qi ; z) (resp.  (qh ; z)):i = (qi ;  (qi ; a1 ))( (qi ; a1 ); ( (qi ; a1 ); a2 )) : : :((qi ; a1 a2 : : : ak b1 b2 : : : bm01 ); bm )(resp:h = (qh ;  (qh ; a1 ))( (qh ; a1 ); ( (qh ; a1 );a2 )) : : : ((qh ; a1 a2 : : : ak b1 b2 : : : bm01 ); bm ))With qi 0 (resp. qh 0) we designate the node at a
distance of (k-1) edges from (qi ; z ) (resp.  (qh ; z))
alongthe path i (resp. h ). As jzj  k, qi 0 (resp.

qh 0) exists, and x is the (k-1)-sux  of zsuch that: (qi 0;x) =  (qi ; y ) (resp.
(qh 0; x ) =  (qh ; y )). We
notice that x2 Vk01 (qi 0) \ Vk01 (qh 0), howeverthe
set equalityDk01 (qi 0; x ) = Dk 01 (qh 0; x) does not
hold.  (qi 0; x) =  (qi ; y )2F , hence lemma 1 guarx
xantees that 2 Dk01(qi 0; ). On the other hand,being (qh 0; x) =  (qh ; y ) 2= F; x 2= Dk01 (qh 0; x)(lemma 1). This represents a contradiction: necessarily  (qi ; x) is equivalent to (qh ; x).
2

Lk (w) 2kk^Ik (w)  k ^Rk (w) 2 k^Ik (w)  k ^Rk (w) 2 k ) w 2 L

Because of (8), (9), (10) the rst of them holds ina straightforward manner, whereas the second one
requires additional considerations.
Let w be a string of this form: w =a1 a2 : : : am (m  k), with the property that
Lk (w) 2 k ; Ik (w)  k ; Rk (w) 2 k . Our aim
is to show that w is syntactically correct. Let qr be
the state of M reached from q0 through a1 a2 : : : ar ,r-pre x of w: qr =  (q0 ; a1 a2 : : : ar )(1  r  m).
In the general case  is not a total function overQ 2 6, and w is a sentence of L i the following
conditions hold: transition
 (qr ; ar+1 )is de ned for any 0  r  m 0 1,
 and

(13)

qm 2 F(14)
As a rst step, condition (13) will be proved bycomplete induction on r.
Extending the terminology from one letter input
to a i-letters string (i > 1), we will say that
 (qr ; ar+1 ar+2 : : : ar+i01 ) is de ned if all the following transitions are de ned: (qr+j ; ar+1+j );0 j  i 0 2.

(Base of induction: r=0)
Lk (w) = a1 a2 : : : ak 2 k . Recalling the de nitionof k (8), a string y exists such that y is in L andits k-pre x is a1 a2 : : : ak , hence  (q0 ; a1 ) is de ned,being y correct.

We can derive the following result as immediate
consequence of previous lemma:
Corollary1 Let M be a reduced DFA suchthat:
Dk01(qi ; x) = Dk01(qh ; x)for any qi ; qh 2 Q and for any x 2 Vk01 (qi ) \Vk01 (qh ). Then  (qi ; x) equals (qh ; x)

(Inductive assumption)
Let us assume that  (qj ; aj +1 ) is de ned for 1 j  r 0 1, where 1  r  m 0 1.

It is now possible to proceed to theorem 3: itproves the validity of exchanging hypothesis andthesis in theorem 2.
Theorem3 Let M be a DFA such that:
Dk01(qi ; x) = Dk01(qh ; x)for any qi ; qh 2 Q and for any x 2 Vk01 (qi ) \Vk01 (qh ). Then the language accepted by M is
LTk s:s: w.r.t. k ; k ; k .

(Inductive step)
Now it is required to show that the inductive assumption holds also for j = r. Two di erent cases
are considered.
(Case a: 1  r  k 0 1) Lk (w) = a1 a2 : : : ak 2 k .
Basing on the same considerations expressed previously (Base of induction), it is possible to conclude
that  (qj ; aj+1 ) is de ned for any 1  j  k 0 1.
(Case b: k  r  m 0 1) Let u be the stringof (k-1) symbols: ar0k+2ar0k+3 : : :ar , and let v
be uar+1 . v is a k-length sub string of the in-

Proof

Recalling the de nition of LTk s:s: language (4), two
implications must be veri ed, being w 2 63 ; jwj k:6

put string w. It belongs to ( k [ k ), its initialcharacter ar0k+2 is at least the second one: it occurs in position number (r-k+2) from left, whichis greater or equal to 2. Hence a string y in L
exists such that v 2 Ik (y) or v = Rk (y ). In bothqcases, we canconsidertwostates  and q0 such that:u 2 Vk01( q ); q0=  ( q ; u). From q0 the output transition  (q 0; ar+1 ) is necessarily de ned because all
the transitions in the sequence ( q ; v) are de ned(v 2 Ik (y ) or v = Rk (y )) and  (q 0; ar ) =  ( q ; v). Inductive assumption assures that (qr0k+1; u) is correctly de ned,that
 hence it is possible to guaranteeu 2 Vk01( q ) \ Vk01 (qr0k+1 ), being q and qr0k+1
possibly equal. Nonetheless, the hypothesis imposes the equality: Dk01( q ; u) = Dk01 (qr0k+1; u).
We know that v is in Dk01 ( q ; u), hence v belongs
also to Dk01 (qr0k+1; u), therefore  (qr0k+1; v) isde ned and we nally get that (qr ; ar+1 ) is dened.

L is in LTk00 s:s: where k00 < k . The order of alanguage is de ned as the minimum value of theparameter k such that L is in LTk s:s: In the
more general case of Locally Testable class (LT ),it is known that the analogous problems is NPHard5) . As concerns LT s:s: languages, no explicit
result is available in literature about the complexity class of the problem. Our approach consists inxing the parameter k and in formulating the decision problem corresponding to the question: \Is
L in LTk s:s:?". In previous section, a decidibility procedure was proved. Hence it is possible toimmediately obtain a decidibility algorithm for thedi erent problem: \Is L in LT s:s:?". Such a resultbases on theorem 1, that expresses an upper boundto use when ascertaining local testability.
The approach we adopted presents the advantagethat the same procedure can be employed for two
di erent problems, respectively a decidibility andan optimization one. It allows us to decide if L isin LT s:s:, basing on theorem 1, and secondly to
It remains to prove condition (14):  (q0 ; w) =evaluate
kmin , such that L is in LTk s:s: , i.e.
qm 2 F . Rk (w) = am0k+1 am0k+2 : : : am 2 k . Let
the
order
of L.
us consider the states: qm0k+1 = (q0 ;a1 a2 : : :am0k+1 )Let
usconsidera language L and one of its acand qm =(qm0k+1 ; am0k+2 am0k+3 : : :am ). The
cepting
automata,
comprising n states. If L is instring am0k+1 am0k+2 : : : am is in k , therefore a
LT
s:s:
,
then
it
necessarily
is in LTn+2 s:s: (thestring y of L exists such that am0k+1 am0k+2 : : : am
orem
1).
It
is
possibletotest whether such ais its k-length sux. Being y in L, a state
conditionholds
byapplying
theresult we proved
q exists: ( q ; am0k+2 am0k+3 : : : am ) = qf 2
about
LT
s:s:
decidibility(theorem4) consideringkF.
In particular:  am0k+2 am0k+3 : : : am 2
k
=
n
+2.
If
the
responseisnegative,then it means
Vk01 (qm0k+1 ) \ Vk01 ( q ). Basing on lemma 2, the
L
is
not
LT
s:s:
for
any
value
of
k.
In
case the rek
state (qm0k+1 ; am0k+2 am0k+3 : : : am ) is equivasponseisarmative,
thisprovesLisLT
s:s:, thus
lent to  ( q ; am0k+2 am0k+3 : : : am ). Therefore, qm
itispossibletoproceedtodetermine
theorder ofis equivalent to qf : qm belongs to F .
L.
By
iteratingthe
test
expressedintheorem4,2and decreasing each time the value of parameter k
by unit, the minimal value kmin is produced such
Theorems 2 and 3 lead us to directly obtain thethat
L 2 LTk , as illustrated in the fragment of
main result of this section, characterizing LTk s:s:
pseudocode below.
Theorem4 A language L, accepted by a DFA
M , is LTk s:s: i Dk01 (qi ; x) = Dk01 (qh ; x) for any
int order(automaton M=(N,E))
qi ; qh 2 Q and for any x 2 Vk01(qi ) \ Vk01 (qh ).
min

min

min

{
int upper_bound=|N|+2;
int k=upper_bound;boolean is_k_testable=TRUE;

The following corollary is a straightforward consequence of theorem 3 and corollary 1:
Corollary2 A language L, accepted by the reduced DFA M , is LTk s:s: i (qi ; x) = (qh ; x) for
any qi ; qh 2 Q and for any x 2 Vk01 (qi ) \ Vk01 (qh ).
5. Order of a LTk s:s: language
If L is in LTk s:s:, clearly it is also in LTk0 s:s:,with k0 > k. However, in general it is not true thatfor(;k>0;--k){
is_k_testable=test_condition(M,k);/* verify condition of theorem 4*/
if((!is_k_testable)&&(k==upper_bound))7

of locally testable events. Discrete Mathemat-

ics, Vol. 4, 1973, pp. 243-271
2) J. A. Brzozowski. Hierarchies of aperiodic languages. R.A.I.R.O. Information Theorique (vol.
10, No. 8, ao^ut 1976, pp. 33-49)
3) R. S. Cohen, J. A. Brzozowski. Dot-depth ofstar-free events. J. Computer and System Sc.,
Vol. 5, 1971, pp. 1-16
4) S. Crespi-Reghizzi, M. A. Melkano , L.
Lichten. The use of grammatical inference
for designing programming languages. Comm.
ACM 16, 2 (Feb. 1973), pp. 83-90
5) S. M. Kim, R. McNaughton, R. McCloskey.

return(-1);/*M in not in LTs.s.
for any value of k*/else if(!is_k_testable)/*M is in LTs.s., hence theorder will be evaluated*/
return(k+1);/*Not possible todecrease k further*/};return(1);/*M is 1-testable: M is the whole
free monoid*/}

A polynomial time algorithm for local testability problem of deterministic nite automata.

I.E.E.E. Trans. Comput., 40, 1991, pp. 10871093
6) S. M. Kim, R. McNaughton. Computing theorder of a locally testable automaton. SIAM J.
Comput. Vol. 23, No. 6, pp. 1193-1215, December 1994
7) A.M. Magnaghi. La testabilita locale nelle sinstasi dei linguaggi arti ciali Master Thesis, Adviser Prof. S. Crespi-Reghizzi, Politecnico di
Milano, 1996
8) R. McNaughton, S. Papert. Counter-free automata. M.I.T. Press, Cambridge, MA, 1971
9) M. Perles, O. Rabin, E. Shamir. The theoryof de nite automata. I.E.E.E. Trans. Electronic
Computers EC-12, 1963, pp.233-243
10) A. Pottho , W. Thomas. Regular tree languages without unary symbols are strar free. in
9th International Conference on Fundamentals
of Computation Theory, Zoltan E sik, ed., Lecture Notes in Compute Science 710 (1993), pp.
396-405
11) M. Steinby. A theory of language varieties. inTree Automata and Languages, M. Nivat andA. Podelski (editors), Elsevier Publ., 1992, pp.
57-8112) Y. Zalcstein. Locally testable languages. J.
Computer and System Sc., Vol. 6, 1972, pp.
151-167

6. Conclusions
After introducing the concept of local testability
in a general context, the paper focused directly on
the speci c case of locally testable string languages
in a strict sense. Interest in such a class of formal
languages is motivated not only on a theoretical but
also on an applied level, because of links to parallel
parsing and error handling.
Through the formulation of a set of lemmata
and theorems, a decidibility result was obtained for
LTk s:s: property. On an operative level it provides
a constructive algorithm to utilize on an accepting
automaton M of language L. The analyzed procedure tries to frame the extensively studied conceptof local testability in a di erent perspective. It aims
at capturing LTk s:s: in a direct and general manner without employing the algebraic properties ofthe syntactic monoid. Moreover, it does not impose
minimality constraints on M .
As a direct consequence of the developed algorithm, it was possible to easily relate LTk s:s: decidibility to LT s:s: decidibility and to the problemof nding the order of LT s:s: language.
The adopted approach does not rely on algebraic
concepts. Hence, this aspect could be of help toinvestigate the extension of the exposed considerations to the case of tree languages.
7. Acknowledgments
We are grateful to Mr. P. E. Purcell for his encouragement to write this paper and for the precious editing suggestions he gave us.

µ ¶ · ¸

1) J. A. Brzozowski, I. Simon. Characterization

8