Diego Figueira

Leonid Libkin

Synchronizing Relations on Words

Keywords: 1998 ACM Subject Classification F.4.3 Formal Languages Word Relations, Regular, Rational, Recognizable

While the theory of languages of words is very mature, our understanding of relations on words is still lagging behind. And yet such relations appear in many new applications such as verification of parameterized systems, querying graph-structured data, and information extraction, for instance. Classes of well-behaved relations typically used in such applications are obtained by adapting some of the equivalent definitions of regularity of words for relations, leading to non-equivalent notions of recognizable, regular, and rational relations.

The goal of this paper is to propose a systematic way of defining classes of relations on words, of which these three classes are just natural examples, and to demonstrate its advantages compared to some of the standard techniques for studying word relations. The key idea is that of a synchronization of a pair of words, which is a word over an extended alphabet. Using it, we define classes of relations via classes of regular languages over a fixed alphabet, just {1, 2} for binary relations. We characterize some of the standard classes of relations on words via finiteness of parameters of synchronization languages, called shift, lag, and shiftlag. We describe these conditions in terms of the structure of cycles of graphs underlying automata, thereby showing their decidability. We show that for these classes there exist canonical synchronization languages, and every class of relations can be effectively re-synchronized using those canonical representatives. We also give sufficient conditions on synchronization languages, defined in terms of injectivity and surjectivity of their Parikh images, that guarantee closure under intersection and complement of the classes of relations they define.

Introduction

Foundations of formal language theory have been largely developed in the 1960s and 1970s, and used heavily in practically all areas of computer science. The field itself stayed somewhat dormant for a while, but that changed over the past 10-15 years due to new application areas requiring techniques that could not have been foreseen 30 or 40 years earlier. Among consumers of results in formal language theory are verification (for instance, automata-based approaches to model-checking are now part of standard industrial verification tools [START_REF] Ben-Ari | Principles of the Spin model checker[END_REF][START_REF] Mcmillan | Symbolic Model Checking[END_REF]) and data management (standards for describing and querying XML documents, for instance, are rooted in both word and tree automata [START_REF] Neven | Automata, Logic, and XML[END_REF][START_REF] Schwentick | Automata for XML -a survey[END_REF], and emerging graph data models are borrowing many formal language concepts [START_REF] Angles | Survey of graph database models[END_REF]).

Of interest to us in this paper are relations on words. That is, for a given finite alphabet A, we deal with binary relations R ⊆ A * × A * . Their study goes back to Elgot, Mezei, Nivat in the 1960s [START_REF] Elgot | On relations defined by generalized finite automata[END_REF][START_REF] Nivat | Transduction des langages de Chomsky[END_REF] with much subsequent work done later (see, e.g., surveys [START_REF] Berstel | Transductions and Context-Free Languages[END_REF][START_REF] Choffrut | Relations over words and logic: A chronology[END_REF]). The standard notions of regularity that generate the same class of languages -recognizability by finite monoids, definability by automata, or by regular expressions-give rise to different classes of relations, called recognizable, regular, and rational relations. Their properties may differ significantly from properties of regular languages: for instance, rational relations are not closed under intersection and it is even undecidable whether the intersection of two such languages is non-empty. Recognizable relations are just unions of products of regular languages; examples of regular relations are prefix, equality, or equal length of words; and examples of rational relations are suffix, subword (for instance, bb is a subword of aabbaa), and subsequence (bb is a subsequence of abaaba: letters need not be consecutive).

There has been renewed interest in relations on words as of late. One motivation comes from verification of safety and liveness properties of parameterized systems, where such relations describe transitions [START_REF] Abdulla | A survey of regular model checking[END_REF][START_REF] Bouajjani | Regular model checking[END_REF][START_REF] Jonsson | Transitive closures of regular relations for verifying infinitestate systems[END_REF][START_REF] To | Algorithmic metatheorems for decidable LTL model checking over infinite systems[END_REF]. Another comes from graph databases, which are actively studied as a suitable model for RDF data, social networks data, and others [START_REF] Angles | Survey of graph database models[END_REF]. Paths in graph databases are described by their labels, and need to be compared, for instance, for their degree of similarity, e.g., their edit distance [START_REF] Anyanwu | ρ-queries: enabling querying for semantic associations on the semantic web[END_REF][START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF][START_REF] Milo | Network motifs: simple building blocks of complex networks[END_REF]. Yet another example is the study of formal models underlying IBM's tools for information extraction [START_REF] Fagin | A formal framework for information extraction[END_REF].

Many of the basic questions that arise in these new applications, however, are not the kind of questions that had been addressed previously. Just to give an example, it is well known that checking nonemptiness of the intersection of a rational relation and a regular relation is an undecidable problem. But what about really used rational relations such as subword, suffix, subsequence (as opposed to artificial codings of the halting problem)can we test if their intersection with regular relations is nonempty? However natural these questions are, they were answered only recently [START_REF] Barceló | Graph logics with rational relations[END_REF].

An even more basic question relates to the very choice and structure of the main classes of relations: recognizable, regular, and rational. They appeared in a somewhat ad hoc way, just as analogs of different ways of defining regularity of languages, but is there another way to explain these, and perhaps other classes as well? This is the main point of our paper: we argue that there is a natural way to study relations on words, and we do it by explaining how positions in words are synchronized.

As an example of synchronization, consider words w 1 = ababb and w 2 = baaaba. We can represent this pair as a single word over {a, b}, by shuffling w 1 and w 2 , i.e., interspersing letters of w 1 among letters of w 2 . For each position in the shuffle, we remember which word it came from -this is indicated by the symbols 1 or 2 above the letters in the figure. When we read the letters marked i, for i = 1, 2 we get the word w i . The word over {1, 2} provides a synchronization of the pair (w 1 , w 2 ) -in our example, 12212112212. We show that the commonly occurring classes of relations over words follow the same principle:

These are the questions we answer. We define three parameters of regular languages in (1|2) * : the shift says how often we switch between 1s and 2s, the lag says how big the difference between the numbers of 1 and 2 is allowed to get, and shiftlag combines the two in a certain way. Then finite shift characterizes recognizability, while finite shiftlag characterizes regularity of relations. Finite lag, which appears to be a natural measure then, captures another known class of relations.

We provide automata characterizations of classes of synchronization languages in terms of the structure of cycles in the graph representations of automata. All these turn out to be decidable. This shows one advantage of dealing with relations in terms of their synchronizations. For instance, it is known that checking whether a given rational relation is regular, is an undecidable problem (assuming the input is a transducer, i.e., an automaton with output [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]). However, if the input to the problem is a synchronization language, then it is decidable whether the relations it describes are all regular.

Another advantage of describing relations by their synchronizations is the ability to find classes closed under intersection or complementation (rational relations, for instance, are not). We do it by imposing decidable conditions on Parikh images of synchronization languages to guarantee closure properties of classes of relations they give rise to.

We also look at re-synchronization of relations. For each class of relations, there may be many different regular synchronizing languages over {1, 2}. We show that in the standard cases, there exist canonical synchronizing languages, and relations can be effectively resynchronized using those canonical languages.

Recognizable, regular, and rational relations

We start with some basic notations. Throughout the paper, A stands for a finite alphabet, N = {1, 2, . . . } for the set of positive natural numbers, and N 0 for N ∪ {0}. The set of all words over A is denoted by A * , and the length of w in A * is denoted by |w|. If w = a 1 . . . a n , then w[i, j] stands for the subword a i . . . a j ; in particular, w[i] is the letter a i . Recall that there are three standard ways of defining regular languages:

Recognizability by finite monoids: the set A * , equipped with the concatenation operation (denoted by '•', whose unit is the empty word 'ε') is a monoid. A set L ⊆ A * is recognizable if there is a finite monoid M and a homomorphism A * , •, ε → M so that L = f -1 (M 0 ) for some M 0 ⊆ M . Definability by finite automata, say NFAs. Definability by regular (sometimes called rational) expressions, i.e., those built from the empty word and alphabet letters using union, concatenation, and the Kleene star.

Classical formal language theory tells us that these definitions generate the same class of languages, known as regular languages. We now adapt them to binary relations on words.

Recognizable relations Since

A * , •, ε is a monoid, A * × A * has
the structure of a monoid too. We can thus define recognizable relations as sets R ⊆ A * × A * for which there is a finite monoid M and a morphism f : is given by an automaton over this alphabet: it contains pairs (w 1 , w 2 ) whose encodings are accepted by the automaton. The class of regular relations is denoted by REG. Rational relations There are two equivalent ways of defining them. One uses regular expressions, which are now built from pairs in (A ∪ {ε}) × (A ∪ {ε}) using the same operations of union, concatenation, and Kleene star. Alternatively, rational relations can be defined by means of 2-tape automata, that have 2 heads for the tapes and one additional control; at every step, based on the state and the letters it is reading, the automaton can enter a new state and move some (not necessarily all) tape heads. The class of rational relations is denoted by RAT.

A * × A * → M such that R = f -1 (M 0 ) for some M 0 ⊆ M .
Relations in REC are exactly the finite unions of products of regular languages over Note that unlike in the case of languages, where the three notions coincide, we have REC REG RAT. The classes REC and REG are closed under intersection; however the class of rational relations is not. In fact, one can find R ∈ REG and S ∈ RAT so that R ∩ S ∈ RAT. However, if R ∈ REC and S ∈ RAT, then R ∩ S ∈ RAT.

Relations in REC and REG inherit all the closure/decidability properties of regular languages. If R ∈ RAT, then each of its projections is a regular language, and can be effectively constructed. Hence, the nonemptiness problem is decidable for RAT. However, testing nonemptiness of the intersection of two rational relations is undecidable. We refer to [START_REF] Berstel | Transductions and Context-Free Languages[END_REF][START_REF] Carton | Decision problems among the main subfamilies of rational relations[END_REF][START_REF] Sakarovitch | Elements of Automata Theory[END_REF] for basic information on these relations and their decision problems.

3

Synchronizations of relations

We now formalize the idea of synchronizations informally described in the introduction. We write k for the set {1, . . . , k}. A synchronization of a pair (w 1 , w 2 ) of words in A * is a word over 2×A so that the projection on A of positions labeled i is exactly w i , for i = 1, 2 (see the figure on page 2). Every word w in (2 × A) * is a synchronization of a uniquely determined pair (w 1 , w 2 ), where w i is the sequence of A-letters corresponding to the symbol i in the first position of 2 × A. We denote such (w 1 , w 2 ) by [[w]] and extend it to languages S ⊆ (2

× A) * by [[S]] = {[[w]] | w ∈ S}. For two words u = a 1 • • • a n ∈ A * and v = b 1 • • • b n ∈ B * , we write u ⊗ v for the word (a 1 , b 1 ) • • • (a n , b n ) ∈ (A × B) * .
The main idea of our approach to relations on words comes from two different ways of viewing words in (2 × A) * .

Every word w

∈ (2 × A) * is a synchronization of a pair [[w]] = (w 1 , w 2 ). Every word w ∈ (2 × A) * is of the form u ⊗ v with u ∈ 2 * and v ∈ A * .

