A survey on difference hierarchies of regular languages
Olivier Carton Dominique Perrin Jean-Éric Pin



=1




1–LastPage
Feb. 28, 2017Mar. 29, 2018







  


automata,positioning
matrix









  





















conditions

   ()
   
     enumi
     
     
				
     
     
     
     
     
     
   




conditionsJE[2][]

























		






































































































-.3ex













O. Carton]Olivier Carton
IRIF, CNRS and Université Paris-Diderot
olivier.carton@irif.fr

D. Perrin]Dominique Perrin
Laboratoire d'informatique Gaspard-Monge, Université de Marne-la-Vallée
dominique.perrin@esiee.fr

J.-É. Pin]Jean-Éric Pin
IRIF, CNRS and Université Paris-Diderot jean-eric.pin@irif.fr The
third author is partially funded from the European Research Council (ERC) under the
European Union's Horizon 2020 research and innovation programme (grant agreement No
670624). The first and third authors are partially funded by the DeLTA project
(ANR-16-CE40-0007)


Formal languages and automata theory, Regular languages, Algebraic
language theory


	Difference hierarchies were originally introduced by Hausdorff and they play an
	important role in descriptive set theory. In this survey paper, we study difference
	hierarchies of regular languages. The first sections describe standard techniques
	on difference hierarchies, mostly due to Hausdorff. We illustrate these techniques
	by giving decidability results on the difference hierarchies based on shuffle
	ideals, strongly cyclic regular languages and the polynomial closure of group
	languages.