This makes it possible to define relations consisting of pairs [[w]

] with restricted synchronizations, i.e., w = u ⊗ v and u belongs to a given language L ⊆ 2 * .

Formally, if L ⊆ 2 * , we say that u ⊗ v is L-controlled if u ∈ L; a language is L-controlled if all its words are. We now look at relations given by L-controlled synchronizations, i.e., for a regular language L ⊆ 2 * , let

Rel(L) = {[[S]] | S is a regular L-controlled language} (1) If C is a class of relations over A * , then L ⊆ 2 * is a synchronization for C if Rel(L) ⊆ C,
that is, all relations given by L-controlled synchronizations belong to C. We remark that a similar approach to defining relations was used in [START_REF] Harju | shuffle on trajectories: the Schützenberger product and related operations[END_REF], although the questions considered were completely different. Procedurally, each relation in Rel(L) is obtained as follows:

1. Choose an automaton over 2 × A; 2. consider words u ⊗ v it accepts so that u ∈ L, 3. view v as a synchronization of (w 1 , w 2 ) and add the pair to the relation.

This view suggests natural candidates for capturing classes REC, REG, and RAT. For REC, relations are unions of products of regular languages, so synchronizations are of the form 1 * 2 * : one starts by going over the first word, and then over the second. For REG, they are from ( 12) * (1 * |2 * ): we first go over two words letter-by-letter, and then write out the rest of the longer word. For RAT, there are no restrictions. Indeed, we can show the following. Proposition 1.

(I) Rel(1 * 2 * ) = REC. (II) Rel((12) * • (1 * |2 * )) = REG. (III) Rel((1|2) * ) = RAT.
It is easy to see that Rel(L) is closed under union, alphabetic morphisms, and inverse alphabetic morphisms, and that

L 1 ⊆ L 2 implies Rel(L 1 ) ⊆ Rel(L 2 ).
Remark One may ask why we need to take both S and L regular in the definition (1) of Rel(L). The reason why S needs to be regular is that even with regular L (e.g., 1 * ), Rel(L) would otherwise contain non-rational relations (e.g., {(a n b n , ε) | n ∈ N}). If, on the other hand, L is not regular, strange things may happen. For instance, it could be that all relations in Rel(L) are finite, although L is infinite. Indeed, take L as the set of all words 1 p for prime p. Note that there is no infinite regular L-controlled language, since it would imply that an infinite number of distinct primes is semi-linear. Thus, all regular L-controlled languages are finite, and Rel(L) is the set of all finite relations on A * × {ε} so that the first component is of prime length.

4

Synchronizations for recognizable, regular, and rational relations

) * 2) * (1 * |2 * )) = REG.
What kind of parameters guarantee that L ⊆ 2 * synchronizes relations in a class C, for the classes we study here? That is, what parameters guarantee that with the synchronization language L, we are guaranteed that the resulting relations are in C?

We now answer this question, but first we need some definitions. Given a word w over some finite alphabet, and a letter a in the alphabet, we define # a (w) as the number of occurrences of a in w. Given a word w ∈ 2 * , a position i ≤ |w|, and δ ∈ N, we say i is

δ-lagged if |# 1 (w[1, i]) -# 2 (w[1, i])| = δ; ≥δ-lagged if |# 1 (w[1, i]) -# 2 (w[1, i])| ≥ δ; ≤δ-lagged if |# 1 (w[1, i]) -# 2 (w[1, i])| ≤ δ.
That is, these parameters show by how much the numbers of 1s and 2s in w ∈ 2 * differ.

A shift of w is a position i ∈ {1, . . . , |w| -1} so that w[i] = w[i + 1]. Two shifts i < j are consecutive if there is no shift l so that i < l < j.

Let shift(w) be the number of shifts of w, let lag(w) be the maximum lag of a position in w, and let shiftlag(w) be the maximum n ∈ N so that w contains n consecutive shifts which are >n-lagged. We lift these notions to languages by taking maxima, e.g., shift(L) = max w∈L shift(w), and likewise for lag(L) and shiftlag(L). If words of arbitrarily large lag (shift, or shiftlag) occur in L, we write shift(L) = ∞ (and likewise for the other parameters).

Observe that finite shift and finite lag imply that shiftlag is finite, but the converse is not true: for L = (12) * 1 * we have shiftlag(L) < ∞ and yet lag(L) = shift(L) = ∞.

It turns out that finiteness of the shiftlag parameter corresponds to synchronizing regular languages, and finiteness of shift corresponds to synchronizing recognizable languages. An arbitrary regular L ⊆ 2 * is guaranteed to synchronize rational languages.

As for the finite lag, it corresponds to a class of languages that is known as well. The class REG bld of bounded length discrepancy relations [START_REF] Frougny | Synchronized rational relations of finite and infinite words[END_REF][START_REF] Sakarovitch | Elements of Automata Theory[END_REF] is defined as follows. Recall the definition of rational relations using two-tape automata. For a rational relation to be in REG bld it is required that there be δ ≥ 0 so that in accepting runs of such automata, the heads for the two tapes are never more than δ positions apart. It also follows from [START_REF] Frougny | Synchronized rational relations of finite and infinite words[END_REF][START_REF] Sakarovitch | Elements of Automata Theory[END_REF] that

REG bld is the class k∈N0 Rel(L k ), for L k = (12) * (1 k |2 k ). Note that Rel(L 0 ) is the class of length preserving relations. A closely related class R ≤ = {(w 1 , w 2 ) ∈ A * × A * | |w 1 | ≤ |w 2 |}
[21] can be equally defined by Rel((12|2) * ). Now we can state the characterization result.

Theorem 1. Let L ⊆ 2 * be a regular language. Then:

(I) L synchronizes regular relations iff shiftlag(L) < ∞, (II) L synchronizes recognizable relations iff shift(L) < ∞, (III) L synchronizes relations in REG bld iff lag(L) < ∞, (IV) L synchronizes rational relations.
Proof idea. For the 'if' direction of (I), one can easily show that for any regular language L with shiftlag(L) < n there is some δ so that L ⊆ L for L = L ≤δ-lag • (1 * |2 * ) n , where L ≤δ-lag is the (regular) language of all words with ≤δ-lagged positions. On the other hand, it is easy to show that Rel(L ) = REG. Since L ⊆ L , by applying monotonicity, we then have Rel(L) ⊆ REG.

For the 'only if' direction of (I), suppose that shiftlag(L) = ∞. Note that this means that for every s, δ ∈ N there is some w ∈ L that has s consecutive shifts >δ-lagged. Let S ⊆ (2 × {a, b}) * consist of all words u ⊗ v ∈ (2 × {a, b}) * so that u ∈ L, and for every i ∈ {1, . . . , |v|}, we have v

[i] = a if i is a shift of u, and v[i] = b otherwise. One can show that S is an L-controlled relation so that [[S]] ∈ RAT \ REG.
The proofs for the items (II), (III), and (IV), as well as the full proof for item (I) are contained in the Appendix and are omitted here.

We conclude the section with a couple of examples of applications of the main result. First, we show that Rel((112) * ) ⊆ REG. Indeed, note that for every s, δ, the word w = (112) δ+s is in (112) * and the last s shifts of w are ≥δ-lagged. Hence, there must be some L-controlled regular language S ⊆ (2 × A) * so that [[S]] is not a regular relation.

As another example, we get more ways of synchronizing regular relations: given

L 1 = (1 k •2 k ) * , L 2 = (1 * •2 * ) k for some fixed k, we have Rel(L i ) ⊆ REG (in fact, Rel(L 2 ) ⊆ REC).
Finally, we consider the (r/s)-synchronized relations [27, p.660] studied in [START_REF] Carton | The growth ratio of synchronous rational relations is unique[END_REF]. This class can be defined as Rel(L r/s ), where

L r/s = (1 r 2 s ) * r <r (1 r 2 * ) | s <s (1 * 2 s ) .
(

) 2
It is easy to see that shiftlag(L r/s ) = ∞ whenever r = s, and hence that (r/s)-synchronized relations (with r = s) are not in REG.

Automata theoretic characterizations

We characterized classes of relations via conditions imposed on their synchronization languages: finite shift, lag, or shiftlag. Now we show that these conditions themselves can be characterized using automata, or more precisely, the underlying labeled graphs of automata. It turns out that the structure of the cycles provides the desired characterizations.

Since in this section we deal with synchronization languages, we consider automata over the alphabet {1, 2}. For a given NFA A, we consider the transition graph G A of A as the usual representation of the transition relation, where G A is a directed graph where states are vertices and edges are labeled by transitions. Given a cycle C of G A , we define # a (C) as the number of edges in C labeled with transitions reading letter a. In a heterogeneous cycle

C we have # 1 (C) > 0 and # 2 (C) > 0; otherwise a cycle is homogeneous. A cycle C is balanced if # 1 (C) = # 2 (C),
otherwise it is unbalanced (these definitions are closely related to the notions of balanced/unbalanced oriented cycles in digraphs, cf. [START_REF] Hell | Graphs and Homomorphisms[END_REF]). Note that all balanced cycles are also heterogeneous.

Recall that the trim automaton is the result of removing all states which are not reachable from the initial state, and all states from which no final state is reachable.

Theorem 2. For any trim NFA A over the alphabet 2, and its transition graph

G A , (I) shiftlag(L(A)) = ∞ iff G A contains a heterogeneous unbalanced cycle, or G A contains a path from a homogeneous to a heterogeneous cycle, (II) shift(L(A)) = ∞ iff G A has a heterogeneous cycle, (III) lag(L(A)) = ∞ iff G A has an unbalanced cycle.
Proof idea. The 'if' directions of all items are straightforward. For the 'only if' direction of item (I), it can be shown that for n = 2|Q| + 1 (where |Q| is the number of states of A), any accepting run of A on w ∈ L(A) so that shiftlag(w) ≥ n must induce a path on the transition graph G A of A containing either a heterogeneous unbalanced cycle, or a homogeneous cycle followed by a heterogeneous cycle. Once this is verified, the statement follows. Note that since shiftlag(w) ≥ n, w must contain n consecutive >n-lagged shifts

1 ≤ a 1 < a 2 < • • • < a n ≤ |w| in w.
Since a 1 is >n-lagged, there must be an unbalanced cycle C 1 contained in the path induced by the run ρ restricted to w[1, a 1 ]. Since there is a sufficiently large number of shifts, there must be some heterogeneous cycle C 2 contained in the path induced by the run ρ restricted to w[a 1 , |w|]. Of course, we have that there is a path from C 1 to C 2 in G A , showing (I). The remaining items are shown in the Appendix.

Corollary 3. Checking whether Rel(L(

A)) ⊆ REG, Rel(L(A)) ⊆ REC or Rel(L(A)) ⊆ REG bld
2 can be done in polynomial time in the size of A.