A survey on difference hierarchies of regular languages
    [
    December 30, 2023
=======================================================





	Dedicated to the memory of Zoltán Ésik.











§ INTRODUCTION


Consider a set E and a set  of subsets of E containing the empty set. The
general pattern of a difference hierarchy is better explained in a picture. Saturn's
rings-style Figure <ref> represents a decreasing sequence

    X_1 ⊇ X_2⊇ X_3 ⊇ X_4⊇ X_5

of elements of . The grey part of the picture corresponds to the set (X_1 -
X_2) + (X_3 - X_4) + X_5, a typical element of the fifth level of the difference
hierarchy defined by . Similarly, the n-th level of the difference hierarchy
defined by  is obtained by considering length-n decreasing nested sequences of
sets.

Difference hierarchies were originally introduced by Hausdorff
<cit.>. They play an important role in
descriptive set theory <cit.> and also yield a hierarchy on
complexity classes known as the Boolean hierarchy <cit.>, <cit.>, <cit.>,
<cit.>. Difference hierarchies were also used in the
study of ω-regular languages <cit.>.

The aim of this paper is to survey difference hierarchies of regular languages.
Decidability questions for difference hierarchies over regular languages were studied
in <cit.> and more recently by Glasser, Schmitz and Selivanov in
<cit.>. The latter article is the reference paper on this
topic and contains an extensive bibliography, to which we refer the interested
reader. However, paper <cit.> focuses on forbidden patterns
in automata, a rather different perspective than ours.

We first present some general results on difference hierarchies and their connection
with closure operators. The results on approximation of Section
<ref>, first presented in <cit.>, lead in some cases to
convenient algorithms to compute chain hierarchies.

Next we turn to algebraic methods. Indeed, a great deal of results on regular
languages are obtained through an algebraic approach. Typically, combinatorial
properties of regular languages — being star-free, piecewise testable, locally
testable, etc. — translate directly to algebraic properties of the syntactic monoid
of the language (see <cit.> for a survey). It is therefore natural to expect a
similar algebraic approach when dealing with difference hierarchies. However, things
are not that simple. First, one needs to work with ordered monoids, which are
more appropriate for classes of regular languages not closed under complement.
Secondly, although Proposition <ref> yields a purely algebraic characterization
of the difference hierarchy, it does not lead to decidability results, except for
some special cases. Two such cases are presented at the end of the paper. The first
one studies the difference hierarchy of the polynomial closure of a lattice of
regular languages. The main result, Corollary <ref>, which appears to be
new, states that the difference hierarchy induced by the polynomial of group
languages is decidable. The second case, taken from <cit.>, deals with
cyclic and strongly cyclic regular languages.

Our paper is organised as follows. Prerequities are presented in Section
<ref>. Section <ref> covers the results
of Hausdorff on difference hierarchies and Section <ref> is a
brief summary on closure operators. The results on approximation form the core of
Section <ref>. Decidability questions on regular languages are
introduced in Section <ref>. Section <ref> on chains is inspired by results of descriptive set theory.
Two results that are not addressed in <cit.> are presented
in Sections <ref> and <ref>. The final Section 
<ref> opens up some perspectives.









§ PREREQUISITES


In this section, we briefly recall the following notions: upper sets, ordered monoids, 
stamps and syntactic objects.

Let E be a preordered set. An upper set of E is a subset U of E such
that the conditions x ∈ U and x ≤ y imply y ∈ U. An ordered
monoid is a monoid M equipped with a partial order ≤ compatible with the
product on M: for all x, y, z ∈ M, if x ≤ y then zx ≤ zy and xz ≤
yz.

A stamp is a surjective monoid morphism φ:A^* → M from a finitely
generated free monoid A^* onto a finite monoid M. If M is an ordered
monoid, φ is called an ordered stamp. 

The restricted direct product of two stamps φ_1:A^* → M_1 and
φ_2:A^* → M_2 is the stamp φ with domain A^* defined by
φ(a) = (φ_1(a), φ_2(a)). The image of φ is an [ordered]
submonoid of the [ordered] monoid M_1 × M_2.


	
	
	
	
	
	
	
	
	
	
	
	
	
	
  
    < g r a p h i c s >



Stamps and ordered stamps are used to recognise languages. A language L of A^* is
recognised by a stamp φ: A^* → M if there exists a subset P of M
such that L = φ^-1(P). It is recognised by an ordered stamp φ:
A^* → M if there exists an upper set U of M such that L = φ^-1(U).

The syntactic preorder of a language was first introduced by Schützenberger in
<cit.>. Let L be a language of A^*. The syntactic
preorder of L is the relation ≤_L defined on A^* by u ≤_L v if and
only if, for every x, y ∈ A^*,

    xuy ∈ L  xvy ∈ L.

The associated equivalence relation ∼_L, defined by u ∼_L v if u ≤_L v
and v≤_L u, is the syntactic congruence of L and the quotient monoid
M(L) = A^*/∼_L is the syntactic monoid of L. The natural morphism
η: A^* → A^*/∼_L is the syntactic stamp of L. The
syntactic image of L is the set P = η(L).

The syntactic order ≤_P is defined on M(L) as follows: u ≤_P v if and
only if for all x,y ∈ M(L),

    xuy ∈ P  xvy ∈ P

The partial order ≤_P is stable and the resulting ordered monoid (M(L), ≤_P)
is called the syntactic ordered monoid of L. Note that P is now an upper set 
of (M(L), ≤_P) and η becomes an ordered stamp, called the syntactic ordered 
stamp of L.









§ DIFFERENCE HIERARCHIES


Let E be a set. In this article, a lattice is simply a collection of subsets
of E containing ∅ and E and closed under taking finite unions and
finite intersections. A lattice closed under complement is a Boolean
algebra. Throughout this paper, we adopt Hausdorff's convention to denote union 
additively, set difference by a minus sign and intersection as a product. We also 
sometimes denote L^c the complement of a subset L of a set E. 

Let  be a set of subsets of E containing the empty set. We set _0() =
{∅} and, for each integer n≥ 1, we let _n() denote the class
of all sets of the form

    X = X_1 - X_2 + …± X_n

where the sets X_i are in  and satisfy X_1 ⊇ X_2⊇ X_3
⊇…⊇ X_n. By convention, the expression on the right hand
side of (<ref>) should be evaluated from left to right, but given the
conditions on the X_i's, it can also be evaluated as

    (X_1-X_2) + (X_3-X_4) + (X_5-X_6) + …

Since the empty set belongs to , one has _n() ⊆_n+1()
for all n ≥ 0 and the classes _n() define a hierarchy within the Boolean
closure of . Moreover, the following result, due to
Hausdorff <cit.>, holds:


	Let  be a lattice of subsets of E. The union of the classes _n() for
	n≥ 0 is the Boolean closure of .


 Let () = ∪_n≥ 1_n(). By construction, every
element of _n() is a Boolean combination of members of  and thus
() is contained in the Boolean closure of . Moreover _1() =
and thus ⊆(). It is therefore enough to prove that () is
closed under complement and finite intersection. If X = X_1-X_2+…±
X_n, one has

    E-X = E-X_1+X_2- …∓ X_n

and thus X∈() implies E-X∈(). Thus () is closed under
complement.

Let X = X_1 - X_2 + …± X_n and Y = Y_1 - Y_2 + …± Y_m
be two elements of (). Let

    Z    = Z_1 - Z_2 + …± Z_n+m-1
     with
    Z_k    = ∑_i+j = k+1
    i and j not both even X_iY_j 
     Therefore
    	Z_1    = X_1Y_1,
    
    	Z_2    = X_1Y_2 + X_2Y_1,
    
    	Z_3    = X_1Y_3 + X_3Y_1,
    
    	Z_4    = X_1Y_4 + X_2Y_3 + X_3Y_2 + X_4Y_1,
       =
    
    	Z_n+m-1   =
    								X_nY_m      if m and n are not both even
    ∅   otherwise

We claim that Z = XY. To prove the claim, consider for each set X =
X_1 - X_2 + …± X_n associated with the decreasing sequence
X_1, …, X_n of subsets of E, the function μ_X defined
on E by

    μ_X(x) = max {i≥ 1| x∈ X_i}

with the convention that μ_X(x) = 0 if x ∈ E - X_1. Then x∈ X if and only
if μ_X(x) is odd. We now evaluate μ_Z(x) as a function of i = μ_X(x) and
j = μ_Y(x). We first observe that if k ≥ i + j, then x ∉ Z_k. Next,
if i and j are not both even, then x ∈ X_iY_j and X_iY_j ⊆
Z_i+j-1, whence μ_Z(x) = i + j -1. Finally, if i and j are both even, then
x ∉ Z_i+j-1 and thus μ_Z(x) is either equal to 0 or to i+j-2.
Summarizing the different cases, we observe that μ_X(x) and μ_Y(x) are both
odd if and only if μ_Z(x) is odd, which proves the claim. It follows that
() is closed under intersection.


An equivalent definition of _n() was given by Hausdorff
<cit.>. Let X  Y denote the symmetric difference of two subsets X
and Y of E.


	For every n ≥ 0, _n() = {X_1  X_2 … X_n | X_i∈}.


 Indeed, if X = X_1 - X_2 + …± X_n with X_1 ⊇
X_2⊇ X_3 ⊇…⊇ X_n, then X= X_1  X_2 … X_n. In the opposite direction, if X = X_1  X_2 … X_n, then X = Z_1 - Z_2 + …± Z_n where Z_k =
∑_i_1, …, i_k distincts X_i_1… X_i_k.










§ CLOSURE OPERATORS


We review in this section the definition and the basic properties of
closure operators.

Let E be a set. A map X →X from (E) to itself is a closure
operator if it is extensive, idempotent and isotone, that is, if the
following properties hold for all X, Y⊆ E:

	
  * X⊆X (extensive)

	
  * X = X (idempotent)

	
  * X⊆ Y implies X⊆Y (isotone)

A set F⊆ E is closed if F = F. If F is closed, and if
X⊆ F, then X⊆F = F. It follows that X is
the least closed set containing X. This justifies the terminology “closure”.
Actually, closure operators can be characterised by their closed sets.


	A set of closed subsets for some closure operator on E is closed under
	(possibly infinite) intersection. Moreover, any set of subsets of E closed under
	(possibly infinite) intersection is the set of closed sets for some closure
	operator.


 Let X→X be a closure operator and let (F_i)_i∈ I be a
family of closed subsets of E. Since a closure is isotone, ⋂_i∈
IF_i⊆F_i = F_i. It follows that ⋂_i∈ IF_i⊆⋂_i∈ IF_i and thus ⋂_i∈ IF_i is closed.

Given a set  of subsets of E closed under intersection, denote by
X the intersection of all elements of  containing X. Then the map
X→X is a closure operator for which  is the set of closed sets.


In particular, X ∩ Y⊆X∩Y, but the
inclusion may be strict.


The trivial closure is the application defined by

    X = ∅   if X = ∅
    
             E     otherwise

For this closure, the only closed sets are the empty set and E.



	If E is a topological space, the closure in the topological sense
	is a closure operator.



	The convex hull is a closure operator. However, it is not induced by
	any topology, since the union of two convex sets is not necessarily
	convex.


The intersection of two closure operators X →X and X →X is the function X →X defined by X = X∩X.

   The intersection of two closure operators is a closure operator.


 Let X be the intersection of
X and X. First, since
X⊆X and X⊆X, one has X⊆X =
X∩X. In particular, X⊆X. Secondly, since X∩X⊆X, X∩X⊆X = X. Similarly, X∩X⊆X. It follows that

    X = X∩X∩X∩X⊆X∩X = X

and hence X = X. Finally, if
X ⊆ Y, then X⊆Y and X⊆Y, and therefore X⊆Y.

Let us conclude this section by giving a few examples of closure operators
occurring in the theory of formal languages.







 
Iteration. The map L → L^* is a closure operator. Similarly, the map L
→ L^+, where L^+ denotes the subsemigroup generated by L, is a closure
operator.








 Shuffle ideal. 
The shuffle product (or simply shuffle) of two languages L_1 and
L_2 over A is the language

    L_1  L_2 = { w ∈ A^* | w = u_1v_1 … u_nv_n  for
    	some words u_1, …, u_n, v_1, …, v_n of A^*
    such that u_1 … u_n ∈ L_1 and v_1 … v_n ∈ L_2} .

The shuffle product defines a commutative and associative operation over the set of
languages over A. Given a language L, the language L  A^* is called the
shuffle ideal generated by L and it is easy to see that the map L → L
 A^* is a closure operator.

This closure operator can be extended to infinite words in two ways: the finite
and infinite shuffle ideals generated by an ω-language X are respectively:

    X  A^*    = { y_0x_1y_1 … x_ny_nx | y_0, …, y_n ∈ A^*
    	 and  x_1… x_n x ∈ X }
    
    	X  A^ω   = { y_0x_1y_1x_2 …| y_0, …, y_n, …∈ A^*
    	 and  x_1x_2…∈ X }

The maps X → X  A^* and X → X  A^ω are both closure
operators.


 Ultimate closure. The
ultimate closure of a language X of infinite words is defined by:

    (X) = { ux | u∈ A^*  and  vx ∈ X  for some  v ∈ A^*}

The map X →(X) is a closure operator.










§ APPROXIMATION


In this section, we consider a set  of closed sets of E containing the empty
set. It follows that the corresponding closure operator satisfies the condition
∅ = ∅. We first define the notion of an approximation
of a set by a chain of closed sets. Then the existence of a best approximation will
be established.
In this section, L is a subset of E.


A chain F_1 ⊇ F_2 ⊇…⊇ F_n of closed sets is an
n-approximation of L if the following inclusions hold for all k such 
that 2k + 1 ≤ n:

    F_1 - F_2 ⊆ F_1 - F_2 + F_3 - F_4 ⊆…⊆ F_1 -
    	F_2 + … + F_2k-1 - F_2k⊆…
    ⊆ L⊆…⊆ F_1 - F_2 + F_3 - … + F_2k+1⊆…⊆ F_1 - F_2 + F_3 ⊆ F_1


There is a natural order among the n-approximations of a given set L.
An n-approximation F_1 ⊇ F_2 ⊇…⊇ F_n of L is
said to be better than an n-approximation F'_1 ⊇ F'_2 ⊇…⊇ F'_n if, for all k such that 2k+1 ≤ n,

    F_1 - F_2 + F_3 - … + F_2k+1   ⊆ F'_1 - F'_2 + F'_3 -
    	… + F'_2k+1
     and
    	F'_1 - F'_2 + … + F'_2k-1 - F'_2k   ⊆ F_1 - F_2 +
    	… + F_2k-1 - F_2k

We will need the following elementary lemma:


	Let X, Y and Z be subsets of E.
	
		
  *  The conditions X-Y ⊆ Z and X-Z⊆ Y are
		equivalent.
		
		
  *  The conditions Z ⊆ X+Y and X^c ∩ Z⊆
		Y are equivalent.
		
		
  *  If Y ⊆ X and X-Y ⊆ Z, then X-Z = 
		Y-Z and X + Z = Y + Z.
	


The description of the best approximation of L requires the introduction
of two auxiliary functions. For every subset X of E, set

    f(X) = X-L  and   g(X) = X ∩ L

The key properties of these functions are formulated in the following lemma.


	The following properties hold for all subsets X and Y of E:

	
  *  X - f(X) ⊆ L and L ⊆ X + g(X^c),
	 
	
  *  if X ⊇ Y ⊇ L, then f(X) ⊇ f(Y)
	and X -f(X) ⊆ Y - f(Y) ⊆ L,

	 
  *  if X ⊆ Y ⊆ L, then g(X) ⊆ g(Y)
	 and L ⊆ Y + g(Y^c) ⊆ X + g(X^c).



 Let X and Y be subsets of E.

(<ref>) follows from a simple computation: 

    X - f(X)    = X - X-L⊆ X - (X-L) = X∩ L ⊆ L 
    
    	X + g(X^c)    = X + X^c ∩ L⊇ (X ∩ L) + (X^c ∩ L) = L.

(<ref>) Suppose that X ⊇ Y ⊇ L. Then X - L ⊇ Y -
L and thus X - L⊇Y - L, that is, f(X) ⊇ f(Y).
Furthermore, X - Y ⊆ X - L ⊆X - L = f(X). Applying part
(<ref>) of Lemma <ref> with Z = f(X), one gets X - f(X) =
Y - f(X), whence X - f(X)⊆ Y - f(Y) since f(X) ⊇ f(Y) by the
first part of (<ref>).

(<ref>) Suppose that X ⊆ Y ⊆ L. Then X ∩ L⊆Y ∩ L and thus g(X) ⊆ g(Y). Furthermore, Y - X = X^c ∩
Y ⊆ X^c ∩ L ⊆X^c ∩ L = g(X^c). Applying part
(<ref>) of Lemma <ref> with Z = g(X^c), one gets Y +
g(X^c)= X + g(X^c), whence Y + g(Y^c) ⊆ X + g(X^c) since g(Y^c) ⊆
g(X^c) by the first part of (<ref>).



 
	Let F_1 ⊇ F_2 ⊇…⊇ F_n be an
	n-approximation of L and, for 1 ≤ k ≤ n, let S_k = F_1 - F_2 + …± F_k. Then, for 1 ≤ k ≤ n,

    {
    	f(S_k)    = f(F_k)  if k is odd
    
    	g(S_k^c)    = g(F_k)  if k is even.



 If k=1, then S_1=F_1 and the result is trivial. Suppose that k>
1. If k is odd, S_k-1⊆ L and thus S_k - L = (S_k-1 + F_k) - L =
F_k - L. It follows that f(S_k) = f(F_k). If k is even, L ⊆ S_k-1
and thus S_k^c ∩ L = (S_k-1^c + F_k) ∩ L = F_k ∩ L. Therefore g(S_k^c)
= g(F_k).

Define a sequence (L_n)_n≥ 0 of subsets of E by
L_0= E and, for all n ≥ 0,

    L_n+1 =
    		f(L_n)    if n is odd
    
        g(L_n)    if n is even

The next theorem expresses the fact that the sequence (L_n)_n≥ 0 is the best
approximation of L as a Boolean combination of closed sets. In particular, if L_n
= ∅ for some n > 0, then L ∈_n-1().


	Let L be a subset of E. For every n > 0, the sequence (L_k)_1 ≤ k≤
	n is the best n-approximation of L.


 We first show that the sequence (L_k)_1 ≤ k≤ n is an
n-approximation of L. First, every L_k is closed by construction. We show that
L_k+1⊆ L_k by induction on k. This is true for k=0 since L_0 = E.
Now, if k is even, L_k+1 = L_k ∩ L⊆L_k = L_k and if
k is odd, L_k+1 = L_k - L⊆L_k = L_k.

Set, for k > 0, S_k = L_1 - L_2 + …± L_k. By part (<ref>)
of Lemma <ref>, the relations L_2k-1 - L_2k = L_2k-1 - f(L_2k-1)
⊆ L hold for every k> 0, and similarly, L_2k - L_2k+1 = L_2k -
g(L_2k) ⊆ L^c. It follows that S_2k⊆ L. Furthermore
S_2k+1^c = (L_0 -L_1) + (L_2 -L_3) + … + (L_2k - L_2k+1) ⊆
L^c and thus L⊆ S_2k+1.

We now show that the sequence (L_k)_1 ≤ k≤ n is the best approximation of
L. Let (L'_k)_1 ≤ k ≤ n be another n-approximation of L. Set, for k
> 0, S'_k = L'_1 - L'_2 + …± L'_k. Then, by definition, L
⊆ L'_1 and thus

    S_1 = L_1 = L⊆L'_1 = L'_1 = S'_1.

Let k > 0. Suppose by induction that S_2k-1⊆ S'_2k-1. We show
successively that S_2k⊆ S'_2k and S_2k+1⊆ S'_2k+1.

By definition of an approximation, S'_2k = S'_2k-1 - L'_2k⊆ L, and
thus S'_2k-1 - L⊆ L'_2k by part (<ref>) of Lemma
<ref>. It follows that f(S'_2k-1) = S'_2k-1 - L⊆L'_2k = L'_2k. Now, since S'_2k-1⊇ S_2k-1⊇ L, one
can apply part (<ref>) of Lemma <ref> to get

    S'_2k = S'_2k-1 - L'_2k⊆S'_2k-1 - f(S'_2k-1)⊆S_2k-1 - f(S_2k-1).

Moreover since f(S_2k-1) = f(L_2k-1) = L_2k by Lemma <ref>, one
gets 

    S'_2k⊆ S_2k-1 - f(S_2k-1) = S_2k-1 - L_2k = S_2k.

Similarly, L ⊆ S'_2k+1 = S'_2k + L'_2k+1 and hence (S'_2k)^c ∩
L⊆ L'_2k+1 by part (<ref>) of Lemma <ref>. It
follows that g((S'_2k)^c) = (S'_2k)^c ∩ L⊆L'_2k+1 =
L'_2k+1. Now, since S'_2k⊆ S_2k⊆ L, one can apply part
(<ref>) of Lemma <ref> to get

    S_2k + g(S_2k^c) ⊆ S'_2k + g((S'_2k)^c) ⊆ S'_2k
    	+ L'_2k+1 = S'_2k+1.

Moreover since the equalities g(S_2k^c) = g(L_2k) = L_2k+1 hold by Lemma
<ref>, one gets

    S_2k+1 = S_2k + L_2k+1 = S_2k + g(S_2k^c) ⊆ S'_2k+1.

which concludes the proof.
  

When  is a set of subsets of E closed under arbitrary intersection, Theorem
<ref> provides a characterization of the classes
_n().


	Let L be a subset of E and let  be a set of subsets of E closed under
	(possibly infinite) intersection and containing the empty set. Let (L_k)_1 ≤ k
	≤ n be the best n-approximation of L with respect to . Then L ∈_n-1() if and only if L_n = ∅ and in this case

    L = L_1 - L_2 + …± L_n-1



 If L ∈_n-1(), then L = F_1 - F_2 + …±
F_n-1 with F_1, …, F_n-1∈. Let F_n = ∅. Then the
sequence (F_k)_1≤ k ≤ n is an n-approximation of L. Since (L_k)_1
≤ k ≤ n is the best n-approximation of L, one has L =L_1 - L_2 + …± L_n-1. Thus, with the notation of Lemma <ref>,

    {
    	f(L_n-1)    = f(L) = ∅ if n-1 is odd
    
    	g(L_n-1)    = g(L^c) = ∅ if n-1 is even.

Therefore, L_n = ∅ by (<ref>).

Conversely, suppose that L_n = ∅. If n = 2k, then

    (L_1 - L_2) + … + (L_2k-1 - L_2k) ⊆ L   
    	⊆ (L_1 - L_2) + … + (L_2k-3 - L_2k-2) + L_2k-1
     If n = 2k + 1, then   (L_1 - L_2) + … + (L_2k-1 - L_2k) ⊆ L  
    	⊆ (L_1 - L_2) + … + (L_2k-1 - L_2k) + L_2k+1

In both cases, one gets L = L_1 - L_2 + …± L_n-1 and thus
L ∈_n-1().


Let us illustrate this corollary by a concrete example.


Let A = {a, b, c} and let  be the lattice of shuffle ideals. If L is the
language {1, a, b, c, ab, bc, abc}, a straightforward computation gives 

    L_0    = A^*  
    
    	L_1    = g(L_0) = A^*  (L_0 ∩ L) = A^*  L = A^* 
    
    	L_2    = f(L_1) = A^*  (L_1 - L) = A^* {aa, ac, ba, bb, ca, cb,
    	cc} = A^* - {1, a, b, c, ab, bc}
    
    	L_3    = g(L_2) = A^*  (L_2 ∩ L) = A^*  abc 
    
    	L_4    = f(L_3) = A^*  (L_3 - L) = A^*  ((A^*  abc) - abc)
       = A^* {aabc, abac, abca, babc,
    	abbc, abcb, cabc, acbc, abcc }
    
    	L_5    = g(L_4) = A^*  (L_4 ∩ L) = ∅

It follows that L = L_1 - L_2 + L_3 - L_4 and L ∈_4(), but L ∉_3().


It is also possible to use the approximation algorithm for a set  of subsets of 
E closed under (possibly infinite) union and containing the set E. In this case, 
the set 

    ^c = {L^c | L ∈}

is closed under (possibly infinite) intersection and contains the empty set.
Consequently, the approximation algorithm can be applied to ^c but it describes
the difference hierarchy _n(^c). To recover the difference hierarchy
_n(), the following algorithm can be used. First compute the best
^c-approximation of even length of L and the best ^c-approximation of odd
length of L^c, say

    L      = L_1^c - L_2^c + …± L_n^c    
    
    	L^c    = F_1^c - F_2^c + …± F_m^c

with n even, m odd, L_i, F_i ∈ and L_n and F_m possibly empty to fill
the parity requirements. Now L admits the following -decompositions, where 
L_1 and F_1 are possibly empty (and consequently deleted):

    L    = L_n - L_n-1 + …± L_1  
       = F_m - F_m-1 + …± F_1

It remains to take the shortest of the two expressions to get the best
-approximation of L.









§ DECIDABILITY QUESTIONS ON REGULAR LANGUAGES


Given a lattice of regular languages , four decidability questions arise:


 

	Is the membership problem for  decidable? 



	Is the membership problem for () decidable? 



	For a given positive integer n, is the membership problem for _n()
	decidable?



	Is the hierarchy _n() decidable?


In other words, given a regular language L, Question <ref>
asks to decide whether L ∈, Question <ref> whether L ∈() and Question <ref> whether L ∈_n(). Question
<ref> asks whether one can one effectively compute the smallest
n such that L ∈_n(), if it exists. Note that if Questions <ref> and <ref> are decidable, then so is Question
<ref>. Indeed, given a language L, one first decides whether
L belongs to () by Question <ref>. If the answer is
positive, this ensures that L belongs to _n() for some n and Question
<ref> allows one to find the smallest such n.

If the lattice  is finite, it is easy to solve the four questions in a positive
way. In some cases, a simple application of Corollary <ref> suffices to solve  
Question <ref> immediately. One just needs to find the appropriate 
closure operator and to provide algorithms to compute the functions f(X) and g(X) 
defined by (<ref>).


	Let  be the lattice generated by the languages of the form B^*, where B
	⊆ A. Then both  and () are finite. It is known that a regular
	language belongs to  if and only if its syntactic ordered monoid is idempotent
	and commutative and satisfies the inequation 1 ≤ x for all x <cit.>.
	It belongs to () if and only if its syntactic monoid is idempotent and
	commutative.
	
	Finally, one can define a closure operator by setting L = B^*, where
	B is the set of letters occurring in some word of L. For instance, let L =
	({a,b,c}^* - {b,c}^*) + ({a,b}^* - a^*) + 1. This language belongs to
	() and its minimal automaton is represented below:


	
	
	
	
	
	
	
	
	
	
	
	
	
	
  
    < g r a p h i c s >



Applying the approximation algorithm of Section <ref>, one gets
L_0 = {a,b,c}^*, L_1 = {b,c}^*, L_2 = b^* and L_3 = ∅ and thus L
= {a,b,c}^* - {b,c}^* + b^* is the best 3-approximation of L.

If the lattice is infinite, our four questions become usually much harder, but can
still be solved in some particular cases. We will discuss this in Sections
<ref> and <ref>, but first present a powerful tool
introduced in <cit.>, chains in ordered monoids.









§ CHAINS AND DIFFERENCE HIERARCHIES


Chains can be defined on any ordered set. We first give their definition, then
establish a connection with difference hierarchies.








Let (E, ≤) be a partially ordered set and let X be a subset of E. A
chain of E is a strictly increasing sequence

    x_0 < x_1 < … < x_m-1
 
of elements of E. It is called an X-chain if x_0 is in X and the
x_i's are alternatively elements of X and of its complement X^c. The integer
m is called the length of the chain. We let m(X) denote the maximal length
of an X-chain.


There is a subtle connection between chains and difference hierarchies of
regular languages. Let M be a finite ordered monoid and let φ : A^*
→ M be a surjective monoid morphism. Let

    = {φ^-1(U) |U is an upper set of M}

By definition, every language of  is recognised by the ordered monoid M.


	If there exists a subset P of M such that L= φ^-1(P) and m(P) ≤
	n, then L belongs to _n().


Before starting the proof, let us clarify a delicate point. The condition
L= φ^-1(P) means that L is recognised by the monoid M. It does
not mean that L is recognised by the ordered monoid M, a property which
would require P to be an upper set.


For each s ∈ M, let m(P, s) be the maximal length of a P-chain ending with
s. Finally, let, for each k > 0,

    U_k = {s ∈ M | m(P, s) ≥ k }

We claim that U_k is an upper set of M. Indeed, if s ∈ U_k, there exists a
P-chain x_0 < x_1 < … < x_r-1 = s of length r ≥ k. Let t be an
element of M such that s ≤ t. If s and t are not simultaneously in P,
then x_0 < x_1 < … < x_r-1 < t is a P-chain of length r+1 ≥ k.
Otherwise, x_0 < x_1 < … < x_r-2 < t is a P-chain of length r ≥ k.
Thus m(P, t) ≥ k, and t ∈ U_k, proving the claim.

We now show that

    P = U_1 - U_2 + U_3 - U_4 …± U_n

First observe that s ∈ P if and only if m(P, s) is odd. Since m(P) ≤
n, one has m(P, s) ≤ n for every s ∈ M and thus U_n+1 =
∅. Formula (<ref>) follows, since for each r ≥ 0, 

    {s ∈ M | m(P, s) = r } = U_r - U_r+1.

Let, for 1 ≤ i≤ n, L_i = φ^-1(U_i). Since U_i is
an upper set, each L_i belongs to . Moreover, one gets from (<ref>)
the formula

    L = L_1 - L_2 + L_3 …± L_n

which shows that L ∈_n().


We now establish a partial converse to Proposition <ref>. A lattice of regular languages is a set  of regular
languages of A^* containing ∅ and A^* and closed under finite union and
finite intersection.


	Let  be a lattice of regular languages. If a language L belongs to
	_n(), then there exist an ordered stamp η : A^* → M and a
	subset P of M satisfying the following conditions:
	 
	
  *  η is a restricted product of 
	syntactic ordered stamps of members of ,
	
	
  *  L= η^-1(P),
	
	
  *  m(P) ≤ n.



 If L ∈_n(), then

    L = L_1 - L_2 + L_3  … ± L_n

with L_1 ⊇ L_2 ⊇…⊇ L_n and L_i ∈. Let
η_i: A^* → (M_i, ≤_i) be the syntactic morphism of L_i and let
P_i = η_i(L_i). Then each P_i is an upper set of M_i and L_i =
η_i^-1(P_i). Let η : A^* → M be the restricted product of the
stamps η_i. Condition (<ref>) is satisfied by
construction.

Observe that if η(u) = (s_1, …, s_n) is an element of M, the condition
s_i+1∈ P_i+1 is equivalent to u ∈ L_i+1, and since L_i+1 is a
subset of L_i, this condition also implies u∈ L_i and s_i ∈ P_i.
Consequently, for each element s = (s_1, …, s_n) of M, there exists a unique
k ∈{0, …, n} such that

    s_1 ∈ P_1, …, s_k ∈ P_k, s_k+1∉ P_k+1, …, s_n ∉ P_n

This unique k is called the cut of s. Setting

    P = {s ∈ M |the cut of s is odd}

one gets, with the convention L_n+1 = ∅ for n odd, 

    η^-1(P) = ⋃_k odd((L_1 ∩…∩ L_k)
    	- L_k+1) = ⋃_k odd (L_k - L_k+1)
    	= L

which proves (<ref>).

Let now x_0 < x_1 < … < x_m-1 be a P-chain. Let, for 0 ≤ i ≤
m-1, x_i = (s_i,1, …, s_i,n) and let k_i be the cut of x_i. We claim
that k_i+1 > k_i. Indeed, since x_i < x_i+1, s_i, k_i≤_i s_i+1, k_i
and since P_i is an upper set, s_i, k_i∈ P_i implies s_i+1, k_i∈
P_i+1, which proves that k_i+1≥ k_i. But since x_i and x_i+1 are not
simultaneously in P, their cuts must be different, which proves the claim. Since
x_0 ∈ P, the cut of x_0 is odd, and in particular, non-zero. It follows that 0
< k_0 < k_1 < … < k_m-1 and since the cuts are numbers between 0 and
n, m ≤ n, which proves (<ref>).


It is tempting to try to improve Proposition <ref> by taking for M the
syntactic morphism of L and for φ the syntactic morphism of L. However,
Example <ref> ruins this hope. Indeed, let F = {1, a, b, c,
ab, bc, abc} be the set of factors of the word abc. Then the syntactic monoid of
L can be defined as the set F ∪{0} equipped with the product defined by

    xy = 
      
      	xy    if x, y and xy are all in F
    
      	0     otherwise

Now the syntactic image of L is equal to F. It follows that M - F = {0} and
thus, whatever order is taken on M, the length of a chain is bounded by 3.
Nevertheless, if  is the lattice of shuffle ideals, then L does not belong to
_3().

Therefore, if L is a regular language, the maximal length of an L-chain cannot be
in general computed in the syntactic monoid of L. It follows that decidability
questions on _n(), as presented in Section <ref>
below, cannot in general be solved just by inspecting the syntactic monoid. An
exceptional case where the syntactic monoid suffices is presented in the next
section.









§ THE DIFFERENCE HIERARCHY OF THE POLYNOMIAL CLOSURE OF A
LATTICE


A language L of A^* is a marked product of the languages L_0, L_1,
…, L_n if

    L = L_0a_1L_1 … a_nL_n

for some letters a_1, …, a_n of A. Given a set  of languages, the
polynomial closure of  is the set of languages that are finite unions of
marked products of languages of . The polynomial closure of  is
denoted  and the Boolean closure of  is denoted . Finally, let
 denote the set of complements of languages in . In this section, we 
are interested in the difference hierarchy induced by .
We consider several examples.









 §.§ Shuffle ideals


If = {∅, A^*}, then  is exactly the set of shuffle ideals
considered in Examples <ref> and <ref> and  is the class of
piecewise testable languages. The following easy result was mentioned in
<cit.>.


	A language is a shuffle ideal if and only if its syntactic ordered monoid M
	satisfies the inequation 1 ≤ x for all x ∈ M.


The syntactic characterization of piecewise testable languages follows from a much
deeper result of Simon <cit.>.


	A language is piecewise testable if and only if its syntactic monoid is
	-trivial.


Note that the closed sets of the closure operator X → X  A^* of Example
<ref> are exactly the shuffle ideals. It follows that for the lattice
 of shuffle ideals, the four questions mentioned earlier have a positive answer.
More precisely, the decidability of the membership problem for  and for
() follows from Proposition <ref> and Theorem
<ref>, respectively. The decidability of Question
<ref> (and hence of Question <ref>) follows
from the approximation algorithm. See Example <ref>.









 §.§ Group languages


Recall that a group language is a language whose syntactic monoid is a
group, or, equivalently, is recognized by a finite deterministic automaton in which
each letter defines a permutation of the set of states. According to the definition
of a polynomial closure, a polynomial of group languages is a finite union
of languages of the form L_0a_1L_1 … a_kL_k where a_1, …, a_k are
letters and L_0, …, L_k are group languages.

Let d_ be the metric on A^* defined as follows:

    r_(u,v)    = min{|M| |M is a finite group that separates u
    	and v}
    
    	d_(u,v)    = 2^-r_(u,v)

It is known that d_ defines the so-called pro-group topology
on A^*. It is also known that the closure of a regular language for d_ is
again regular and can be effectively computed. This result was actually proved in two
steps: it was first reduced to a group-theoretic conjecture in <cit.>
and this conjecture became a theorem in <cit.>.

Let  be the set of group languages on A^* and let  be the polynomial
closure of . We also let  denote the set of complements of languages of
. The following characterization of  was given in <cit.>.


	Let L be a regular language and let M be its syntactic ordered monoid. The
	following conditions are equivalent:

		
	
  * L ∈,
	
	
  * L is closed in the pro-group topology on A^*,
	
	
  * for all x ∈ M, x^ω≤ 1.
	



Theorem <ref> shows that , and hence , is
decidable. The corresponding result for  has a long story, related in detail
in <cit.>, where several other characterizations can be found.


	Let L be a regular language and let M be its syntactic monoid. The following
	conditions are equivalent:
	
	
  * L ∈,
	
	
  * the submonoid generated by the idempotents of M is -trivial,
	
	
  * for all idempotents e, f of M, the condition efe = e implies ef = e
	= fe.
	


We  now study the difference hierarchy based on . Let
 be the set of closed subsets for the pro-group topology.


	For each n ≥ 0, a regular language belongs to _n() if
	and only if it belongs to _n().


 Theorem <ref> shows that  is a subset of . It 
follows that any language of _n() belongs to _n().

Let now L be a regular language of _n() and let (L_k)_1 ≤ k ≤ n
be the best n-approximation of L with respect to . Corollary <ref>
shows that L ∈_n() if and only if L_n+1 = ∅. Moreover, in
this case L = L_1 - L_2 + …± L_n. According to the algorithm
described at the end of Section <ref>, the best n-approximation
of L is obtained by alternating the two operations

    f(X) = X-L  and   g(X) = X ∩ L

Now, as we have seen, the closure of a regular language for d_ is regular. It
follows that if X is regular, then both f(X) and g(X) are regular and closed.
By Theorem <ref>, they both belong to . It follows that each
L_k belongs to  and thus L ∈_n().


This leads to the following corollary:


	The difference hierarchy _n() is decidable.


 Let L be a regular language. Theorem <ref> shows that one
can effectively decide whether L ∈. If this is the case, it remains to
find the minimal n such that L ∈_n(). But Proposition
<ref> shows that L belongs to _n() if and only if it
belongs to _n(). Moreover, since the closure of a regular language can be
effectively computed, the best n-approximation of L with respect to  can be
effectively computed. Now, Corollary <ref> gives an algorithm to decide
whether L ∈_n().











§ CYCLIC AND STRONGLY CYCLIC REGULAR LANGUAGES


Cyclic and strongly cyclic regular languages are two classes of regular languages
related to symbolic dynamic and first studied in <cit.>. It
was shown in <cit.> that an appropriate notion of chains suffices to
characterise the difference hierarchy based on the class of strongly cyclic regular
languages. This contrasts with Section <ref>,
in which the general results on chain did not lead to a full characterization of
difference hierarchies.

Let = (Q, A, ) be a finite (possibly incomplete) deterministic automaton. A
word u stabilises a subset P of Q if P  u = P. Given a subset P
of Q, let (P) be the set of all words that stabilise P. The language
() that stabilises  is by definition the set of all words which
stabilise at least one nonempty subset of Q.


	A language is strongly cyclic if it stabilises some finite deterministic
	automaton.



If  is the automaton represented in Figure <ref>, then 

    ({1}) = (b + aa)^*, ({2}) = (ab^*a)^*, ({1,
    	2}) = a^*
 
and () = (b + aa)^* + (ab^*a)^* + a^*.


One can show that the set of strongly cyclic languages of A^* forms a
lattice of languages but is not closed under quotients. For instance, as shown in
Example <ref>, the language L = (b + aa)^* + (ab^*a)^* + a^* is
strongly cyclic, but Corollary <ref> will show that
its quotient b^-1L = (b + aa)^* is not strongly cyclic, since aa ∈ (b + aa)^*
but a ∉ (b + aa)^*.

We will also need the following characterization <cit.>:


	Let = (Q,A,E) be a deterministic automaton. A word u belongs to
	() if and only if there is some state q of  such that for every
	integer n, the transition q· u^n exists.
 


Strongly cyclic languages admit the following syntactic characterization
<cit.>. As usual, s^ω denotes the 
idempotent power of s, which exists and is unique in any finite monoid.


	Let L be a non-full regular language. The following conditions are equivalent:
	
		
  * L is strongly cyclic,
	
		
  * there is a morphism φ from A^* onto a finite monoid M with zero
		such that

    L = φ^-1({s ∈ M | s^ω≠ 0 }),


		
  * the syntactic monoid M of L has a zero and the syntactic image of L
		is the set of all elements s ∈ M such that s^ω≠ 0.
	


Proposition <ref> leads to a simple
syntactic characterization of strongly cyclic languages. Recall that a language of
A^* is nondense if there exists a word u ∈ A^* such that L ∩ A^*uA^*
= ∅.



	Let L be a regular language, let M be its syntactic monoid and let P be its
	syntactic image. Then L is strongly cyclic if and only if it satisfies the
	following conditions, for all u, x, v ∈ M:
S
	
  *  ux^ω v ∈ P implies x^ω∈ P,
	
	
  *  x^ω∈ P if and only if x ∈ P.

Furthermore, if these conditions are satisfied and if L is not the full language,
then L is nondense.



Let L be a strongly cyclic language, let M be its syntactic monoid and let P be
its syntactic image. If L is the full language, then the conditions <ref> and
<ref> are trivially satisfied. If L is not the full language, then
Proposition <ref> shows that M has a zero and that
P = {s ∈ M | s^ω≠ 0 }. Observing that x^ω =
(x^ω)^ω, one gets

    x ∈ P ⟺ x^ω≠ 0 ⟺ 
    	(x^ω)^ω≠ 0 ⟺ x^ω∈ P

which proves <ref>. Similarly, one gets

    ux^ω v ∈ P  (ux^ω v)^ω≠ 0  x^ω≠ 0  x 
    	∈ P

which proves <ref>.

Conversely, suppose that L satisfies <ref> and <ref>. If L is full,
then L is strongly cyclic. Otherwise, let z ∉ P. Then z^ω∉ P by
<ref> and uz^ω v ∉ P for all u, v ∈ M by <ref>. This
means that z is a zero of M and that 0 ∉ P. By Proposition
<ref>, it remains to prove that x ∈ P if and only
if x^ω≠ 0. First, if x ∈ P, then x^ω∈ P by <ref> and
since 0 ∉ P, one has x^ω≠ 0. Conversely, if x^ω≠ 0, then
ux^ω v ∈ P for some u, v ∈ M, since x^ω is not equivalent to 0
in the syntactic congruence of P. It follows that x^ω∈ P by <ref>
and x ∈ P by <ref>.


We turn now to cyclic languages.


A subset of a monoid is said to be cyclic if it is closed under conjugation,
power and root. That is, a subset P of a monoid M is cyclic if it satisfies the
following conditions, for all u, v ∈ M and n > 0:
C
	
  *  u^n ∈ P if and only if u ∈ P,

	
  *  uv ∈ P if and only if vu ∈ P.


This definition applies in particular to the case of a language of A^*.


  If A = {a, b}, the language b^* and its complement A^*aA^* are cyclic.

One can show that regular cyclic languages are closed under inverses of
morphisms and under Boolean operations but not under quotients. For instance, the
language L = {abc, bca, cab} is cyclic, but its quotient a^-1L = {bc} is
not cyclic. Thus regular cyclic languages do not form a variety of languages.
However, they admit the following straightforward characterization in terms of
monoids.

 
	Let L be a regular language of A^*, let φ be a surjective morphism from
	A^* to a finite monoid M recognising L and let P = φ(L). Then L is
	cyclic if and only if P is cyclic.



	Every strongly cyclic language is cyclic. 



	Let L be a strongly cyclic language, let M be its syntactic monoid and let P
	be its syntactic image. By Proposition <ref>,
	P satisfies <ref> and <ref>. It suffices now to prove  that it 
	satisfies <ref>. The sequence of implications

    xy ∈ P    <ref> (xy)^ω∈ P  (xy)^ω
    	(xy)^ω∈ P  (xy)^ω -1xy(xy)^ω -1xy ∈ P 
        ((xy)^ω -1x)(yx)^ω y ∈ P <ref>
    	(yx)^ω∈ P <ref> yx ∈ P.

shows that xy ∈ P implies yx ∈ P and the opposite implication follows by
symmetry.


Another result is worth mentioning: for any regular cyclic language, there
is a least strongly cyclic language containing it <cit.>.


	Let L be a regular cyclic language of A^*, let η : A^* → M be its
	syntactic stamp and let P = η(L). There M has a zero and the language 

    L = 
    	η^-1({s | s^ω≠ 0})    if 0 ∉ P,
    
    	  A^*       otherwise.

is the least strongly cyclic language containing L.



If 0 ∉ P, then the language L is strongly cyclic by
Proposition <ref>. Morevover, since L is cyclic, P
is cyclic by Proposition <ref>. It follows that if s ∈ P, then
s^ω∈ P and in particular s^ω≠ 0. Consequently, L
contains L. 

It remains to prove that L is the least strongly cyclic language
containing L. Let X be a strongly cyclic language containing L and let u be a
word of L. Let 𝒜 = (Q,A,E) be a deterministic automaton such
that X = (𝒜). Setting s = η(u), one has s^ω≠ 0 by
definition of L. Consequently, η(s)^n ≠ 0 for every integer n
and there are two words x_n and y_n such that x_nu^ny_n belongs to L. By
Proposition <ref>, there is a state q_n of  such that the
transition q_n· x_nu^ny_n is defined. The transition (q_n· x_n)· u^n
is thus defined for every n and by Proposition <ref> again, the
word u belongs to X. Thus L⊆ X as required.
  
Suppose now that 0 ∈ P and let z be a word of L such that η(z) = 0. Let
X be a strongly cyclic language containing L. If X is not full, then X is
nondense by Proposition <ref> and there exists a
word u ∈ A^* such that A^*uA^* ∩ X = ∅. Since X contains L, one
also gets A^*uA^* ∩ L = ∅ and in particular zu ∉ L. But this
yieds a contradiction, since η(zu) = η(z)η(u) = 0 ∈ P and thus zu ∈η^-1(P) = L. Thus the only strongly cyclic language containing L is A^*.


Given a finite monoid M, the Green's preorder relation  defined on
M by

    s  t  if and only if s ∈ MtM, or equivalently, if there exists u, v
    	∈ M such that s = utv

is a preorder on M. The associated equivalence relation  is defined by 

    s  t  if s  t and t  s, or equivalently, if MsM = MtM.



	Let L be a regular cyclic language of A^*, let η : A^* → M be its
	syntactic stamp and let P = η(L). Then L is strongly cyclic if and only if
	for all idempotents e, f of M, the conditions e ∈ P and e  f imply f
	∈ P.



Suppose that L is strongly cyclic and let e, f be two idempotents of M such
that e ∈ P and e  f. Let u,v ∈ M be such that e = ufv. Since
f^ω = f, one gets uf^ω v ∈ P and thus f ∈ P by Condition
<ref> of Proposition <ref>.

In the opposite direction, suppose that for all idempotents e, f of M, the
conditions e ∈ P and e  f imply f ∈ P. Since L is cyclic, it
satisfies <ref> and hence <ref>. We claim that it also satisfies
<ref>. Indeed, ux^ω v ∈ P implies (ux^ω v)^ω∈ P by
<ref>. Furthermore, since (ux^ω v)^ω x^ω, one also has
x^ω∈ P, and finally x ∈ P by <ref>, which proves the claim.


The precise connection between cyclic and strongly cyclic languages was given in
<cit.>.


	A regular language is cyclic if and only if it is a Boolean combination of regular
	strongly cyclic languages.


Theorem <ref> motivates a detailed
study of the difference hierarchy of the class  of strongly cyclic languages.
This study relies on a careful analysis of the chains on the set of idempotents of a
finite monoid, pre-ordered by the relation .


	A P-chain of idempotents is a sequence (e_0, e_1, …, e_m-1) of
	idempotents of M such that

    e_0  e_1 … e_m-1

e_0 ∈ P and, for 0 < i <m, e_i ∈ P if and only if e_i-1∉
P. The integer m is the length of the P-chain of idempotents.


We let ℓ(M, P) denote the maximal length of a P-chain of idempotents
of M. We consider in particular the case where φ : A^* → M is a stamp
recognising a regular language L of A^* and P = φ(L). The next theorem
shows that in this case, ℓ(M, P) does not depend on the choice of the stamp
recognising L, but only depends on L.





	Let L be a regular language. Let φ : A^* → M and ψ : A^* → N be
	two stamps recognising L. If P = φ(L) and Q = ψ(L), then ℓ(M,P) =
	ℓ(N,Q).



It is sufficient to prove the result when φ is the syntactic stamp of L.
Since the morphism ψ is surjective, M is a quotient of N and there is a
surjective morphism π : N → M such that π∘ψ = φ. It follows
that

    π(Q) = P  and π^-1(P) = Q.

We show that to any P-chain of idempotents in N, one can associate a Q-chain of
idempotents of the same length in M and vice-versa.
  
Let (e_0, …, e_m-1) be a Q-chain of idempotents in N and let f_i =
π(e_i) for 0 ≤ i ≤ m-1. Since every monoid morphism preserves , the
relations (<ref>) show that (f_0, …, f_m-1) is a P-chain of
idempotents in M.
  
Let now (f_0, …, f_m-1) be a P-chain of idempotents in M. Since f_i-1 f_i, there exist for 1 ≤ i ≤ m-1 elements u_i, v_i of M such that
u_if_iv_i = f_i-1. Let us choose an idempotent e_m-1 such that π(e_m-1)
= f_m-1 and some elements s_i and t_i of N such that π(s_i) = u_i and
π(t_i) = v_i. We now define a sequence of idempotents (e_0, …, e_m-1)
of N by setting

    e_m-2 = (s_m-1e_m-1t_m-1)^ω     e_m-3 =
    	(s_m-2e_m-2t_m-2)^ω    …     e_0 = (s_1e_1t_1)^ω

By construction, e_0 … e_m-1 and a straightforward induction
shows that π(e_i) = f_i for 0 ≤ i ≤ m-1. Moreover the equalities
(<ref>) show that e_i ∈ Q if and only if f_i ∈ P. It follows that
(e_0, …, e_m-1) is a Q-chain of idempotents of N and thus ℓ(M,P) =
ℓ(N,Q).

 
Since the integers ℓ(M, P) only depend on L and not on the choice of the
recognising monoid, let us define ℓ(L) as ℓ(M, P) where M [P] is the
syntactic monoid [image] of L. Note that by Corollary <ref>, a cyclic language L is strongly cyclic if and only if ℓ(L) =
1. This is a special case of the following stronger result <cit.>.


	Let L be a regular cyclic language. Then L ∈_n() if and only if
	ℓ(L) ≤ n.


We first prove the following lemma which states that the function ℓ is
subadditive with respect to the symmetric difference.


	If X and Y are regular languages, then ℓ(X  Y) ≤ℓ(X) + ℓ(Y).
 


	Suppose that the languages X and Y are respectively recognised by the stamps
	φ : A^* → M and ψ : A^* → N. Let P and Q be the images of X
	and Y in M and N, so that X = φ^-1(P) and Y = ψ^-1(Q). The
	language X  Y is recognised by the restricted product of the stamps φ
	and ψ, say γ: A^* → R, and the image of X  Y in R is

    T = R ∩(P × (N - Q) + (M - P) × Q).

	Let ((e_0,f_0), …, (e_m-1, f_m-1)) be a T-chain of idempotents in R.
	Let us consider the set I (resp. J) of integers i for which exactly one of
	the idempotents e_i-1 or e_i (resp. f_i-1 or f_i) belongs to P (resp.
	Q). Formally, we define the sets of integers I and J to be
  
    I    = { 1 ≤ i ≤ m-1 | e_i-1∈ P  e_i ∉P }
    
    		 J    = { 1 ≤ i ≤ m-1 | f_i-1∈ Q  f_i ∉Q }

	Since the sequence ((e_0,f_0), …, (e_m-1, f_m-1)) is a T-chain in R,
	one has e_0 … e_m-1 and f_0 …
	f_m-1. Moreover, every integer i between 1 and m-1 belongs to exactly one
	of the sets I or J. Otherwise, the idempotents (e_i-1, f_i-1) and (e_i,
	f_i) of R would be either both in T or both out of T. Let I = {i_1,
	…, i_p} and J = {j_1, …, j_q} with i_1 < … < i_p and
	j_1 < … < j_q. Then p + q = m - 1.
	
	Since (e_0,f_0) ∈ T, the conditions e_0 ∈ P and f_0 ∉ Q are
	equivalent. By symmetry, suppose that e_0 ∈ P. Then f_0 ∉ Q and thus
	f_1 ∈ Q. Furthermore, the definitions of I and J give

    e_0    ∈ P,     e_1    ∈ P,    …       e_i_1-1   ∈ P,     e_i_1   ∉ P,    …      
    	e_i_2-1   ∉ P,    e_i_2   ∈ P,    …
    
    	f_0    ∉ P,     f_1    ∉ P,    …       f_j_1-1   ∉ P,    f_j_1   ∈ P,
    	   …       f_j_2-1   ∈ P,    f_j_2   ∉ P,    …

	Then the sequence (e_0, e_i_1, …, e_i_p) is a P-chain of
	idempotents in M and (f_j_1, …, f_q) is a Q-chain of idempotents in
	N. Therefore p + 1 ≤ℓ(X), q ≤ℓ(Y) and m = p + 1 + q ≤ℓ(X) + ℓ(Y). Thus ℓ(X  Y) ≤ℓ(X) + ℓ(Y).


We can now complete the proof of Theorem <ref>. 


Let η:A^* → M be the syntactic stamp of L and let P = η(L). Let 
also E(M) be the set of idempotents of M.
If L ∈_n(), then L = L_1 … L_n for some strongly cyclic
languages L_i. By Corollary <ref>, one has
ℓ(L_i) = 1 for 1 ≤ i ≤ n and thus ℓ(L) ≤ n by Lemma
<ref>.
  
Suppose now that ℓ(L) ≤ n. For each idempotent e of M, let ℓ(e)
denote the maximal length of a P-chain of idempotents ending with e. Then
ℓ(e) ≤ℓ(L) by definition. For each i > 0, let

    P_i = {s ∈ M |ℓ(s^ω) ≥ i}  and   L_i =
    	η^-1(P_i)

Let e, f ∈ E(M). Since every idempotent e satisfies e^ω = e, the
conditions e ∈ P_i and e  f imply f ∈ P_i. It follows by
Corollary <ref> that the languages L_i are
strongly cyclic. We claim that

    P = P_1 - P_2 + P_3 - P_4 … ± P_m

First observe that since L is cyclic, an element s of M belongs to P if and
only if s^ω belongs to P. Moreover, s^ω∈ P if and only if
ℓ(s^ω) is odd. Since ℓ(P) ≤ n, one has ℓ(s^ω) ≤ n for
every s ∈ M and thus P_n+1 = ∅. Formula (<ref>)
follows, since for each r ≥ 0,

    {s ∈ M |ℓ(s^ω) = r } = P_r - P_r+1.

Moreover, one gets from (<ref>) the formula

    L = L_1 - L_2 + L_3  … ± L_n

which completes the proof of the theorem.


Theorem <ref> can be used to give an another proof of Theorem
<ref>. To get this result, we must prove that any
cyclic language belongs to the class _n() for some integer n. By Theorem
<ref>, it suffices to prove that the length of the P-chains of
idempotents in a monoid recognising L is bounded. This is a consequence of the
following proposition <cit.>.


	Let L be a regular cyclic language. Let φ : A^* → M be a stamp
	recognising L and let P = φ(L). Then the length of any P-chain of
	idempotents is bounded by the -depth of M.



Let (e_0, …, e_n-1) be a P-chain of idempotents in M. Then by definition

    e_0 … e_n-1.

Moreover, if e_i-1 e_i, then by <cit.>, the
idempotents e_i-1 and e_i are conjugate. That is, there exist two elements x
and y of M such that xy = e_k-1 and yx = e_k. Since L is cyclic, P is
also cyclic by Proposition <ref> and <ref> implies
that e_i-1∈ P if and only if e_i ∈ P, which contradicts the definition of
a P-chain of idempotents. It follows that the sequence (e_0, …, e_n-1) is a
strict <_-chain and hence its length is bounded by the -depth of M.


 
	Let L be the cyclic language (b+aa)^* + (ab^*a)^* +a^* - b^* + 1. Its syntactic
	monoid is the monoid with zero presented by the relations bb = b, a^3 = a, baa
	= a^2b, a^2ba = ba, bab = 0. Its transition table and its -class
	structure are represented below. The syntactic image of L is P = {1, a, a^2,
	aba, a^2b} and (aba, b, 1) is a maximal P-chain of idempotents.
	




	
	2|c|   1    2    3    4    5    6    7    8 

	*    1      1    2    3    4    5    6    7    8 

			   a      3    4    5    2    3    8    2    6 

	*    b      7    0    8    4    4    0    7    8 

  *    a^2    5    2    3    4    5    6    4    8 

			   ab     8    4    4    0    8    8    0    0  

			   ba     2    0    6    2    2    0    2    6 

  *    a^2b   4    0    8    4    4    0    4    8 

  *    aba    6    2    2    0    6    6    0    0 

  *    bab    0    0    0    0    0    0    0    0 

	
	    
	
	
		  1 

		 

	

  
	
		 b 

		
	    
	
		 a^2    a 

		



	
	
		a^2b    ba 

		ab    aba 

		



	
	
		bab 

		

	












§ CONCLUSION



Difference hierarchies of regular languages form an appealing measure of complexity.
They can be studied from the viewpoint of descriptive set theory and automata theory
<cit.> or from an algebraic perspective, as presented in
this paper. It would be interesting to compare these two approaches.

The results proposed by Glasser, Schmitz and Selivanov
<cit.>, together with our new result on group languages,
give hope that more decidability results might be obtained in a near future. In
particular, the recent progress on concatenation hierarchies <cit.>, might lead to new decidability results for the
difference hierarchies induced by the lower levels of the Straubing-Thérien
hierarchy.

Let us conclude with an open problem:


	Does there exist a lattice of regular languages  and an integer n such that
	the membership problems for  and for () are decidable, but is
	undecidable for _n()?


If the answer to Question <ref> is positive, a more 
precise question can be raised:


	For each integer n, does there exist a lattice of regular languages  such that
	the membership problems for , () and _n() are decidable, but
	the membership problem for _n+1() is undecidable?




§ ACKNOWLEDGMENTS


The authors would like to thank the anonymous referees, whose suggestions strongly
improved the quality of this paper.








  
biblistanglais