Note that Corollary 3 does not mean that it is decidable whether a relation R ∈ RAT is in REG (in fact, this problem is undecidable [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]]). What one can check is whether it has a "safe" control, in the sense that it synchronizes regular relations. Hence, for any relation R controlled by L(A), if Rel(L(A)) ⊆ REG then R ∈ REG, but the opposite does not necessarily hold. For example, if we take L = (1|2) * , we have that Rel(L ) ⊆ REG but the universal relation A * × A * is obviously in REG.

Resynchronizing relations

We saw that different languages in 2 * can generate the same class relations, and yet for the commonly used classes, we have synchronization languages that somehow look canonical: for instance, ( 12) * (1 * |2 * ) for REG. Thus, we now address the question whether we can resynchronize relations using those canonical synchronization languages, and if so, can we do it effectively?

To pose this formally, suppose two different languages S, S ⊆ (2 × A) * controlled by L, L ⊆ 2 * respectively represent the same relation, i.e.,

[[S]] = [[S ]

]. Then we say that S is an L-resynchronization of S . Given a class C of regular languages over 2, we say that L 0 ∈ C is a canonical representative of C if for every L ∈ C and every L-controlled language S there exists an L 0 -resynchronization of S. In other words, for every L ∈ C and R ∈ Rel(L), there is an

L 0 -controlled S ∈ (2 × A) * so that [[S ]] = R.
If, in addition, there is a recursive procedure that constructs such an L 0 -resynchronization of S, then we say that L 0 is an effective canonical representative of C.

Let RL all be the class of all regular languages over 2, and let RL fin param stand for class of regular languages L ⊆ 2 * with finite parameter param, where param is lag, or shift, or shiftlag. We also let RL lag≤δ denote the class of all regular languages L ⊆ 2 * with lag(L) ≤ δ.

Example 4. Take, for example,

L 1 = (1122) * 1 * 2 * and L 2 = (12) * (1 * |2 * ), and a L 1 - controlled relation S 1 . Since shiftlag(L 1 ) < ∞, [[S 1 ]] ∈ REG by Theorem 1. Further, since by Proposition 1-(II) Rel(L 2 ) = REG, there must be some L 2 -controlled relation S 2 so that [[S 2 ]] = [[S 1 ]]. In other words S 2 is the L 2 -resynchronization of S 1 . Since Rel(L 2 ) = REG in fact L 2 is a canonical representative of RL fin shiftlag .
Theorem 5 (Resynchronization theorem).

(I) (12) * (1 * |2 * ) is an effective canonical representative of RL fin shiftlag ; (II) 1 * 2 * is an effective canonical representative of RL fin shift ; (III) there is no canonical representative of RL fin lag ; (IV) (12) * (1 ≤δ |2 ≤δ ) is an effective canonical representative of RL lag≤δ ; (V) 2 * is an effective canonical representative of RL all .
If the relations are given as NFA, the synchronization procedures are in exponential time.

Proof idea. We only give the proof sketch for (I), the other items being easier.

The strongly connected components (henceforth SCC) of G A are its maximal strongly connected subgraphs. An SCC is heterogeneous if it contains a heterogeneous cycle; an SCC is homogeneous if it contains a cycle and all the cycles it contains are homogeneous; otherwise, an SCC without cycles (that is, a single vertex) is an edgeless SCC. The condensation of G A (written con(G A )) is the labeled directed acyclic graph (henceforth labeled DAG) induced by the SCC's of G A . This is the labeled DAG whose nodes are the SCC's of G A , and there is an edge labeled (q, (i, a), q ) from vertex v to vertex v iff v = v , q belongs to the SCC v in G A , q belongs to the SCC v in G A , and there is an edge labeled (q, (i, a), q ) from q to q in G A (in other words, (q, (i, a), q ) is a transition of A).

Let S ⊆ (2 × A) * be an L-controlled regular language with shiftlag(L) < ∞. Let A be an NFA recognizing S with statespace Q, initial state q 0 and set of final states Q F .

Note that since the projection of S onto 2 is inside L, we can apply Theorem 2-(I) to A, obtaining that there are no paths from homogeneous SCC's to heterogeneous SCC's in G A (and there are no heterogeneous cycles C with # 1 (C) = # 2 (C)). Let Q hom be the set of all vertices of G A that are reachable from a vertex of a homogeneous SCC. Note

Q het Q hom 2 1 2 2 2 1 2 1 2 1 1 1 2 1 1 2
Figure 1 Example of GA with the subgraphs induced by Q hom and Q het . For simplicity we assume that A = {a} and we hence omit the letter a when depicting edges labeled by (i, a).

that Q hom includes all vertices in homogeneous SCC's, plus some vertices from edgeless SCC's. Also, note that the subgraph of G A induced by Q hom has no heterogeneous cycles.

Let Q het = Q \ Q hom .
Hence, Q het includes all vertices in heterogeneous SCC's and some vertices in edgeless SCC's. Also, by the property before, the subgraph of G A induced by Q het is connected. Figure 1 contains an example. Further, any path P in G A is of the form (1) P • (q, τ, q ) • P , (2) P , or (3) P , where

P is a (possibly empty) path of the subgraph of G A induced by Q het , P is a (possibly empty) path of the subgraph of G A induced by Q hom , q ∈ Q het , q ∈ Q hom ,

and τ is a transition of A.

Let A het be A restricted to Q het , and let A hom be A restricted to Q hom . For every pair of states q het ∈ Q het and q hom ∈ Q hom , let L q het ,q hom be the union of all

L(A het [q 0 , q het ]) • {(i, a)} • L(A hom [q hom , q f ])
for every q f ∈ Q F and (i, a) ∈ 2 × A so that (q het , (i, a), q hom ) is a transition of A. Let

L hom = q f ∈Q F L(A hom [q 0 , q f ]) and L het = q f ∈Q F L(A het [q 0 , q f ]). It follows that S = L hom ∪ L het ∪ q het ∈Q het ,q hom ∈Q hom L q het ,q hom .
We show that we can build, in exponential time, a (12) * (1 * |2 * )-controlled automaton for each of these languages. Since the case of L q het ,q hom is more general than L hom and L het , we will only prove this case.

Note that by definition of A het and A hom , and since G A has no unbalanced heterogeneous cycles, for every

q het ∈ Q het , q hom ∈ Q hom , q f ∈ Q F we have that lag(L(A het [q 0 , q het ])) < ∞ and shift(L(A hom [q hom , q f ])) < ∞. This implies that lag(L(A het [q 0 , q het ])) ≤ n, and shift(L(A hom [q hom , q f ])) ≤ n, for n = |A|(this is actually shown in Lemma 12 in the Ap- pendix).
By the already shown item (II), there exists a (1

* 2 * )-controlled automaton A hom q hom ,q f so that [[L(A hom [q 0 , q hom ])]] = [[L(A hom q0,q hom )]]
. By item (IV), there exists a ( 12)

* (1 ≤n |2 ≤n )- controlled automaton A het q0,q het so that [[L(A het [q 0 , q het ])]] = [[L(A het q0,q het )]
]. These automata can be built in exponential time.

Indeed, a (12) * (1 * |2 * )-controlled automaton for L q het ,q hom can be built from A het q0,q het and all the A hom q hom ,q f 's for all q f ∈ Q F in polynomial time, and thus the statement follows. This is shown by a variant of (II), showing that from any (1 * 2 * )-controlled automaton one can build, in polynomial time, an equivalent automaton (in the sense of the relation it represents) that is (12) * (1 * |2 * )-controlled.

Closure via Parikh images

It is well known that the class REG is effectively closed under Boolean operations. Although RAT is a natural generalization of REG, it is not a Boolean algebra (let alone an effective one), not being closed under intersection or complement [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]. Even testing whether a rational relation is regular, or whether it has an empty intersection with a regular relation is undecidable [START_REF] Berstel | Transductions and Context-Free Languages[END_REF]. Since regular relations are characterized via finite shiftlag, it is natural to ask whether infinite shiftlag somehow describes "dangerous" classes of relations. That is, does this mean for example that for any L ⊆ 2 * with shiftlag(L) = ∞ the intersection problem is undecidable for Rel(L)? The answer to this question is negative: take for instance L = (122) * with shiftlag(L) = ∞. However, it is not hard to see that Rel(L) is effectively closed under intersection. This raises the question of whether there are classes C ⊆ RAT that are natural, expressive, and well-behaved, that is, so that REC C, C is effectively closed under union, intersection and complementation (i.e., is an effective Boolean algebra); and C corresponds to a natural condition on the language.

Note that REG is one such example. Here we address the question from our perspective in terms of control languages. The idea is to show sufficient conditions of synchronization languages L so that Rel(L) is effectively closed under intersection, or an effective boolean algebra. We state those in terms of Parikh images of languages.

Recall that the Parikh image of a word w ∈ k * , written Π(w), is the vector of N k 0 whose ith component contains # i (w), the number of occurrences of i in w. The Parikh image of a language L is Π(L) = {Π(w) | w ∈ L}. It is well known that for regular and context-free languages L, sets Π(L) are exactly the semi-linear sets in N k 0 , see [START_REF] Parikh | On context-free languages[END_REF]. It is easy to see that L r/s as defined in (2) is Parikh-injective and Parikh-surjective for any choice of r, s. For example, if r = 2, s = 1, we have L r/s = (122) * (22 * |1 * 2|1 * ), which is Parikh-injective and Parikh-surjective, since every element of (N 0 ) 2 is covered, and there is only one way to reach any element of (N 0 ) 2 .

A language L ⊆ k * is Parikh-injective if the function Π : L → N k 0 is
We now analyze the (effective) closure of classes Rel(L) under Boolean operations. It turns out that closure under union is free, but for closure under intersection and complement, the newly introduced criteria serve as sufficient conditions. It was shown in [START_REF] Carton | The growth ratio of synchronous rational relations is unique[END_REF] that the class of (r/s)-synchronized relations is an effective Boolean algebra. Our results provide an alternative proof, since L r/s is Parikh-injective and Parikh-surjective.

Observation Note that Theorem 7 cannot be generalized to finite unions of Parikh-injective languages, since for example Rel(L) for L = ((12) * 1 * )|(1 * (12) * ) is not closed under intersection. In fact, its intersection problem is undecidable. This follows from the fact that Rel(L) contains the suffix relation and all regular relations (where the first component is longer than the second). By [5, Theorem V.1], this problem is undecidable.

7

Future work

We presented a new way of looking at relations on words, and this new perspective opens up several directions. An obvious one is to extend results to k-ary relations, for k > 2. We know that exact analogs of Proposition 1, Theorem 1, and Theorem 2 continue to hold. Another natural extension is to look for other classes of relations, say analogs of contextfree languages. In particular, one can look at a generalization of rational relations, the pushdown relations of [START_REF] Choffrut | Properties of finite and pushdown transducers[END_REF], which are those recognized by multi-tape automata with a stack or, equivalently, by a context-free grammar. We have some preliminary results in this direction but more work is needed.

We also would like to use the structural approach to look for better behaved classes of relational word transducers for verification purposes, and for classes of relations that can be effectively used in querying graph data. Finally, we would like to use it to identify classes of well behaved relations over data words [START_REF] Bojańczyk | Automata for data words and data trees[END_REF] and study logics over them, extending the approach of [START_REF] Barceló | Graph logics with rational relations[END_REF][START_REF] Barceló | Expressive languages for path queries over graph-structured data[END_REF] with data.

A APPENDIX: Complete Proofs Preliminaries

The strongly connected components (henceforth SCC) of G A are its maximal strongly connected subgraphs. An SCC is heterogeneous if it contains a heterogeneous cycle; an SCC is homogeneous if it contains a cycle and all cycles it contains are homogeneous; otherwise, an SCC without cycles (that is, a single vertex) is an edgeless SCC. The condensation of G A (written con(G A )) is the directed acyclic graph (henceforth DAG) induced by the SCC's of G A . This is the DAG where nodes are SCC's of G A and there is an edge labeled (q, (i, a), q ) from vertex v to (a different) vertex v if q belongs to the SCC of v, q belongs to the SCC of v and there is an edge labeled (q, (i, a), q ) from q to q in G A (in other words, (q, (i, a), q ) is a transition of A).

Complete proof of Proposition 1

Proof. (I)-[⊇] The fact that Rel(L) contains any union of products of regular languages (and hence that REC ⊆ Rel(L)) is straightforward. Note that Rel(L) is closed under finite union, and for any two regular languages L 1 , L 2 we have that

L 1 × L 2 ∈ Rel(L) because (1 ⊗ L 1 ) • (2 ⊗ L 2 ) is an L-controlled language. (I)-[⊆]
On the other hand, let R ∈ Rel(L), defined by a L-controlled language S. Let S be described by an NFA A S with statespace Q, initial state q 0 and final states F . Let L q,q i be the language consisting of all words v ∈ A * so that there is a partial run of A S on i ⊗ v starting in state q and ending in state q . Note that L q,q i is regular. Hence,

R = [[S]] = q∈Q,q ∈F L q0,q 1 × L q,q 2 ,
(A ) is L-controlled. Let Q = 2 × Q.
For any transition (q, (a, b), q ) of A, where a, b = ⊥, we have two transitions ((1, q), (1, a), (2, q)) and ((2, q), (2, b), (1, q )) in A ; and for any transition (q, (⊥, b), q ) (resp. (q, (a, ⊥), q )) of A, we have a transition ((1, q), (2, b), (1, q )) (resp. ((1, q), (1, a), (1, q ))) in A . It follows that if a pair (u, v) is accepted by the relation represented by L(A ) if, and only if, (u, v) is in [[L(A )]]. Further, it is plain that by the behavior of A (i.e., once it reads a letter (a, ⊥) for a ∈ A, it reads only ⊥ in the second component, and likewise for the first component) A must be L-controlled.

(II)-[⊆] Let A be an NFA over

2 × A so that L(A) is L-controlled, with statespace Q. Note that Q can be partitioned into four sets Q 1 , Q 2 , Q 1 , Q 2 , so that the transition relation δ of A is such that δ ⊆ i∈2 Q i × {i} × A × (Q \ Q i ) ∪ i∈2 Q i × {i} × A × Q i ( †)
that is, all outgoing transitions from Q i , Q i read letters from {i} × A, and there is an alternation between Q 1 and Q 2 until a state from Q i is reached, and after that it stays only in Q i . We can build an automaton A over (A ∪ {⊥}) 2 representing the same relation as follows. For every two transitions (q 1 , (1, a), q 2 ) and (q 2 , (2, b), q ) of A where q i ∈ Q i , we have a transition (q 1 , (a, b), q ) in A ; for every transition (q 1 , (1, a), q 1 ) where q 1 , q 1 ∈ Q 1 ∪ Q 1 , we have a transition (q 1 , (a, ⊥), q 1 ) in A ; and for every transition (q 2 , (2, b), q 2 ) where q 2 , q 2 ∈ Q 2 ∪ Q 2 , we have a transition (q 2 , (⊥, b), q 2 ) in A . By ( †), it follows that A represents the relation [[L(A)]].

(III) Note that L = (1|2) * = 2 * imposes no constraint on Rel(L). That is, Rel(L) is the set of all relations [[S]] so that S ⊆ 2 × A is regular. Any automaton A over 2 × A can be alternatively seen as a two-tape automaton A , having one head on each tape, where a transition (q, (i, a)q, ) in A corresponds to a transition in A from q to q reading letter a from tape i. Conversely, any two-tape automaton A can be converted into an NFA A over 2 × A. For both directions, the set of relations accepted by A is [[L(A)]]. These are precisely the relations in RAT, and hence the statement follows.

Complete proof of Theorem 1

Lemma 10. For every s ≥ 1, we have Rel((

1 * 2 * ) s ) = REC.
Proof. This is a consequence of a synchronization theorem, Theorem 5-(II), which implies that for every (1 * 2 * ) s -controlled language S there is a (1 * 2 * )-controlled language S so that

[[S]] = [[S ]

]. This fact, in conjunction with Proposition 1-(I), shows the statement.

In the lemma below, we extend the notion of concatenation to classes of relations in the natural way, i.e., element-wise. Lemma 11. For every δ ∈ N, we have Rel(L ≤δ-lag ) REG and Rel(L ≤δ-lag )•REC = REG.

Proof. Note that any relation

R ∈ Rel(L ≤δ-lag ) only contains pairs (u, v) so that -δ ≤ |u| -|v| ≤ δ. Hence the regular relation {(u, ε) | u ∈ A * } is not in Rel(L ≤δ-lag ),

and thus

Rel(L ≤δ-lag ) = REG. On the other hand, we have that any R ∈ Rel(L ≤δ-lag ) is regular, since it can be recognized by a nondeterministic automaton on two tapes with a look-ahead of δ, which can be simulated in the states of the automaton. Hence, Rel(L ≤δ-lag ) REG.

Since the concatenation of a regular relation and a recognizable relation is regular [START_REF] Berstel | Transductions and Context-Free Languages[END_REF], we are only left to show REG ⊆ Rel(L ≤δ-lag ) • REC. It is easy to see from their automata description that every regular relation R ∈ REG can be factored into a finite union of relations R 1 •R 2 so that R 1 is (12) * -controlled and R 2 is (1 * |2 * )-controlled. Since (12) * ∈ Rel(L ≤δ-lag ) for δ = 1, it follows that REG ⊆ Rel(L ≤1-lag ) • REC. Note that for every δ ≤ δ we have L ≤δ-lag ⊆ L ≤δ -lag . Then, by the above and monotonicity, REG ⊆ Rel(L ≤δ-lag ) • REC for every δ ≥ 1.

Proof of Theorem 1. (I)-(if)

Let n ∈ N so that shiftlag(L) < n. Since L is regular, this implies that there is some δ where all shifts of w are ≤δ -lagged for some δ , except perhaps the last n -1 shifts.

Claim 1. There is some δ so that for all w ∈ L and for all shifts i of w that are not among the last n -1 shifts, we have that they are ≤δ -lagged.

Proof. Remember that L is regular. Let A L be an NFA accepting the language L with a state space Q. Let δ = n(|Q| + 1) + 1. Suppose, by means of contradiction, that there is w ∈ L with a shift i ∈ {1, . . . , |w|} that is >δ -lagged, so that there are at least n -1 shifts to the right of i. Let us assume, without any loss of generality, that # 1 (w[1, i]) -# 2 (w[1, i]) > δ . Figure 2 contains an example. Since w ∈ L, let ρ : {0, . . . , |w|} → Q be an accepting run of A L on w. Let i ≤ i be the largest shift i < i that is ≤n-lagged, if there is any, or i = 1 otherwise.

w : Note that in [i , i] there cannot be more than n shifts, since otherwise w would have n consecutive >n-lagged shifts contradicting shiftlag(w) < n. Also, in [i , i] there must be

1 1 1 1 1 2 1 1 1 1 1 δ : i 1 i 2 i 3 i 4 i j i j 1
k = δ -n positions i ≤ i 1 < • • • < i k ≤ i so that for every j ∈ {1, . . . , k -1} # 1 (w[i j + 1, i j+1 ]) -# 2 (w[i j + 1, i j+1 ]) = 1, (3)
where, by definition of δ , k = n|Q| + 1 (cf. Figure 2). Remember that there are no more than n shifts in [i , i] and i is itself a shift; hence, since k > n|Q|, there must be

|Q| + 1 such positions i j1 < • • • < i j |Q|+1 so that there is no shift in [i j1 , i j |Q|+1 -1].
Then, there must be two distinct positions i j , i j ∈ {i j1 , . . . , i j |Q|+1 }, i j < i j , so that ρ(i j ) = ρ(i j ) and there is no shift in [i j , i j -1] (cf. Figure 2). We show that we can then "pump" the subword of w inside [i j , i j ] to obtain a larger word w ∈ L that has n shifts >n-lagged, that is, where shiftlag(w ) ≥ n. Indeed, for any l ∈ N, we have that

w = w[1, i j ] • (w[i j + 1, i j ]) l • w[i j + 1, |w|] ∈ L.
Note that w has as many shifts as w. Moreover, shift i in w corresponds now to shift î

= i + (l -1) • |[i j + 1, i j ]|
(w [1, î]) -# 2 (w [1, î]) > |w| + δ .
Therefore, the last n shifts of w are all >n-lagged, contradicting shiftlag(L) < n. The contradiction comes from assuming that for all δ there is w ∈ L and a >δ -lagged shift i of w that is not among the last n -1 shifts.

As a consequence of Claim 1, there must be some δ where all the positions occurring before the last s shifts are ≤δ -lagged.

Claim 2. There is some δ so that for all w ∈ L and all i so that w has at least n shifts in [i, |w|], we have that i is ≤δ -lagged.

Proof. Let δ be as in Claim 1. Take any position i so that there are at least n shifts in [i, |w|]. Take also the two positions i 1 ≤ i ≤ i 2 so that i 2 is a shift, i 1 is a shift or i 1 = 1, and there are no shifts in [i 1 + 1, i 2 -1]. By Claim 1, it follows that both i 1 and i 2 are ≤δ -lagged. Since w[i 1 + 1, i 2 ] is a string of only 1's or only 2's, it cannot be that |w[i 1 + 1, i 2 ]| > 2δ , as otherwise either i 1 or i 2 would not be ≤δ -lagged. It then follows that i must be ≤2δ -lagged. Hence, taking δ = 2δ , the statement follows.

A direct consequence of Claim 2 is that there is some δ so that (I)-(only if) Suppose that shiftlag(L) = ∞. Note that this means that for every s, δ ∈ N there is some w ∈ L that has s consecutive shifts >δ-lagged (because in particular there is some w ∈ L so that shiftlag(w) > max(s, δ)). We build an L-controlled relation

L ⊆ L ≤δ -lag • (1 * |2 * ) n
S ⊆ (2 × A) * so that [[S]] ∈ RAT \ REG.
Let A be any two-letter alphabet {a, b}. Let S ⊆ (2 × {a, b}) * consisting of all words u ⊗ v ∈ (2 × {a, b}) * so that u ∈ L, and for every i ∈ {1, . . . , |v|}, Note that every pair in the relation has almost the same number of a's: Let s = 2|Q | + 2, and let us define the constant K = s 2 |Q|. We hence define δ = 2K. There must then be some w = u ⊗ v ∈ S with s consecutive shifts that are >δ-lagged. Let 1 ≤ i 1 < • • • < i s ≤ |u| be the shifts in question. Let us assume, without any loss of generality, that w is minimal in length and that #

v[i] = a if i is a shift of u,
For every (u, v) ∈ [[S]], -1 ≤ # a (u) -# a (v) ≤ 1. ( †) Suppose,
1 (u[1, i 1 ]) -# 2 (u[1, i 1 ]) > δ.
Due to minimality of w, it is easy to see through a pumping argument, that the lengths of w[i 1 , i s ] and of w[i s + 1, |w|] are bounded by a function on s and |Q|.

Claim 3. |w| -i 1 ≤ s 2 |Q| = K.
Proof. Let ρ : [0, |w|] → Q be an accepting run of A S on w. For any l ∈ s we have that u[i l + 1, i l+1 ] is a string of 1's or a string of 2's.

Suppose that u[i l + 1, i l+1 ] is a string of 2's, and suppose that the string has length greater than |Q|. Then there are two distinct elements i, j ∈ [i l + 1, i l+1 ] so that i < j, u[i] = u[j] = 2 and ρ(i) = ρ(j). We then have that w = w [1, i] • w[j + 1, |w|] ∈ S and it has s consecutive >δ-lagged shifts, because we only removed positions labeled with 2. But this is not possible by minimality of w. Hence, u[i l + 1, i l+1 ] cannot contain more than |Q| elements 2, and thus

# 2 (u[i 1 + 1, i s ]) ≤ (s -1)|Q|. ( 5
)
Now suppose that u[i l + 1, i l+1 ] is a string of 1's, and suppose that the string has length greater than s|Q|. Then, there are two distinct elements i, j

∈ [i l + 1, i l+1 ] so that u[i] = u[j] = 2, ρ(i) = ρ(j) and i -j ≤ |Q|. We then have that w = w[1, i] • w[j + 1, |w|] ∈ S.
Further, w has s consecutive >δ-lagged shifts, because although we removed some positions marked with 1, we left sufficiently many (at least (s -1)|Q|) to make sure that, by [START_REF] Barceló | Graph logics with rational relations[END_REF],

# 1 (u[i 1 + 1, i] • u[j + 1, i l+1 ]) -# 2 (u[i 1 + 1, i] • u[j + 1, i l+1 ]) ≥ 0,
and hence that there are still s shifts >δ-lagged in w . However, this is not possible by minimality of w. Hence, u[i l + 1, i l+1 ] cannot contain more than s|Q| positions labeled 1, and thus

# 1 (u[i 1 + 1, i s ]) ≤ (s -1)s|Q|. ( 6
)
Then, by ( 5) and ( 6), the length of u[i 1 , i s ] is bounded by (s -1)|Q| + (s -1)s|Q| + 1.

A simpler consequence of the minimality of w is that

|[i s + 1, |w|]| ≤ |Q|. (7)
Then, summing up, [i (II)-(only if) Suppose shift(L) = ∞. We exhibit a relation of Rel(L) which is not in REC. We use the same relation as a previous part of this proof, but we repeat it here for the reader's convenience. Let A be any two-letter alphabet {a, b}. Let S ⊆ (2 × {a, b}) * consisting of all words u ⊗ v ∈ (2 × {a, b}) * so that u ∈ L, and for every i ∈ {1, . . . , |v|},

+1 = s 2 |Q| + 1. Thus, |w| -i 1 ≤ s 2 |Q| = K. Since δ = 2K < # 1 (u[1, i 1 ]) -# 2 (u[1, i 1 ]) and # 2 (u[i 1 + 1, |w|]) ≤ K by Claim 3, we have that # 1 (u) -# 2 (u) > K. ( 8
) Let w = u ⊗ v ∈ S
v[i] = a if i is a shift of u, and v[i] = b otherwise. It is plain that S is a regular L-controlled relation since L is regular, and hence that [[S]] ∈ Rel(L) is a rational relation. Next we show that [[S]] ∈ REC.
Note that every pair in the relation has almost the same number of a's:

For every (u, v) ∈ [[S]], -1 ≤ # a (u) -# a (v) ≤ 1. ( ‡) By means of contradiction, suppose that [[S]] ∈ REC. Then, by Proposition 1-(I), there is a 1 * 2 * -controlled language S ⊆ (2 × {a, b}) * so that [[S ]] = [[S]]. Let A S be an NFA recognizing S with statespace Q . Let u ⊗ v ∈ S be a word so that u has more than |Q | shifts, and hence [[u ⊗ v]] has more than |Q | letters a. Since [[S ]] = [[S]] there is some w = u ⊗ v ∈ S so that [[u ⊗ v ]] = [[u ⊗ v]]. Let ρ : [0, |w |] → Q be
an accepting run of A S on w . Note that u has at most one shift. Let i be the only shift of u (if u has no shifts the reasoning is only easier). Since v has more than than |Q | a's, there must be two positions j 1 , j 2 of w so that ρ

(j 1 ) = ρ (j 2 ), v [j 1 ] = v [j 2 ] = a and either 1 ≤ j 1 < j 2 ≤ i or i < j 1 < j 2 ≤ |w |. Note then that w [1, j 1 ] • (w [j 1 + 1, j 2 ]) n • w [j 2 + 1, |w |] ∈ S for every n ∈ N. Take n = 4, and let w = w [1, j 1 ] • (w [j 1 + 1, j 2 ]) 4 • w [j 2 + 1, |w |] ∈ S . Note that [[w ]
] has at least two more a's in one component than in the other, because w has at most a difference of one a between its components, due to ( ‡). Hence, w is in contradiction with ( ‡), and it cannot be that

A.1 Complete proof of Theorem 2

Let Q be the statespace of A. Given w ∈ L(A) and an accepting run ρ : [0, |w|] → Q of A on w, the path P on G A induced by w, ρ is defined as the sequence of edges e 1 • • • e |w| of G A , so that e i is the edge between ρ(i -1) and ρ(i) labeled with (ρ(i -1), w[i], ρ(i)).

(I)-(if) Let n ∈ N.
We show that assuming one of the two properties is met, there is some w ∈ L(A) with shiftlag(w) ≥ n.

If G A has a heterogeneous cycle C het with # 1 (C het ) = # 2 (C het ), one can iterate this cycle to obtain a word w with shiftlag(w) > n. In other words, suppose that w ∈ L(A) with an accepting run ρ : [0, |w|] → Q so that the path P induced by w, ρ contains a heterogeneous unbalanced cycle C het between the positions i ≤ j where we assume, without any loss of generality, # 1 (C het ) > # 2 (C het ) > 0. Since this means that ρ(i -1) = ρ(j), we have that

w m = w[1, i -1] • (w[i, j]) m • w[j + 1, |w|] ∈ L(A) for every m ∈ N, and # 1 (w[i, j]) > # 2 (w[i, j]) > 0 because # 1 (C het ) > # 2 (C het ) > 0.
Hence, if we take m = |w| + 2n, it is easy to see that w m has n consecutive shifts that are >n-lagged. Thus, shiftlag(w m ) ≥ n.

If, on the other hand, there is a path from a homogeneous cycle C hom to a heterogeneous cycle C het in G A , then we show that we can iterate both cycles enough times to obtain a word w ∈ L(A) so that shiftlag(w) > n. Suppose w ∈ L(A) with an accepting run ρ : [0, |w|] → Q, so that the path P induced by w, ρ contains both cycles, where C hom occurs before C het . That is, there are 0 < i < j ≤ i < j ≤ |w| so that ρ(i) = ρ(j) and C hom is the cycle induced by w[i, j], ρ| [i-1,j] , and

ρ(i ) = ρ(j ) and C het is the cycle induced by w[i , j ], ρ| [i -1,j ] .
Note that for any m, l ∈ N we have

w m,l = w[1, i] • (w[i + 1, j]) m • w[j + 1, i ] um • (w[i + 1, j]) l • w[j , |w|] v l ∈ L(A).
If we take m = (n + 2)|w| and l = n, we obtain that

|# 1 (u m ) -# 2 (u m )| > (n + 1)|w|, |v l | ≤ n|w|, and shift(v l ) > n. Therefore, w m,l = u m • v l is so that shiftlag(w m,l ) ≥ n.
Thus, if any of the conditions in (I) is met, we must have that shiftlag(L(A)) = ∞.

(I)-(only if) Suppose now that shiftlag(L(A)) = ∞. We choose n = 2|Q| + 1, and show that any accepting run of A on w ∈ L(A) so that shiftlag(w) ≥ n must induce a path P containing either (i) a heterogeneous cycle C het with # 1 (C het ) = # 2 (C het ), or (ii) a homogeneous cycle C hom and a heterogeneous cycle C het , so that C hom occurs before C het in P . Note that once this is verified, the statement follows.

Let ρ : [0, |w|] → Q be an accepting run of A on w so that shiftlag(w) > n. Consider the path P on G A induced by ρ, w. By definition of shiftlag(w) > n, there must be n consecutive >n-lagged shifts 1 ≤ a 1 < a 2 < • • • < a n ≤ |w| in w. Without any loss of generality, assume that

# 1 (w[1, a 1 ]) -# 2 (w[1, a 1 ]) > n, ( †)
and that for every odd index i, w[a i ] = 1 and for every even index i, w[a i ] = 2. Since n > 2|Q|, it follows that there must be a i < a j < a l with ρ(a i ) = ρ(a j ) = ρ(a l ), and thus there must be a heterogeneous cycle inside P (the one defined between positions i + 1 and l). Further, by ( †), there are positions 0

≤ b 1 < • • • < b n ≤ a 1 so that # 1 (w[b i + 1, b i+1 ]) - # 2 (w[b i + 1, b i+1 ]) = 1 for every i ∈ n -1. Since n > |Q|, there must be two b i < b j so that ρ(b i ) = ρ(b j ). Hence the cycle C of P induced by w[b i + 1, b j ], ρ| [bi,bj ] necessarily verifies # 1 (C) > # 2 (C). ( ‡)
Now there are two possibilities.

If # 2 (C) > 0 then C is heterogeneous and with # 1 (C) = # 2 (C) by ( ‡), verifying condition (i).
The other possibility is that C is homogeneous. Since there is a path from C to C het , the condition (ii) is met.

(II)-(if) Suppose that G A contains a heterogeneous cycle C het . Then, there must be some word w ∈ L(A) with an accepting run ρ : [0, |w|] → Q so that the path P induced by w, ρ contains C het between positions i ≤ j of P . Therefore ρ(i -1) = ρ(j), and

w n = w[1, i -1] • (w[i, j]) n • w[j + 1, |w|] ∈ L(A) for any n ∈ N.
Note that as a consequence of C het being heterogeneous, w[i, j] contains at least one letter 1 and one letter 2. Thus, w n contains at least n shifts, and therefore shift(L(A)) = ∞.

(II)-(only if) Suppose that shift(L(A)) = ∞, that is, for every n ∈ N there is a word w ∈ L(A) so that shift(w) > n. Take n = 2|Q|, and let w ∈ L(A) so that shift(w) > n.

There must be more than |Q| shifts in w with the same letter i ∈ 2. Without any loss of generality, suppose there are shifts 1

≤ i 1 < • • • < i |Q|+1 ≤ |w| so that w[i j ] = 1
for all j ∈ {1, . . . , |Q| + 1}. Then there must be two i j1 < i j2 so that ρ(i j1 ) = ρ(i j2 ). Hence, the word w[i j1 + 1, i j2 ] has length ≥ 2, and contains at least one letter 1 (the last letter) and at least one letter 2 (the first letter, as otherwise i j1 would not be a shift with letter 1). It then follows that the path on G A induced by

w[i j1 + 1, i j2 ], ρ| [ij 1 ,ij 2 ] is indeed a heterogeneous cycle.
(III) This is shown in [START_REF] Sakarovitch | Elements of Automata Theory[END_REF]Lemma 6.7,p. 603].

Complete proof of Theorem 5

For the proof of Theorem 5 we use the following lemma. (II) By Theorem 2-(II) there are no heterogeneous cycles in G A , and every SCC S of G A is hence homogeneous or edgeless. Shifts can hence only occur in transitions between SCC's in G A (i.e., transitions that involving states from two different SCC's). Since the condensation of G A is a DAG, there are not more than |A| different SCC that an accepting run of A for a word can go through. Hence, shift(L(A)) < n, where n is the number of SCC's of A minus one. Since n ≤ |A|, the statement follows.

(III) By Theorem 2-(III) all cycles C in G A are so that # 1 (C) = # 2 (C). By means of contradiction, suppose that there is some w ∈ L(A) with lag(w) > |Q|, and an accepting run ρ : [0, |w|] → Q of A on w, where Q is the statespace of A. Further, suppose that w is minimal in length; that is, any word w shorter than w is so that lag(w ) ≤ |Q|. Since |w| > |Q|, let 0 ≤ i < j ≤ |w| be any two indices so that ρ(i) = ρ(j). Note that the path induced by w[i, j -1], ρ| [i,j] is a cycle C, and by hypothesis it must be so that #

1 (C) = # 2 (C). Therefore, # 1 (w[i, j -1]) = # 2 (w[i, j -1]). Consider then the word w = w[1, i -1] • w[j, |w|].
We have that w ∈ L(A) and that lag(w ) = lag(w) because we removed a subword with equal number of letters 1 and 2. This is an absurd by minimality of w. Thus, there cannot be that lag(L(A)) > |Q| and the statement follows.

Proof of Theorem 5. We start by showing (II) and (IV) because we use these items in the proof of (I).

(II) Let S be an L-controlled regular language S ⊆ (2 × A) * with shift(L) < ∞. We assume, without any loss of generality, that L = {u | u ⊗ v ∈ S}. Let A be an NFA recognizing S with statespace Q, initial state q 0 and set of final states Q F . Note that, since S is L-controlled, one can build in linear time an automaton A L recognizing L, having the same statespace Q (the transformation consists in replacing every transition (q, (i, a), q ) with (q, i, q )). Hence, by Lemma 12-(II), shift(L) ≤ |Q|.

Let us call 1-edge (resp. 2-edge) to an edge of G A labeled with a transition reading the letter 1 (resp. 2) in its first component. Note that every SCC of G A is homogeneous or edgeless by Theorem 2-(II). Hence, if a SCC has only 1-edges, we call it a 1-SCC. Otherwise (if it has only 2-edges), we call it a 2-SCC. For the purpose of this proof, it is indifferent whether we categorize edgeless SCC's as 1-SCC's or 2-SCC's, but just to fix nomenclature, let us call them 1-SCC's. Hence, every SCC in G A is a 1-SCC or a 2-SCC.

Note that any path on G A induces a (possibly empty) path on con(G A ) (cf. Figure 3). By acyclicity there are at most exponentially many paths in con(G A ).

For any (possibly empty) path P in con(G A ) and final state q ∈ Q F , let S P,q be the set of all words w ∈ S with an accepting run of A ending in q and inducing the path P in con(G A ). Hence, S = {S P,q | P is a path of con(G A ) and q ∈ Q F }.

We conclude the proof by showing that for every path P in con(G A ) and q ∈ Q F we can build, in polynomial time, a (1 * 2 * )-controlled automaton A P,q so that [[L(A P,q )]] = [[S P,q ]].

Claim 4. For every path P in con(G A ) and q ∈ Q F , an automaton A P,q so that [[L(A P,q )]] = [[S P,q ]] and

L(A P,q ) is (1 * 2 * )-controlled is computable in polynomial time in |A|. G A con(G A ) q 0 q 1 q 2 q 3 q 4 q 5 q 6 q 0 q 1 q 2 q 3 q 4 q 5 q 6 path in G A con(G A ) path in 1 1 1 2 2 1 1 2 1 2 1-SCC 1-SCC 2-SCC 1-SCC q1 2 q5 q12 q4 q 2 1 q 3 q 3 2 q 6 q5 1 q6
Figure 3 Example of path in GA and corresponding path in con(GA). For simplicity, we assume that the alphabet is singleton A = {a}, and we therefore omit 'a' in the transitions.

Proof. We can assume, without any loss of generality, that P is not empty, and contains a vertex corresponding to a 1-SCC, or a 1-edge, and a vertex corresponding to a 2-SCC, or a 2-edge, since otherwise S P,q would be trivially (1 * 2 * )-controlled and an automaton can be easily built in polynomial time in |A|.

Let G P,q be the transition graph of the NFA recognizing S P,q , which is the result of removing from A all the states from SCC's that are not in P and its associated transitions, and all transitions (q, (i, a), q ) not appearing in P , so that q, q do not belong to the same SCC. Note that con(G P,q ) is a directed chain, where there is at most one edge traveling between two vertices from different SCC's; the shape of G P,q is depicted in the top picture of Figure 4. Let states q0,q (P ) be the sequence of states appearing in P , prefixed with q 0 and suffixed with q; that is, if P = (v 1 , (q 1 , (i 1 , a 1 ), q 1 ), v 2 ), . . . , (v n , (q n , (i n , a n ), q n ), v n+1 ), then states q0,q (P ) = q 0 , q 1 , q 1 , . . . , q n , q n , q. The idea is that states q0,q (P ) represents the sequence of states that any accepting run of the automaton recognizing S P,q has to go through (there could, however, be some repetitions of states if the incoming and outgoing state of a SCC are the same in P ). For example, in the path P depicted in Figure 3, we have states q0,q6 = q 0 , q 1 , q 5 , q 5 , q 6 , q 6 . In the top picture of Figure 4, the vertices in states q0,q (P ) are depicted as bullets. Consider the graph G P,q,1 as the result of 1. removing all 2-edges from G P,q , 2. removing all vertices without incoming or outgoing edges that remain, and 3. associating vertices to make it a connected graph, so that the relative appearance of the 1-SCC's and 1-edges given by P is preserved. This construction is shown in Figure 4. Let v 1 , v 1 be the first and last vertices in the construction of G P,q (cf. Figure 4). That is, v 1 corresponds to the first vertex in states q0,q (P )

v 1 v 2 v 2 v 1 1-SCC 1-SCC 2-SCC 1-SCC 2-SCC 1-SCC 2 1 1 1 2 1-SCC 1-SCC 1-SCC 1-SCC 1 1 1 2-SCC 2-SCC 2 2
G P,q G P,q,1 G P,q,2 G P,q

Figure 4

Example of construction of G P,q from GP,q. The SCC are abstracted as boxes, labeled "1-SCC" or "2-SCC" depending on the sort of SCC they are. Edges are also labeled depending on whether they are 1-edges or 2-edges. Dotted lines are used to identify two vertices as being the same.

that has an outgoing 1-edge in G P,q , and v 1 corresponds to the last vertex in states q0,q (P ) that has an incoming 1-edge in G P,q .

We define G P,q,2 and v 2 , v 2 analogously to G P,q,2 and v 1 , v 1 , but removing 1-edges instead (cf. Figure 4). Now, let G P,q be the transition graph resulting from composing G P,q,1 with G P,q,2 by associating v 1 with v 2 (cf. Figure 4). Let us define the automaton A P,q as having the transition relation defined by G P,q , where the initial state is v 1 and the set of final states is {v 2 }. We then have that A P,q is (1 * 2 * )-controlled and [[L(A P,q )]] = [[S P,q ]].

The statement follows directly from the previous claim, defining S = P,q L(A P,q ) for every path P of con(G A ) and q ∈ Q F , and defining A S as the union of all automata A P,q 's. Then, S is a (1 * 2 * )-resynchronization of S, and A S can be built in exponential time.

We now show another claim concerning (1 * 2 * )-controlled languages, that will be useful in the proof of (I).

* |2 * )-controlled automata A tail 1 , . . . , A tail t so that [[L(A)]] = i∈t [[L(A head i ) • L(A tail i )]].
Proof. In the scope of this proof, let Q be the statespace of A, with initial state q init and set of final states Q F . Let us define the automaton A over the same alphabet as A with the statespace Q × Q × 2, with a transition ((q 1 , q 2 , 1), (1, a), (q 1 , q 2 , 2)) if (q 1 , (1, a), q 1 ) is a transition of A, and ((q 1 , q 2 , 2), (2, a), (q 1 , q 2 , 1)) if (q 2 , (2, a), q 2 ) is a transition of A. Note that for every q 1 , q 1 , q 1 , q 2 ∈ Q, A [(q 1 , q 2 , 1), (q 1 , q 2 , 1)] is (12) * -controlled. Also, note that for every q 1 , q 2 , q 2 ∈ Q and q f ∈ Q F , L(A [(q init , q 2 , 1)(q 2 , q 2 , 1)]) Observe that for any q 1 , q 1 , q 2 , q 2 ∈ Q, w ∈ L(A [(q 1 , q 2 , 1)(q 1 , q 2 , 1)]) if, and only if, w odd ∈ L(A[q 1 , q 1 ]) ∩ ({1} × A) * and w even ∈ A[q 2 , q 2 ] ∩ ({2} × A) * , where w odd (resp. w even ) is the subword of w of odd (resp. even) positions.

L head 1 • (L(A[q 2 , q f ]) ∩ ({2} × A) * ) L tail 1 and L(A [(q init , q 2 , 1)(q 1 , q f , 1)]) L head 2 • (L(A[q 1 , q 2 ]) ∩ ({1} × A) * ) L tail
From the definition of L head From any accepting run of A [(q init , q 2 , 1), (q 2 q 2 , 1)] on w 1 and an accepting run of A[q 2 , q f ] on w 2 ∈ ({2} × A) * one can build an accepting run of A on (w 1 ) odd

• (w 1 ) even • w 2 , where [[(w 1 ) odd • (w 1 ) even • w 2 ]] = [[w 1 • w 2 ]].
Similarly, from an accepting run of A [(q init , q 2 , 1), (q 1 , q f , 1)] on w 1 and an accepting run of w 2 ∈ ({1} × A) * on A[q 1 , q 2 ] one can build an accepting run of A on (w

1 ) odd • w 2 • (w 1 ) even , where [[(w 1 ) odd • w 2 • (w 1 ) even ]] = [[w 1 • w 2 ]]
. Indeed, note that in both cases, (w 1 ) odd = (w 1 ) {1}×A and (w 1 ) even = (w 1 ) {2}×A .

Conversely, for every accepting run of A on w, let w be the interleaving of w {1}×A [1, m] and w {2}×A [1, m], where m = min(|w {1}×A |, |w {2}×A |) (more formally, it is the word w

∈ sh(w {1}×A [1, m], w {2}×A [1, m]) so that w ∈ (({1} × A) • ({2} × A)) * ). If |w {1}×A | ≤ |w {2}×A |
then for some q 2 , q 2 ∈ Q and q f ∈ Q F there is an accepting run of A [(q init , q 2 , 1), (q 2 , q 2 , 1)] on w , and accepting run of

A[q 2 , q f ] on w[2m + 1, |w|] ∈ ({2} × A) * . Similarly, if |w {1}×A | > |w {2}×A |
then for some q 2 , q 1 ∈ Q and q f ∈ Q F there is an accepting run of A [(q init , q 2 , 1)(q 1 , q f , 1)] on w , and accepting run of

A[q 1 , q 2 ] on w[2m + 1, |w|] ∈ ({1} × A) * . In both cases, observe that [[w • w[2m + 1, |w|]]] = [[w]].
Summing up, for every pair (u, v)

∈ A * × A * , there is a word w ∈ L head i • L tail i with [[w]] = (u, v) for some i ∈ 2 if, and only if, there is some w ∈ L(A) with [[w ]] = (u, v).
Hence, defining L as the union of all the above L head languages for all possible q 2 , q 2 , q 1 ∈ Q and q

f ∈ Q F , it follows that [[L(A)]] = [[L ]]. Since every L head i is ( 12
) * -controlled and every L tail i is (1 * |2 * )-controlled, and since automata for these languages can be built in polynomial time, the statement follows.

(IV) This follows from [27, Proposition 6.9, pp. 604-605]. Although in the cited work the complexity is not given, it follows from the proof that it can be built in exponential time. In fact, note that it suffices to build an automaton whose every state has a buffer of lag(L) letters.

(I) Let S be an L-controlled regular language S ⊆ (2 × A) * with shiftlag(L) < ∞. Let A be an NFA recognizing S with statespace Q, initial state q 0 and set of final states Q F .

By Theorem 2-(I), there are no paths from homogeneous SCC's to heterogeneous SCC's in G A (and there are no heterogeneous cycles C with # 1 (C) = # 2 (C)). Let Q hom be the set of all vertices of G A that are reachable from a vertex of a homogeneous SCC. Note that Q hom includes all vertices in homogeneous SCC's, plus some vertices from edgeless SCC's. Also, note that the subgraph of G A induced by Q hom has no heterogeneous cycles. Let Q het = Q \ Q hom . Hence, Q het includes all vertices in heterogeneous SCC's and some vertices in edgeless SCC's. Also, by the property before, the subgraph of G A induced by Q het is connected. Figure 5 contains an example. Further, any path P in G A is of the form (1) P • (q, τ, q ) • P , (2) P , or

Figure 5

Example of GA with the subgraphs induced by Q hom and Q het . For simplicity we assume that A = {a} and we hence omit the letter a when depicting edges labeled by (i, a). q ∈ Q het , q ∈ Q hom , and τ is a transition of A.

Let A het be A restricted to Q het , and let A hom be A restricted to Q hom . For every pair of states q het ∈ Q het and q hom ∈ Q hom , let L q het ,q hom be the union of all L(A het [q 0 , q het ]) • {(i, a)} • L(A hom [q hom , q f ]) for every q f ∈ Q F and (i, a) ∈ 2 × A so that (q het , (i, a), q hom ) is a transition of A (if there is no such (i, a), let L q het ,q hom = ∅). Note that in the definition above it could be that, for example, q 0 ∈ Q het , and we remind the reader that A het [q, q ] (resp. A hom [q, q ]) where q or q are not in Q het (resp. Q hom ) denotes the automaton accepting the empty language. Let L hom = q f ∈Q F L(A hom [q 0 , q f ]) and L het = q f ∈Q F L(A het [q 0 , q f ]). It follows that S = L hom ∪ L het ∪ q het ∈Q het ,q hom ∈Q hom L q het ,q hom . We show that we can build, in exponential time, a (12) * (1 * |2 * )-controlled automaton for each of these languages. Since the case of L q het ,q hom is more general than L hom and L het , we will only prove this case.

Note that by definition of A het and A hom , and since G A has no unbalanced heterogeneous cycles, for every q het ∈ Q het , q hom ∈ Q hom , q f ∈ Q F we have that lag(L(A het [q 0 , q het ])) < ∞ and shift(L(A hom [q hom , q f ])) < ∞. Hence, by Lemma 12, lag(L(A het [q 0 , q het ])) ≤ n, shift(L(A hom [q hom , q f ])) ≤ n, for n = |A|.

By the already shown item (II), let A hom q hom ,q f be a (1 * 2 * )-controlled automaton so that [[L(A hom [q 0 , q hom ])]] = [[L(A hom q0,q hom )]]. By item (IV), let A het q0,q het be a (12) * (1 ≤n |2 ≤n )-controlled automaton so that [[L(A het [q 0 , q het ])]] = [[L(A het q0,q het )]]. These automata can be built in exponential time.

We finally show that a (12) * (1 * |2 * )-controlled automaton for L q het ,q hom can be built from A het q0,q het and all the A hom q hom ,q f 's for all q f ∈ Q F in polynomial time, and thus the statement follows. Claim 6. A (12) * (1 * |2 * )-controlled automaton for L q het ,q hom can be built from A het q0,q het and all the A hom q hom ,q f 's in polynomial time.

Proof. It is plain that from A hom q hom ,q f (which is 1 * 2 * -controlled) one can build 1 * -controlled automata B hom-1 * 1 , . . . , B hom-1 * t and 2 * -controlled automata B hom-2 * 1 , . . . , B hom-2 * t in polynomial time so that

L(A hom q hom ,q f ) = i∈t L(B hom-1 * i ) • L(B hom-2 * i ) .
Also, it is easy to see that from A het q0,q het (which is ( 12

) • L(A het-1 * i ) • L(A het-2 * i )
We then have that

[[L q het ,q hom ]] = ∈2 [[ i∈t,j∈s L(A het-(12) * j ) • L(A het-1 * j ) • L(A het-2 * j ) • L ,q het ,q hom • L(B hom-1 * i ) • L(B hom-2 * i )]]
where L ,q het ,q hom = {( , a) | (q het , ( , a), q hom ) in A}. Note that for = 1 we have

[[ i∈t,j∈s L(A het-(12) * j ) • L(A het-1 * j ) • L(A het-2 * j ) • L 1,q het ,q hom • L(B hom-1 * i ) • L(B hom-2 * i )]] = [[ i∈t,j∈s L(A het-(12) * j ) • L 1,i,j ]],
where

L 1,i,j = L(A het-1 * j ) • L 1,q het ,q hom • L(B hom-1 * i ) • L(A het-2 * j ) • L(B hom-2 * i ).
Since L 1,i,j is 1 * 2 * -controlled, we can apply the previous Claim 5 on L 1,i,j obtaining (12) * -controlled automata A head

  This class will be denoted by REC. Regular relations Let ⊥ ∈ A be a new alphabet letter. A pair (w 1 , w 2 ) of words from A * can be encoded by a single word of length max(|w 1 |, |w 2 |) over the alphabet (A ∪ {⊥}) × (A ∪ {⊥}): its ith letter is the pair containing the ith letter of w 1 and the ith letter of w 2 , with ⊥ used when i is greater than the length of w 1 or w 2 . For example, the encoding for the words of the figure of page 2 is (a, b)(b, a)(a, a)(b, a)(b, b)(⊥, a). A regular relation R

Theorem 7 .Corollary 8 .

 78 Let L ⊆ 2 * be a regular language. Then (I) Rel(L) is effectively closed under union, alphabetic morphisms, and inverse alphabetic morphisms; (II) If L is Parikh-injective, then Rel(L) is effectively closed under intersection; (III) if L is both Parikh-injective and Parikh-surjective, then Rel(L) is effectively closed under complement. Proof idea. We prove only item (III). Let S ⊆ (2×A) * be an L-controlled relation. We show that [[S]] c = [[S c ∩ (L ⊗ A * )]], where S c , [[S]] c denote the complement of S, [[S]] respectively, and L ⊗ A * denotes the set of all words u ⊗ v where |u| = |v|, u ∈ L and v ∈ A * . [⊆] Suppose (u, v) ∈ [[S]]. We show that there must be some w ∈ S c ∩ (L ⊗ A * ) so that (u, v) = [[w]]. By Parikh surjectivity and injectivity, there is exactly one word w ∈ L so that Π(w ) = (|u|, |v|). Let w = u ⊗ v ∈ (2 × A) * be the only word so that u = w and [[w]] = (u, v). Note that w ∈ S and that its projection onto the first component (i.e., w ) is in L. Therefore, w ∈ S c ∩ (L ⊗ A * ). [⊇] Assume w ∈ S c ∩ (L ⊗ A * ) and suppose that [[w]] ∈ [[S]]. Then, there is some w ∈ S so that [[w ]] = [[w]]. It cannot be that w = w, as it would be in contradiction with w ∈ S c ∩ (L ⊗ A * ). Since L is Parikh-injective, and w, w are L-controlled, w = w , as otherwise [[w ]] = [[w]]. This contradicts w∈ S c ∩ (L ⊗ A * ). Thus, [[w]] ∈ [[S]] and [[S]] c ⊇ [[S c ∩ (L ⊗ A * )]]. If L ⊆ 2 * isParikh-injective and Parikh-surjective, then Rel(L) is an effective boolean algebra, closed under alphabetic morphisms and inverse alphabetic morphisms. Observe that in this context, REG and REC are simply two examples of the (infinitely) many such well-behaved classes. Example 9. REC and REG are effective boolean algebras because they correspond to Rel(1 * 2 * ) and Rel((12) * (1 * |2 * )), where 1 * 2 * , (12) * (1 * |2 * ) are Parikh-injective and Parikh-surjective. Rel((122) * (112) * ) is effectively closed under intersection.

  and thus any relation in Rel(L) is a finite union of products of languages. Therefore, Rel(L) ⊆ REC. (II)-[⊇] Let R ⊆ A * ×A * be a regular relation, represented by an NFA A over the alphabet (A ∪ {⊥}) 2 , where (u 1 , u 2 ) is in R if and only if u 1 ⊗ u 2 ∈ L(A), where u i ∈ (A ∪ {⊥}) * is the result of padding u i with a suffix of max(|u 1 |, |u 2 |) -|u i | letters ⊥. Let Q be the statespace of A. We produce an NFA A over 2 × A so that [[L(A )]] = R and L

5 Figure 2

 52 Figure 2 Example, where w has a prefix 1111121111112 after which it has n -1 shifts, n = 4, δ = 9, and |Q| = 1. Shift positions are circled.

1 *

 1 |2 * ) n contains all words with at most n shifts, and L ≤δ -lag is the (regular) language of all words with ≤δ -lagged positions. Since Rel(L ) = REC for L = (1 * |2 * ) n by Lemma 10, we obtain that Rel(L ) = REG for L = L ≤δ -lag • (1 * |2 * ) n by Lemma 11. Finally, as stated in (4), we have that L ⊆ L where Rel(L ) = REG. Applying monotonicity, we then have Rel(L) ⊆ REG.

  and v[i] = b otherwise. It is plain that S is a regular L-controlled relation since L is regular, and hence that [[S]] ∈ Rel(L) is a rational relation. Next we show that [[S]] ∈ REG.

  by means of contradiction, that [[S]] is regular and therefore, by Proposition 1, [[S]] ∈ Rel(L ) for L = (12) * (1 * |2 * ). Hence, there must be some L -controlled relation S ⊆ (2 × {a, b}) * so that [[S ]] = [[S]]. Let A S be an NFA accepting S with statespace Q, and let A S be an NFA accepting S with statespace Q .

  be the corresponding word in S , so that [[w]] = [[w ]]. Let ρ : [0, |w |] → Q be an accepting run of A S on w . Note that u can be factored into u = u 1 •u 2 with u 1 ∈ (12) * and u 2 ∈ 1 * . (The other possibility, u 2 ∈ 2 * , is only easier.) Notice that u[|u| -K, |u|] contains s shifts, by Claim 3, and in particular s/2 shifts labeled with 1. Therefore, w[|u| -K, |u|] contains at least s/2 letters (1, a) by definition of S. By (8), we have that |u 2 | ≥ K. Thus, u 2 must contain at least s/2 positions labeled with a. Since s/2 = |Q | + 1, there must be two distinct positions |u 1 | < i < j ≤ |w | labeled with a so that ρ (i) = ρ (j). Consider then w = w [1, i] • (w [i + 1, j]) 4 • w [j + 1, |w |]. Note that w ∈ S . By property ( †), we had that [[w ]] has the same quantity of a's (plus-minus one) in the first and second components. Therefore, [[w ]] has at least two more a's in its first component than in its second component. Hence, due to property ( †), it cannot be that [[w ]] ∈ [[S]], and thus [[S]] = [[S ]]. The contradiction comes from assuming that there exists an L -controlled language S so that [[S ]] = [[S]]. Hence, [[S]] ∈ REG.

(

  II)-(if) Let shift(L) < n. Note that L = (1 * 2 *) n contains all words with less than n shifts. Hence, L ⊆ L . By Lemma 10, Rel(L ) = REC, and since L ⊆ L , it follows that Rel(L) ⊆ REC by monotonicity.

  [[S ]] = [[S]]. Therefore, [[S]] ∈ REC and thus Rel(L) ⊆ REC. (III) This is direct by definition of REG bld . (IV) This is direct from definition of Rel(L) and Proposition 1-(III).

Lemma 12 (

 12 Bounds for shiftlag, shift, lag). Given an NFA A over the alphabet 2 with statespace Q,(I) if shiftlag(L(A)) < ∞, then shiftlag(L(A)) ≤ |Q|; (II) if shift(L(A)) < ∞, then shift(L(A)) ≤ |Q|; (III) if lag(L(A)) < ∞, then lag(L(A)) ≤ |Q|.Proof. Assume without any loss of generality that A is trim. Given a set of vertices S, let A| S be the NFA whose set of initial states is S, and its transition relation corresponds to the subgraph of G A induced by all the vertices reachable from S.(I) By Theorem 2-(I) every SCC S of G A is so that (a) S is edgeless, or (b) S is homogeneous and all SCC's S reachable from S are homogeneous or edgeless, or (c) S is heterogeneous, and all simple cycles C in S are so that # 1 (C) = # 2 (C).Let us analyze each case separately. Let S 1 , . . . , S n be the set of SCC's reachable from S (excluding S). (a) Then, shiftlag(L(A| S )) ≤ 1 + shiftlag(L(A| S1∪•••∪Sn )). (b) Then, any word w accepted by A| S is contained in (1 * 2 * ) ≤l , where l is the number of SCC's in G A| S . Therefore, shift(L(A| S )) ≤ l and therefore shiftlag(L(A| S )) ≤ l. (c) We then have that any word w in L(A| S ) is of the form w = u•v where u ∈ i≤|S| (sh(1 i , 2 i )) * and v ∈ L(A| S1∪•••∪Sn ). Note that there are no positions >|S|-lagged in u, and position |u| is 0-lagged in w. Thus, shiftlag(L(A| S )) ≤ max(|S|, shiftlag(L(A| S1∪•••∪Sn ))). Combining (a), (b) and (c), and by the fact that con(G A ) is a DAG, we obtain that shiftlag(L(A)) ≤ |A|.

Claim 5 .

 5 For any (1 * 2 * )-controlled automaton A one can build, in polynomial time, (12) *controlled automata A head 1 , . . . , A head t and (1

are ( 12 )

 12 * (1 * |2 * )-controlled, and that automata recognizing L head i , L tail i can be obtained in polynomial time.

i

  and L tail i and the previous observation, we show that for any word w ∈ L head i • L tail i there is some w ∈ L so that [[w]] = [[w ]], and vice versa.

1 • L tail 1 and L head 2 • L tail 2

 1122

( 3 )

 3 P , where P is a (possibly empty) path of the subgraph of G A induced by Q het , P is a (possibly empty) path of the subgraph of G A induced by Q hom ,

1 ,)))

 1 . . . , A head m and (1 * |2 * )-controlled automata A tail 1 , . . . , A tail m so that[[L 1,i,j ]] = k∈m [[L(A head k ) • L(A tail k )]]. in polynomial time. Defining L 1,i,j = k∈m L(A head k ) • L(A tail k ), we obtain that L 1,i,j is (12) * (1 * |2 * )-controlled, and an automaton for L 1,i,j can be computed in polynomial time.• L(A het-1 * j ) • L(A het-2 * j ) • L 1,q het ,q hom • L(B hom-1 * i ) • L(B hom-2 * i het-(12) * j ) • L 1,i,j ]],where note thatL 1 = i∈t,j∈s L(A het-(12) * j ) • L 1,i,j is (12) * (1 * |2 * )-controlled,and an automaton for L 1 can be built in polynomial time.For = 2 we apply a similar reasoning,• L(A het-1 * j ) • L(A het-2 * j ) • L 2,q het ,q hom • L(B hom-1 * i ) • L(B hom-2 * i • L 2,i,j ]]this time takingL 2,i,j = L(A het-1 * j ) • L(B hom-1 * i ) • L 2,q het ,q hom • L(A het-2 * j ) • L(B hom-2 * i ).and obtaining, through Claim 5, a (12) * (1 * |2 * )-controlled language L 2 so that [[ i∈t,j∈s L(A het-(12) * j ) • L(A het-1 * j ) • L(A het-2 * j ) • L 2,q het ,q hom • L(B hom-1 * i ) • L(B hom-2 * i )]] = [[L 2 ]].

  A[START_REF] Berstel | Transductions and Context-Free Languages[END_REF][START_REF] Elgot | On relations defined by generalized finite automata[END_REF]. Examples of relations in REG \ REC are prefix, equality, or equal length. Examples of relations in RAT\REG are suffix, given by

a∈A (ε, a) * • a∈A (a, a) * ; subword: a∈A (ε, a) * • a∈A (a, a) * • a∈A (ε, a) * , and subsequence: a∈A (ε, a) ∪ (a, a) * .

  injective, and Parikh-surjective if the function Π : L → N k 0 is surjective.

	Example 6.
	(12)

*

(1 * |2 * ) and 1 * 2 * are Parikh-injective, while (1|2) * is not. It can easily be shown that

L = w * 1 • w * 2 • • • w * ⊆ k * is Parikh-injective if ≤ k

and {Π(w 1 ), . . . , Π(w )} generate a linear subspace of (N 0 ) k of dimension . For example, (122) * (112) * is Parikh-injective. (12) * (1 * |2 * ), 1 * 2 * , and (1|2) * are Parikh-surjective, but (122) * (112) * is not Parikhsurjective.

  ) * (1 ≤n |2 ≤n )) one can build (12) *controlled automata A het-(12) * 1 , . . . , A het-(12) * s , 1 ≤n -controlled automata A het-1 * 1 , . . . , A het-1 * t and 2 ≤n -controlled automata A het-2 * 1 , . . . , A het-2 *

			s	in polynomial time, so that
	L(A het q0,q het ) =	L(A	het-(12)
	i∈s

* i

Acknowledgment Work partially supported by EPSRC grants G049165 and J015377.

Hence,

and an automaton recognizing ∈2 L can be built in polynomial time.

(III) For any L ∈ RL fin lag with lag(L) = k, consider the singleton language L = {1 k+1 } ∈ RL fin lag . Note that any nonempty L -controlled relation cannot have a L-resynchronization. Thus, there cannot be a canonical representative of RL fin lag . Note that, however, the class RL fin lag ∪{ [START_REF] Carton | Decision problems among the main subfamilies of rational relations[END_REF](1 * |2 * )} has [START_REF] Carton | Decision problems among the main subfamilies of rational relations[END_REF](1 * |2 * ) as an effective canonical representative by item (I).

(V) This is straightforward since 2 * contains all languages over 2, and therefore all relations are 2 * -controlled.

Proof of Theorem 7

Proof of Theorem 7.

The fact that it is closed under (inverse) alphabetic morphisms is immediate from the definition of Rel(L). ]. We show that there must be some w ∈ S c ∩ (L ⊗ A * ) so that (u, v) = [[w]]. Since L is Parikh-injective, there must be at most one word w ∈ L so that Π(w ) = (|u|, |v|). Since the Parikh image of L is the whole universe N 2 0 , there must be at least one word w ∈ L so that Π(w ) = (|u|, |v|). Hence, there is exactly one word w ∈ L so that Π(w ) = (|u|, |v|). Let w = u ⊗ v ∈ (2 × A) * be the only word so that u = w and [[w]] = (u, v). Note that w ∈ S (otherwise (u, v) would be in [[S]]) and that its projection onto the first component (i.e., w ) is in L. Therefore, w ∈ S c ∩ (L ⊗ A * ).

[⊇] Suppose now that w ∈ S c ∩ (L ⊗ A * ). We show that