Synchronizing Relations on Words

Abstract

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.

1 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 [7, 25]) and data management (standards for describing and querying XML documents, for instance, are rooted in both word and tree automata [27, 31], and emerging graph data models are borrowing many formal language concepts [3]).

Of interest to us in this paper are relations on words. That is, for a given finite alphabet $\mathbb {A}$, we deal with binary relations $R \subseteq \mathbb {A}^{*}\times \mathbb {A}^{*}$. Their study goes back to Elgot, Mezei, Nivat in the 1960s [17, 28] with much subsequent work done later (see, e.g., surveys [9, 15]). 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 [1, 12, 23, 32]. Another comes from graph databases, which are actively studied as a suitable model for RDF data, social networks data, and others [3]. 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 [4, 6, 26]. Yet another example is the study of formal models underlying IBM’s tools for information extraction [18].

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 [5].

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 ₁ = a b a b b and w ₂ = b a a a b a. We can represent this pair as a single word over {a, b}, by shuffling w ₁ and w ₂, i.e., interspersing letters of w ₁ among letters of w ₂. 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 ₁, w ₂) – in our example, 12212112212. We show that the commonly occurring classes of relations over words follow the same principle:

• 1. to decide whether (w ₁, w ₂) is in the relation, one runs an automaton over the shuffle;

• 2. classes of relations are then determined by the classes of allowed synchronizations.

For instance, recognizable relations are given by synchronizations from 1^∗2^∗, length-preserving regular relations by synchronizations from (12)^∗, arbitrary regular relations by synchronizations from (12)^∗(1^∗|2^∗), and rational relations by synchronizations from (1|2)^∗.

For relations, we have proper inclusions recognizable $\subsetneq$ regular $\subsetneq$ rational [9], making them very different from languages. This raises the question: since every recognizable language is regular, and yet 1^∗2^∗ is not contained in (12)^∗(1^∗|2^∗), there must be multiple ways of synchronizing relations to obtain even known classes. What are these ways, and how can they be characterized? And will those characterizations lead to new naturally appearing classes?

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 [9]). 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.

2 Recognizable, Regular, and Rational Relations

We start with some basic notations. Throughout the paper, $\mathbb {A}$ stands for a finite alphabet, $\mathbb {N} = \{1,2,\dotsc \}$ for the set of positive natural numbers, and $\mathbb {N}_{0}$ for $\mathbb {N} \cup \{0\}$. The set of all words over $\mathbb {A}$ is denoted by $\mathbb {A}^{*}$, and the length of w in $\mathbb {A}^{*}$ is denoted by |w|. If w = a ₁…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 $\mathbb {A}^{*}$, equipped with the concatenation operation (denoted by ‘ ⋅’, whose unit is the empty word ‘ ε’) is a monoid. A set $L\subseteq \mathbb {A}^{*}$ is recognizable if there is a finite monoid M and a homomorphism $\langle {\mathbb {A}^{*},\cdot , \boldsymbol {\varepsilon }}\rangle \rightarrow M$ so that L = f ⁻¹(M ₀) for some M ₀ ⊆ 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 $\langle \mathbb {A}^{*},\cdot ,\boldsymbol {\varepsilon }\rangle$ is a monoid, $\mathbb {A}^{*}\times \mathbb {A}^{*}$ has the structure of a monoid too. We can thus define recognizable relations as sets $R\subseteq \mathbb {A}^{*}\times \mathbb {A}^{*}$ for which there is a finite monoid M and a morphism $f: \mathbb {A}^{*}\times \mathbb {A}^{*} \rightarrow M$ such that R = f ⁻¹(M ₀) for some M ₀ ⊆ M. This class will be denoted by REC.

Regular relations

Let $\bot \not \in \mathbb {A}$ be a new alphabet letter. A pair (w ₁, w ₂) of words from $\mathbb {A}^{*}$ can be encoded by a single word of length max(|w ₁|, |w ₂|) over the alphabet $(\mathbb {A} \cup \{\bot \})\times (\mathbb {A}\cup \{\bot \})$: its ith letter is the pair containing the ith letter of w ₁ and the ith letter of w ₂, with ⊥ used when i is greater than the length of w ₁ or w ₂. For example, the encoding for the words of the figure of page 3 is (a, b)(b, a)(a, a)(b, a)(b, b)(⊥, a). A regular relation R is given by an automaton over this alphabet: it contains pairs (w ₁, w ₂) 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 $(\mathbb {A}\cup \{\boldsymbol {\varepsilon }\})\times (\mathbb {A}\cup \{\boldsymbol {\varepsilon }\})$ 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.

Relations in REC are exactly the finite unions of products of regular languages over $\mathbb {A}$ [9, 17]. Examples of relations in REG∖REC are prefix, equality, or equal length. Examples of relations in RAT∖REG are suffix, given by $\big (\bigcup _{a\in \mathbb {A}}(\boldsymbol {\varepsilon },a)\big )^{*}\cdot \big (\bigcup _{a\in \mathbb {A}}(a,a)\big )^{*}$; subword: $\big (\bigcup _{a\in \mathbb {A}}(\boldsymbol {\varepsilon },a)\big )^{*}\cdot \big (\bigcup _{a\in \mathbb {A}}(a,a)\big )^{*} \cdot \big (\bigcup _{a\in \mathbb {A}}(\boldsymbol {\varepsilon },a)\big )^{*}$, and subsequence: $\big (\bigcup _{a\in \mathbb {A}}(\boldsymbol {\varepsilon },a) \cup (a,a)\big )^{*}$.

Note that unlike in the case of languages, where the three notions coincide, we have ${\sf REC} \subsetneq \sf REG \subsetneq \sf 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 [9, 14, 30] 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 ₁, w ₂) of words in $\mathbb {A}^{*}$ is a word over $\mathbf 2 \times \mathbb {A}$ so that the projection on $\mathbb {A}$ of positions labeled i is exactly w _i , for i = 1,2 (see the figure on page 3). Every word w in $(\mathbf 2 \times \mathbb {A})^{*}$ is a synchronization of a uniquely determined pair (w ₁, w ₂), where w _i is the sequence of $\mathbb {A}$-letters corresponding to the symbol i in the first position of $\mathbf 2 \times \mathbb {A}$. We denote such (w ₁, w ₂) by ⟦w⟧ and extend it to languages $S\subseteq (\mathbf 2 \times \mathbb {A})^{*}$ by ⟦S⟧ = {⟦w⟧∣w ∈ S}.

For two words $u=a_{1}\dotsb a_{n} \in \mathbb {A}^{*}$ and $v=b_{1}\dotsb b_{n}\in \mathbb {B}^{*}$, we write u ⊗ v for the word $(a_{1},b_{1})\dotsb (a_{n},b_{n})\in (\mathbb {A}\times \mathbb {B})^{*}$. The main idea of our approach to relations on words comes from two different ways of viewing words in $(\mathbf 2 \times \mathbb {A})^{*}$.

• Every word $w \in (\mathbf 2 \times \mathbb {A})^{*}$ is a synchronization of a pair ⟦w⟧=(w ₁, w ₂).

• Every word $w \in (\mathbf 2 \times \mathbb {A})^{*}$ is of the form u ⊗ v with u ∈ 2 ^∗ and $v \in \mathbb {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

$$ \textsc{Rel}(L) = \{\left[\kern-0.15em\left[ {S} \right]\kern-0.15em\right] ~|~{S}~\text{is~a~regular}~L\text{-controlled~language}\} $$

(1)

If $\mathcal {C}$ is a class of relations over $\mathbb {A}^{*}$, then L ⊆ 2 ^∗ is a synchronization for $\mathcal {C}$ if $\textsc {Rel}(L) \subseteq \mathcal {C}$, that is, all relations given by L-controlled synchronizations belong to $\mathcal {C}$. We remark that a similar approach to defining relations was used in [21], although the questions considered were completely different.

Procedurally, each relation in Rel(L) is obtained as follows:

• 1. Choose an automaton over $\mathbf 2 \times \mathbb {A}$;

• 2. consider words u ⊗ v it accepts so that u ∈ L,

• 3. view v as a synchronization of (w ₁, w ₂) 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.

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 ₁, L ₂ we have that L ₁×L ₂∈Rel(L) because (1 ⊗ L ₁)⋅(2 ⊗ L ₂) 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 ₀ and final states F. Let $L_{i}^{q,q'}$ be the language consisting of all words $v \in \mathbb {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_{i}^{q,q'}$ is regular. Hence, $R = \left[\kern-0.15em\left[ S \right]\kern-0.15em\right] = \bigcup _{q \in Q, q' \in F} L_{1}^{q_{0},q} \times L_{2}^{q,q'}$, and thus any relation in Rel(L) is a finite union of products of languages. Therefore, Rel(L) ⊆ REC.

• (II)- [⊇] Let $R \subseteq \mathbb {A}^{*} \times \mathbb {A}^{*}$ be a regular relation, represented by an NFA A over the alphabet $(\mathbb {A} \cup \{\bot \})^{2}$, where (u ₁, u ₂) is in R if and only if u1′ ⊗ u2′ ∈ L(A), where $u'_{i} \in (\mathbb {A} \cup \{\bot \})^{*}$ is the result of padding u _i with a suffix of max(|u ₁|, |u ₂|)−|u _i | letters ⊥. Let Q be the statespace of A. We produce an NFA A′ over $\mathbf 2 \times \mathbb {A}$ so that ⟦L(A′)⟧ = R and L(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 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 \in \mathbb {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 $\mathbf 2 \times \mathbb {A}$ so that L(A) is L-controlled, with statespace Q. Note that Q can be partitioned into four sets Q ₁, Q ₂, Q1′, Q2′, so that the transition relation δ of A is such that

  $$ \boldsymbol{\delta} ~~\subseteq~~ \bigcup_{i \in \mathbf 2} Q_{i} \times \{ i\} \times \mathbb{A} \times (Q \setminus Q_{i}) ~~\cup~~ \bigcup_{i \in \mathbf 2}Q'_{i} \times \{ i\} \times \mathbb{A} \times Q'_{i}\qquad\qquad\qquad{(\dag)} $$

  that is, all outgoing transitions from Q _i , Q i′ read letters from $\{ i\} \times \mathbb {A}$, and there is an alternation between Q ₁ and Q ₂ until a state from Q i′ is reached, and after that it stays only in Q i′. We can build an automaton A′ over $(\mathbb {A} \cup \{\bot \})^{2}$ representing the same relation as follows. For every two transitions (q ₁, (1, a), q ₂) and (q ₂,(2, b), q′) of A where q _i ∈ Q _i , we have a transition (q ₁,(a, b), q′) in A′; for every transition (q ₁,(1, a), q1′) where q ₁, q1′ ∈ Q ₁∪Q1′, we have a transition (q ₁,(a,⊥), q1′) in A′; and for every transition (q ₂,(2, b), q2′) where q ₂, q2′ ∈ Q ₂∪Q2′, we have a transition (q ₂,(⊥, b), q2′) in A′. By (1), 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\subseteq \mathbf 2 \times \mathbb {A}$ is regular. Any automaton A over $\mathbf 2 \times \mathbb {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 $\mathbf 2 \times \mathbb {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.

□

It is easy to see that Rel(L) is closed under union, alphabetic morphisms, and inverse alphabetic morphisms, and that L ₁ ⊆ L ₂ implies Rel(L ₁) ⊆ Rel(L ₂).

Remark 1

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}, \boldsymbol {\varepsilon }) \mid n\in \mathbb {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 $\mathbb {A}^{*} \times \{\boldsymbol {\varepsilon }\}$ so that the first component is of prime length.

4 Synchronizations for Recognizable, Regular, and Rational Relations

We have seen examples of languages characterizing the classes of recognizable, regular, and rational relations, but those are not unique. There are trivial examples such as Rel(1^∗2^∗)=Rel(2^∗1^∗) = REC, and Rel((12)^∗(1^∗|2^∗))=Rel((21)^∗(1^∗|2^∗)) = REG, but others as well, e.g., the fact that Rel(1^∗2^∗1^∗2^∗) is the same class as REC, or Rel(((12)^∗1(12)^∗2)^∗(1^∗|2^∗)) = REG.

What kind of parameters guarantee that L ⊆ 2 ^∗ synchronizes relations in a class $\mathcal {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 $\mathcal {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 $\boldsymbol {\delta } \in \mathbb {N}$, we say i is

• δ-lagged if |# ₁(w[1, i]) − # ₂(w[1, i])| = δ;

• ≥ δ-lagged if |# ₁(w[1, i]) − # ₂(w[1, i])| ≥ δ;

• ≤ δ-lagged if |# ₁(w[1, i]) − # ₂(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 s h i f t l a g(w) be the maximum $n \in \mathbb {N}$ so that w contains n consecutive shifts which are > n-lagged. We lift these notions to languages by taking maxima, e.g., s h i f t(L) = maxw ∈ L s h i f t(w), and likewise for l a g(L) and s h i f t l a g(L). If words of arbitrarily large lag (shift, or shiftlag) occur in L, we write s h i f t(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 s h i f t l a g(L) < ∞ and yet lag(L) = s h i f t(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 [20, 30] 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 [20, 30] that REG ^bld is the class $\bigcup _{k \in \mathbb {N}_{0}} \textsc {Rel}({L_{k}})$, for L _k = (12)^∗(1^k|2^k). Note that Rel(L ₀) is the class of length preserving relations. A closely related class $R_{\leq } = \{ (w_{1},w_{2}) \in \mathbb {A}^{*} \times \mathbb {A}^{*} \mid |w_{1}| \leq |w_{2}| \}$ [24] 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 recognizable relations iff shift(L) < ∞,

• (II) L synchronizes regular relations iff shiftlag(L) < ∞,

• (III) L synchronizes relations in REG ^bld iff lag(L) < ∞,

• (IV) L synchronizes rational relations.

In order to prove Theorem I, we first need two lemmas.

Lemma 1

For every s ≥ 1, we have Rel((1^∗2^∗ ) ^s ) = REC.

Proof

This is a consequence of a synchronization theorem, Theorem 3-(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 2

For every $\boldsymbol {\delta } \in \mathbb {N}$ , we have $\textsc {Rel} ({L_{{{\leq }\boldsymbol {\delta }-\text {lag}}}}) \subsetneq \sf 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, \boldsymbol {\varepsilon }) \mid u \in \mathbb {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, $\textsc {Rel}({L_{{{\leq }\boldsymbol {\delta }-\text {lag}}}})\subsetneq \sf REG$.

Since the concatenation of a regular relation and a recognizable relation is regular [9], 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 ₁ ⋅ R ₂ so that R ₁ is (12)^∗-controlled and R ₂ 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_{{\leq }\boldsymbol {\delta }-\text {lag}} \subseteq L_{{\leq }\boldsymbol {\delta }^{\prime }-\text {lag}}$. Then, by the above and monotonicity, REG ⊆ Rel(L _{≤ δ − lag})⋅REC for every δ ≥ 1. □

We can now prove the theorem.

Proof (of Theorem 1) (II)-(if)

Let $n \in \mathbb {N}$ so that s h i f t l a g(L) < n. Since L is regular, this implies that there is some δ′ where all shifts of every w ∈ L 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 # ₁(w[1, i]) − # ₂(w[1, i]) > δ′. Figure 1 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.

Note that in [i′, i] there cannot be more than n shifts, since otherwise w would have n consecutive > n-lagged shifts contradicting shift l a g(w) < n. Also, in [i′, i] there must be k = δ′−n positions i′≤ i ₁ < ⋯ < 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, $$

(2)

where, by definition of δ′, k = n|Q|+1 (cf. Figure 1). 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_{j_{1}} < \dotsb < i_{j_{|Q|+1}}$ so that there is no shift in $[i_{j_{1}},i_{j_{|Q|+1}}-1]$. Then, there must be two distinct positions $i_{j}, i_{j'} \in \{i_{j_{1}}, \dotsc , 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. Fig. 1). 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 shift l a g(w′) ≥ n. Indeed, for any $l \in \mathbb {N}$, we have that

$$w' = w[1,i_{j}] \cdot (w[i_{j}+1,i_{j'}])^{l} \cdot w[i_{j'}+1,|w|] ~\in~ L. $$

Note that w′ has as many shifts as w. Moreover, shift i in w corresponds now to shift $\hat i = i + (l-1) \cdot |[i_{j}+1,i_{j'}]|$ in w′, and we have

$$\#_{1}(w'[1,\hat i]) - \#_{2}(w'[1,\hat i]) > (l-1) + \boldsymbol{\delta}^{\prime} $$

since for every iteration of w[i _j +1, i _j′] we add more letters 1 than letters 2, as a consequence of (2).

Fig. 1

Example, where w has a prefix 1111121111112 after which it has n − 1 shifts, n=4, $\boldsymbol {\delta }^{\prime }=9$, and |Q|=1. Shift positions are circled

If we take l = |w|+1, we then have that

• w′ has at least n shifts in $[\hat i, |w'|]$, because w has at least n shifts in [i,|w|] and $w'[\hat i, |w'|]=w[i, |w|]$, and

• $\#_{1}(w'[1,\hat i]) - \#_{2}(w'[1,\hat i]) > |w| + \boldsymbol {\delta }^{\prime }$.

Therefore, the last n shifts of w′ are all > n-lagged, contradicting shift l a g(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 the above Claim 1, there must be some δ″ where all the positions occurring before the last n 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 ₁ ≤ i ≤ i ₂ so that

• i ₂ is a shift,

• i ₁ is a shift or i ₁ = 1, and

• there are no shifts in [i ₁+1, i ₂−1].

By Claim 1, it follows that both i ₁ and i ₂ are ≤ δ′-lagged. Since w[i ₁+1, i ₂] is a string of only 1’s or only 2’s, it cannot be that |w[i ₁+1, i ₂]| > 2δ′, as otherwise either i ₁ or i ₂ 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

$$ L ~\subseteq~ L_{{{\leq}\boldsymbol{\delta}^{\prime\prime}-\text{lag}}} \cdot (1^{*}|2^{*})^{n} $$

(3)

because (1^∗|2^∗)ⁿ 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^∗)ⁿ by Lemma 1, we obtain that Rel(L″) = R E G for L″=L _{≤ δ″−lag}⋅(1^∗|2^∗)ⁿ by Lemma 2. Finally, as stated in (3), we have that L ⊆ L″ where Rel(L″) = REG. Applying monotonicity, we then have Rel(L) ⊆ REG.

(II)-(only if) :

Suppose that s h i f t l a g(L) = ∞. Note that this means that for every $s, \boldsymbol {\delta } \in \mathbb {N}$ there is some w ∈ L that has s consecutive shifts > δ-lagged (because in particular there is some w ∈ L so that s h i f t l a g(w) > max(s, δ)). We build an L-controlled relation $S \subseteq (\mathbf 2 \times \mathbb {A})^{*}$ so that ⟦S⟧ ∈ RAT∖REG.

Let $\mathbb {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|},

• 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⟧ ∉ REG.

Note that every pair in the relation has almost the same number of a’s:

$$ \text{For every \((u',v') \in \left[\kern-0.15em\left[ S\right]\kern-0.15em\right]\),~~ \(-1 \leq \#_{a}(u') - \#_{a}(v') \leq 1\).}\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad{(\dag)} $$

Suppose, 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′.

Let s = 2|Q′|+2, and let us define the constant K = s ²|Q|. We hence define δ = 2K. There must then be some w = u ⊗ v ∈ S with s consecutive shifts that are > δ-lagged. Let 1 ≤ i ₁ < ⋯ < i _s ≤ |u| be the shifts in question. Let us assume, without any loss of generality, that w is minimal in length and that # ₁(u[1, i ₁])−# ₂(u[1, i ₁]) > δ.

Due to minimality of w, it can be shown through a pumping argument, that the lengths of w[i ₁, i _s ] and of w[i _s +1,|w|] are bounded by a function on s and |Q|.

Claim 3

|w|−i ₁ ≤s ² |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}]) \leq (s-1)|Q|. $$

(4)

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]=1, ρ(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 (4),

$$\#_{1}(u[i_{1}+1,i] \cdot u[j+1,i_{l+1}]) - \#_{2}(u[i_{1}+1,i] \cdot u[j+1,i_{l+1}]) \geq 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}]) \leq (s-1)s|Q|. $$

(5)

Then, by (4) and (5), the length of u[i ₁, 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|]| \leq |Q|. $$

(6)

Then, summing up, [i ₁,|w|] is bounded by

$$\underbrace{|Q|}_{\text{by (6)}} + \underbrace{(s-1)|Q|}_{\text{by (4)}} + \underbrace{(s-1)s|Q|}_{\text{by (5)}} + 1 = s^{2}|Q| +1. $$

Thus, |w| − i ₁ ≤ s ²|Q|=K. □

Since δ = 2K < # ₁(u[1, i ₁])−# ₂(u[1, i ₁]) and # ₂(u[i ₁+1,|w|])≤ K by Claim 3, we have that

$$ \#_{1}(u) - \#_{2} (u) > K. $$

(7)

Let w′ = u′ ⊗ v′ ∈ S′ 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′ = u1′⋅u2′ with u1′∈(12)^∗ and u2′∈1^∗. (The other possibility, u2′ ∈ 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 (7), we have that |u2′| ≥ K. Thus, u2′ must contain at least s/2 positions labeled with a. Since s/2=|Q′|+1, there must be two distinct positions |u1′| < i < j ≤ |w′| labeled with a so that ρ′(i) = ρ′(j). Consider then w″=w′[1, i]⋅(w′[i+1, j])⁴⋅w′[j+1,|w′|]. Note that w″∈S′. By property (4), 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 (4), 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.

(I)-(if) :

Let shift(L) < n. Note that L′ = (1^∗2^∗)ⁿ contains all words with less than n shifts. Hence, L ⊆ L′. By Lemma 1, Rel(L′) = REC, and since L ⊆ L′, it follows that Rel(L) ⊆ REC by monotonicity.

(I)-(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 $\mathbb {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|},

• 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:

$$ \text{For every \((u,v) \in \left[\kern-0.15em\left[ S\right]\kern-0.15em\right]\),~~ \(-1 \leq \#_{a}(u) - \#_{a}(v) \leq 1\).}\qquad\qquad\qquad\qquad\qquad\qquad{(\ddag)} $$

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 (that is, the the sum of occurrences of a’s in both components is greater than |Q′|). 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 ₁, j ₂ of w′ so that ρ′(j ₁) = ρ′(j ₂), v′[j ₁] = v′[j ₂] = a and either 1 ≤ j ₁ < j ₂ ≤ i or i < j ₁ < j ₂ ≤ |w′| (as a consequence of S′ being 1^∗2^∗-controlled). Note then that w′[1, j ₁]⋅(w′[j ₁+1, j ₂])ⁿ⋅w′[j ₂+1,|w′|]∈S′ for every $n \in \mathbb {N}$. Take n = 4, and let w″=w′[1, j ₁]⋅(w′[j ₁+1, j ₂])⁴⋅w′[j ₂+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 ⟦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). □

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 \subseteq (\mathbf 2 \times \mathbb {A})^{*}$ so that ⟦S⟧ is not a regular relation.

As another example, we get more ways of synchronizing regular relations: given L ₁ = (1^k⋅2^k)^∗, L ₂ = (1^∗⋅2^∗)^k for some fixed k, we have Rel(L _i ) ⊆ REG (in fact, Rel(L ₂) ⊆ REC).

Finally, we consider the (r/s)-synchronized relations [30, p.660] studied in [13]. This class can be defined as Rel(L _r/s ), where

$$ L_{r/s} = (1^{r}2^{s})^{*} \big( \bigcup_{r' < r} (1^{r'} 2^{*}) ~|~ \bigcup_{s' < s} (1^{*} 2^{s'}) \big) . $$

(8)

It is easy to see that s h i f t l a g(L _r/s ) = ∞ whenever r ≠ s, and hence that (r/s)-synchronized relations (with r ≠ s) are not in REG.

4.1 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. A path is a finite sequence of edges of G _A so that the arriving vertex of each edge is equal to the departing vertex of the next one. A cycle is a path whose first and last vertices are equal. A simple cycle is a cycle whose only repetition of vertex is the first and last ones. 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 # ₁(C) > 0 and # ₂(C) > 0; otherwise a cycle is homogeneous. A cycle C is balanced if # ₁(C) = # ₂(C), otherwise it is unbalanced (these definitions are closely related to the notions of balanced/unbalanced oriented cycles in digraphs, cf. [22]). 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

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 ₁⋯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 \in \mathbb {N}$. We show that assuming one of the two properties is met, there is some w ∈ L(A) with s h i f t l a g(w) ≥ n.

If G _A has a heterogeneous cycle C _{h e t} with # ₁(C _{h e t} )≠# ₂(C _{h e t} ), one can iterate this cycle to obtain a word w with shift l a g(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 _{h e t} between the positions i ≤ j where we assume, without any loss of generality, # ₁(C _{h e t} ) > # ₂(C _{h e t} ) > 0. Since this means that ρ(i − 1) = ρ(j), we have that

$$w_{m} = w[1,i-1] \cdot (w[i,j])^{m} \cdot w[j+1,|w|] \in L(A) $$

for every $m \in \mathbb {N}$, and # ₁(w[i, j]) > # ₂(w[i, j]) > 0 because # ₁(C _{h e t} ) > # ₂(C _{h e t} ) > 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, s h i f t l a g(w _m ) ≥ n.

If, on the other hand, there is a path from a homogeneous cycle C _{h o m} to a heterogeneous cycle C _{h e t} in G _A , then we show that we can iterate both cycles enough times to obtain a word w ∈ L(A) so that s h i f t l a g(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 _{h o m} occurs before C _{h e t} . That is, there are 0 < i < j ≤ i′ < j′ ≤ |w| so that

• ρ(i) = ρ(j) and C _{h o m} is the cycle induced by w[i, j], ρ|_{[i − 1, j]}, and

• ρ(i′) = ρ(j′) and C _{h e t} is the cycle induced by w[i′, j′], ρ|_{[i′−1, j′]}.

Note that for any $m,l \in \mathbb {N}$ we have

$$w_{m,l} = \underbrace{w[1,i] \cdot (w[i+1,j])^{m} \cdot w[j+1,i']}_{u_{m}} \cdot \underbrace{(w[i'+1,j])^{l} \cdot w[j',|w|]}_{v_{l}} ~\in~ L(A). $$

If we take m = (n+2)|w| and l = n, we obtain that

• |# ₁(u _m )−# ₂(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 shift l a g(w _{m, l} ) ≥ n.

Thus, if any of the conditions in (I) is met, we must have that shift l a g(L(A)) = ∞.

(I)-(only if) :

Suppose now that shift l a g(L(A)) = ∞. We choose n = 2|Q|+1, and show that any accepting run of A on w ∈ L(A) so that shift l a g(w) ≥ n must induce a path P containing either

• (i) a heterogeneous cycle C _{h e t} with # ₁(C _{h e t} )≠# ₂(C _{h e t} ), or

• (ii) a homogeneous cycle C _{h o m} and a heterogeneous cycle C _{h e t} , so that C _{h o m} occurs before C _{h e t} 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 shift l a g(w) > n. Consider the path P on G _A induced by ρ, w. By definition of shift l a g(w) > n, there must be n consecutive > n-lagged shifts 1 ≤ a ₁ < a ₂ < ⋯ < a _n ≤ |w| in w. Without any loss of generality, assume that

$$ \#_{1} (w[1,a_{1}]) - \#_{2} (w[1,a_{1}]) > n,\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad{(\dag)} $$

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 ₁ < ⋯ < b _n ≤ a ₁ so that # ₁(w[b _i +1, b _i+1])−# ₂(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}], \rho|_{[b_{i},b_{j}]}$ necessarily verifies

$${\kern6pc} \#_{1} (C) > \#_{2} (C).{\kern15pc} {(\ddag)} $$

Now there are two possibilities.

• If # ₂(C) > 0 then C is heterogeneous and with # ₁(C)≠# ₂(C) by ( †), verifying condition (i).

• The other possibility is that C is homogeneous. Since there is a path from C to a heterogeneous cycle C _{h e t} , the condition (ii) is met.

(II)-(if) :

Suppose that G _A contains a heterogeneous cycle C _{h e t} . 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 _{h e t} between positions i ≤ j of P. Therefore ρ(i − 1) = ρ(j), and w _n = w[1, i − 1]⋅(w[i, j])ⁿ⋅w[j+1,|w|]∈L(A) for any $n \in \mathbb {N}$. Note that as a consequence of C _{h e t} 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 \in \mathbb {N}$ there is a word w ∈ L(A) so that shift(w) > n. Take n = 2|Q|, and let w ∈ L(A) so that s h i f t(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 ₁ < ⋯ < i _|Q|+1 ≤ |w| so that w[i _j ] = 1 for all j ∈ {1,…,|Q|+1}. Then there must be two $i_{j_{1}} < i_{j_{2}}$ so that $\rho (i_{j_{1}}) = \rho (i_{j_{2}})$. Hence, the word $w[i_{j_{1}}+1,i_{j_{2}}]$ 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_{j_{1}}$ would not be a shift with letter 1). It then follows that the path on G _A induced by $w[i_{j_{1}}+1,i_{j_{2}}], \rho |_{[i_{j_{1}},i_{j_{2}}]}$ is indeed a heterogeneous cycle.

(III) This is shown in [30, Lemma 6.7, p. 603]. □

Corollary 1

Checking whether Rel(L(A)) ⊆ REG, Rel (L(A)) ⊆ REC (L(A)) ⊆ REC or whether $\textsc {Rel}({L(A)}) \subseteq {\sf REG}^{\textit {bld}}_{2}$ can be done in polynomial time in the size of A.

Note that Corollary 1 does not mean that it is decidable whether a relation R ∈ RAT is in REG (in fact, this problem is undecidable [9, Theorem 8.4-(vi)]). What one can check is whether a synchronized relation 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 $\mathbb {A}^{*} \times \mathbb {A}^{*}$ is obviously in REG.

5 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'\subseteq (\mathbf 2 \times \mathbb {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 $\mathcal {C}$ of regular languages over 2, we say that $L_{0} \in \mathcal {C}$ is a canonical representative of $\mathcal {C}$ if for every $L \in \mathcal {C}$ and every L-controlled language S there exists an L ₀-resynchronization of S. In other words, for every $L\in \mathcal {C}$ and R ∈ Rel(L), there is an L ₀-controlled $S'\in (\mathbf 2 \times \mathbb {A})^{*}$ so that ⟦S′⟧ = R. If, in addition, there is a recursive procedure that constructs such an L ₀-resynchronization of S, then we say that L ₀ is an effective canonical representative of $\mathcal {C}$.

Let RL _all be the class of all regular languages over 2, and let $\sf RL_{\textit {param}}^{\textit {fin}}$ stand for the 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 1

Take, for example, L ₁ = (1122)^∗1^∗2^∗ and L ₂ = (12)^∗(1^∗|2^∗), and a L ₁-controlled relation S ₁. Since shift l a g(L ₁) < ∞, ⟦S ₁⟧ ∈ REG by Theorem 1. Further, since by Proposition 1-(II) Rel(L ₂) = REG, there must be some L ₂-controlled relation S ₂ so that ⟦S ₂⟧=⟦S ₁⟧. In other words S ₂ is the L ₂-resynchronization of S ₁. Since Rel(L ₂) = REG in fact L ₂ is a canonical representative of $\sf RL_{\textit {shift}lag}^{\textit {fin}}$.

Theorem 3 (Resynchronization theorem)

• (I) (12)^∗ (1 ^∗ |2 ^∗ ) is an effective canonical representative of $\sf RL_{\textit {shift}lag}^{\textit {fin}}$;

• (II) 1^∗2^∗ is an effective canonical representative of $\sf RL_{\textit {shift}}^{\textit {fin}}$;

• (III) there is no canonical representative of $\sf RL_{\textit {lag}}^{\textit {fin}}$;

• (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.

For the proof of the Theorem above wee need to introduce some standard notions. The shuffle s h(U, V) of two languages $U, V \subseteq \mathbb {A}^{*}$ is the set of all words u ₁ ⋅ v ₁⋯u _k ⋅ v _k so that u ₁⋯u _k ∈ U, v ₁⋯v _k ∈ V. 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 c o n(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).

For the proof of Theorem 3 we use the following lemma.

Lemma 3 (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 # ₁(C) = # ₂(C).

  Let us analyze each case separately. Let S ₁,…, S _n be the set of SCC’s reachable from S (excluding S).

  • (a)  Then, $\textit {shift}lag(L(A|_{S})) \leq 1 + \textit {shift}lag(L(A|_{S_{1} \cup \dotsb \cup S_{n}}))$.

  • (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 shift l a g(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 \in \bigcup _{i \leq |S|} (sh(1^{i},2^{i}))^{*}$ and $v \in L(A|_{S_{1} \cup \dotsb \cup S_{n}})$. Recall that s h(1ⁱ,2ⁱ) represents the set of shuffles of 1ⁱ and 2ⁱ (i.e., all the words over 2 having exactly i 1’s and i 2’s). Note that

    • there are no positions > |S|-lagged in u, and

    • position |u| is 0-lagged in w.

    Thus, $\textit {shift}lag(L(A|_{S})) \leq \max ( |S|, \textit {shift}lag(L(A|_{S_{1} \cup \dotsb \cup S_{n}})))$.

  Combining (a), (b) and (c), and by the fact that c o n(G _A ) is a DAG, we obtain that shift l a g(L(A)) ≤ |Q|.

• (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 |Q| 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 ≤ |Q|, the statement follows.

• (III) By Theorem 2-III all cycles C in G _A are so that # ₁(C) = # ₂(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 # ₁(C) = # ₂(C). Therefore, # ₁(w[i, j − 1]) = # ₂(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, it cannot be that lag(L(A)) > |Q| and the statement follows.

□

We are now in conditions to prove Theorem 3.

Proof of Theorem 3

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

• (II) Let $S\subseteq (\mathbf 2 \times \mathbb {A})^{*}$ be an L-controlled regular language 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 ₀ 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 3-(II), shift(L) ≤ |Q|.

Let us call 1-edge (resp. 2-edge) 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 c o n(G _A ) (cf. Fig. 2). By acyclicity there are at most exponentially many paths in c o n(G _A ).

Fig. 2

Example of path in G _A and corresponding path in c o n(G _A ). For simplicity, we assume that the alphabet is singleton $\mathbb {A} = \{a\}$, and we therefore omit ‘a’ in the transitions

For any (possibly empty) path P in c o n(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 c o n(G _A ). Hence,

$$S = \bigcup \{S_{P,q} \mid \text{\textit{P} is a path of \(con(G_{A})\) and \(q\in Q_{F}\)}\}. $$

We conclude the proof by showing that for every path P in c o n(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|.

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 c o n(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 Fig. 3 (the path in this Figure is unrelated to the path of the previous Figures). Let $states_{q_{0},q}(P)$ be the sequence of states appearing in P, prefixed with q ₀ and suffixed with q; that is, if

$$P = (v_{1},(q_{1},(i_{1},a_{1}),q'_{1}),v_{2}), \dotsc, (v_{n},(q_{n},(i_{n},a_{n}),q'_{n}),v_{n+1}),$$

then $states_{q_{0},q}(P) = q_{0}, q_{1}, q'_{1}, \dotsc , q_{n}, q'_{n}, q$. The idea is that $states_{q_{0},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 Fig. 2, we have $states_{q_{0},q_{6}} = q_{0},q_{1},q_{5},q_{5},q_{6},q_{6}$, note that it includes, for every SCC, the incoming and outgoing states ( q ₀, q ₁ for the first, q ₅, q ₅ for the second, and q ₆, q ₆ for the third SCC). In the top picture of Fig. 3, the vertices in $states_{q_{0},q}(P)$ are depicted as bullets.

Fig. 3

Example of construction of G P, q′ from G _{P, q} . The SCC are abstracted as grey 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

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 Fig. 3. Let v ₁, v′ ₁ be the first and last vertices in the construction of G _{P, q} (cf. Fig. 3). That is, v ₁ corresponds to the first vertex in $states_{q_{0},q}(P)$ that has an outgoing 1-edge in G _{P, q} , and v′ ₁ corresponds to the last vertex in $states_{q_{0},q}(P)$ that has an incoming 1-edge in G _{P, q} .

We define G _{P, q,2} and v ₂, v′ ₂ analogously to G _{P, q,2} and v ₁, v′ ₁, but removing 1-edges instead (cf. Fig. 3). Now, let G P, q′ be the transition graph resulting from composing G _{P, q,1} with G _{P, q,2} by associating v′ ₁ with v ₂ (cf. Fig. 3). Let us define the automaton A _{P, q} as having the transition relation defined by G P, q′, where the initial state is v ₁ and the set of final states is $\{v_{2}^{\prime }\}$. 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^{\prime} = \bigcup_{P,q} L(A_{P,q}) $$

for every path P of c o n(G _A ) and q ∈ Q _F , and defining $A_{S^{\prime }}$ as the union of all automata A _{P, q} ’s. Then, S′ is a (1^∗2^∗)-resynchronization of S, and $A_{S^{\prime }}$ 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).

Claim 5

For any (1 ^∗2^∗ )-controlled automaton A one can build, in polynomial time, (12) ^∗ -controlled automata $A^{head}_{1}, \dotsc , A^{head}_{t}$ as well as (1 ^∗ |2 ^∗ )-controlled automata $A^{tail}_{1}, \dotsc , A^{tail}_{t}$ so that

$$\left[\kern-0.15em\left[{L(A)}\right]\kern-0.15em\right] = \bigcup_{i \in \mathbf t} \left[\kern-0.15em\left[{ L(A^{\textit{head}}_{i}) \cdot L(A^{\textit{tail}}_{i}) }\right]\kern-0.15em\right]. $$

Proof

In the scope of this proof, let Q be the statespace of A, with initial state q _{i n i t} 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 ₁, q ₂, 1), (1, a), (q1′, q ₂,2)) if (q ₁,(1, a), q1′) is a transition of A and q ₂ ∈ Q, and

• ((q ₁, q ₂,2),(2, a), (q ₁, q2′,1)) if (q ₂,(2, a), q2′) is a transition of A and q ₁ ∈ Q.

Note that for every q ₁, q ₁, q1′, q2′ ∈ Q, A′[(q ₁, q ₂,1),(q1′, q2′,1)] is (12)^∗-controlled. Also, note that for every q1′, q ₂, q2′ ∈ Q and q _f ∈ Q _F ,

$$\underbrace{L(A^{\prime}[(q_{init},q_{2},1)(q_{2},q^{\prime}_{2},1)])}_{L^{head}_{1}} \cdot \underbrace{(L(A[q^{\prime}_{2},q_{f}]) \cap (\{2\} \times\mathbb{A})^{*})}_{L^{tail}_{1}} $$

and

$$\underbrace{L(A^{\prime}[(q_{init},q_{2},1)(q^{\prime}_{1},q_{f},1)])}_{L^{head}_{2}} \cdot \underbrace{(L(A[q^{\prime}_{1},q_{2}]) \cap (\{1\} \times \mathbb{A})^{*})}_{L^{tail}_{2}} $$

are (12)^∗(1^∗|2^∗)-controlled, and that automata recognizing $L^{head}_{i}, L^{tail}_{i}$ can be obtained in polynomial time.

From the definition of $L^{head}_{i}$ and $L^{tail}_{i}$ and the previous observation, we show that for any word $w \in L^{head}_{i} \cdot L^{tail}_{i}$ there is some w′ ∈ L so that ⟦w⟧ = ⟦w′⟧, and vice versa.

Observe that for any q ₁, q1′, q ₂, q2′ ∈ Q, w ∈ L(A′[(q ₁, q ₂,1)(q1′, q2′,1)]) if, and only if, $w_{\textit {odd}} \in L(A[q_{1},q^{\prime }_{1}])\cap (\{1\} \times \mathbb {A})^{*}$ and $w_{\textit {even}} \in A[q_{2},q^{\prime }_{2}]\cap (\{ 2\} \times \mathbb {A})^{*}$, where w _odd (resp. w _even ) is the subword of w of odd (resp. even) positions.

From any accepting run of A′[(q _{i n i t} , q ₂,1),(q ₂, q2′,1)] on w ₁ and an accepting run of A[q2′, q _f ] on $w_{2} \in (\{ 2\} \times \mathbb {A})^{*}$ one can build an accepting run of A on (w ₁) _odd ⋅(w ₁) _even ⋅ w ₂, where ⟦(w ₁) _odd ⋅(w ₁) _even ⋅ w ₂⟧=⟦w ₁ ⋅ w ₂⟧. Similarly, from an accepting run of

$$A^{\prime}[(q_{init},q_{2},1),(q^{\prime}_{1},q_{f},1)] $$

on w ₁ and an accepting run of $w_{2} \in (\{ 1\} \times \mathbb {A})^{*}$ on A[q1′, q ₂] one can build an accepting run of A on (w ₁) _odd ⋅ w ₂⋅(w ₁) _even , where ⟦(w ₁) _odd ⋅ w ₂⋅(w ₁) _even ⟧=⟦w ₁ ⋅ w ₂⟧. Indeed, note that in both cases, $(w_{1})_{\textit {odd}} = (w_{1})_{\{1\} \times \mathbb {A}}$ and $(w_{1})_{\textit {even}} = (w_{1})_{\{2\} \times \mathbb {A}}$.

Conversely, for every accepting run of A on w, let w′ be the interleaving of $w_{\{1\} \times \mathbb {A}}[1,m]$ and $w_{\{2\} \times \mathbb {A}}[1,m]$, where $m = \min (|w_{\{1\} \times \mathbb {A}}|, |w_{\{2\} \times \mathbb {A}}|)$ (more formally, it is the word $w^{\prime } \in sh(w_{\{1\} \times \mathbb {A}}[1,m],w_{\{2\} \times \mathbb {A}}[1,m])$ so that $w^{\prime } \in ((\{1\}\times \mathbb {A}) \cdot (\{2\}\times \mathbb {A}))^{*}$). If $|w_{\{1\} \times \mathbb {A}}| \leq |w_{\{2\} \times \mathbb {A}}|$ then for some q ₂, q2′ ∈ Q and q _f ∈ Q _F there is an accepting run of A′[(q _{i n i t} , q ₂,1),(q ₂, q2′,1)] on w′, and accepting run of A[q2′, q _f ] on $w[2m+1, |w|] \in (\{2\} \times \mathbb {A})^{*}$. Similarly, if $|w_{\{1\} \times \mathbb {A}}| > |w_{\{2\} \times \mathbb {A}}|$ then for some q ₂, q1′ ∈ Q and q _f ∈ Q _F there is an accepting run of A′[(q _{i n i t} , q ₂,1)(q1′, q _f ,1)] on w′, and accepting run of A[q1′, q ₂] on $w[2m+1, |w|] \in (\{ 1\} \times \mathbb {A})^{*}$. In both cases, observe that ⟦w′⋅w[2m+1,|w|]⟧=⟦w⟧.

Summing up, for every pair $(u,v) \in \mathbb {A}^{*} \times \mathbb {A}^{*}$, there is a word $w \in L^{head}_{i} \cdot 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}_{1} \cdot L^{tail}_{1}$ and $L^{head}_{2} \cdot L^{tail}_{2}$ languages for all possible q ₂, q2′, q1′ ∈ 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 [30, 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\subseteq (\mathbf 2 \times \mathbb {A})^{*}$ with shift l a g(L) < ∞. Let A be an NFA recognizing S with statespace Q, initial state q ₀ 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 # ₁(C)≠# ₂(C)). Let Q _{h o m} be the set of all vertices of G _A that are reachable from a vertex of a homogeneous SCC. Note that Q _{h o m} 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 _{h o m} has no heterogeneous cycles. Let Q _{h e t} = Q∖Q _{h o m} . Hence, Q _{h e t} 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 _{h e t} is connected. Figure 4 contains an example. Further, any path $\hat P$ in G _A is of the form (1) $\hat P \cdot (q,\tau ,q^{\prime }) \cdot \hat P^{\prime }$, (2) $\hat P$, or (3) $\hat P^{\prime }$, where

• $\hat P$ is a (possibly empty) path of the subgraph of G _A induced by Q _{h e t} ,

• $\hat P^{\prime }$ is a (possibly empty) path of the subgraph of G _A induced by Q _{h o m} ,

• q ∈ Q _{h e t} , q′ ∈ Q _{h o m} , and τ is a transition of A.

Fig. 4

Example of G _A with the subgraphs induced by Q _{h o m} and Q _{h e t} . For simplicity we assume that $\mathbb {A} = \{ a\}$ and we hence omit the letter a when depicting edges labeled by (i, a)

Let A ^het be A restricted to Q _{h e t} , and let A ^hom be A restricted to Q _{h o m} . For every pair of states q _{h e t} ∈ Q _{h e t} and q _{h o m} ∈ Q _{h o m} , let $L_{q_{het},q_{hom}}$ be the union of all

$$L(A^{het}[q_{0},q_{het}]) \cdot \{(i,a)\} \cdot L(A^{hom}[q_{hom},q_{f}]) $$

for every q _f ∈ Q _F and $(i,a) \in \mathbf 2 \times \mathbb {A}$ so that (q _{h e t} ,(i, a), q _{h o m} ) is a transition of A (if there is no such (i, a), let $L_{q_{het},q_{hom}} = \emptyset$). We remind the reader that A ^het[q, q′] (resp. A ^hom[q, q′]) where q or q′ are not in Q _{h e t} (resp. Q _{h o m} ) denotes the automaton accepting the empty language. Let $L_{\textit {hom}} = \bigcup _{q_{f} \in Q_{F}}L(A^{hom}[q_{0},q_{f}])$ and $L_{\textit {het}} = \bigcup _{q_{f} \in Q_{F}}L(A^{het}[q_{0},q_{f}])$. It follows that

$$S = L_{\textit{hom}} \cup L_{\textit{het}} \cup \bigcup_{q_{het} \in Q_{het}, q_{hom} \in 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 _{h e t} ∈ Q _{h e t} , q _{h o m} ∈ Q _{h o m} , q _f ∈ Q _F we have that both lag(L(A ^het[q ₀, q _{h e t} ])) < ∞ and shift(L(A ^hom[q _{h o m} , q _f ])) < ∞. Hence, by Lemma 3,

• lag(L(A ^het[q ₀, q _{h e t} ])) ≤ n,

• shift(L(A ^hom[q _{h o m} , 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 $\left[\kern-0.15em\left[ {L(A^{hom}[q_{0},q_{hom}])}\right]\kern-0.15em\right] = \left[\kern-0.15em\left[ {L(A^{hom}_{q_{0},q_{hom}})}\right]\kern-0.15em\right]$. By item (IV), let $A^{het}_{q_{0},q_{het}}$ be a (12)^∗(1^{≤ n}|2^{≤ n})-controlled automaton so that $\left[\kern-0.15em\left[ {L(A^{het}[q_{0},q_{het}])}\right]\kern-0.15em\right] = \left[\kern-0.15em\left[ {L(A^{het}_{q_{0},q_{het}})}\right]\kern-0.15em\right]$. 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}_{q_{0},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}_{q_{0},q_{het}}$ and all the $A^{hom}_{q_{hom}, q_{f}}$ ’s in polynomial time.

Proof

From $A^{hom}_{q_{hom},q_{f}}$ (which is 1^∗2^∗-controlled) one can easily build 1^∗-controlled automata A ^hom A l t1^∗ ₁,…, A ^hom A l t1^∗ _t and 2^∗-controlled automata A ^hom A l t2^∗ ₁,…, A ^hom A l t2^∗ _t in polynomial time so that

$$L(A^{hom}_{q_{hom},q_{f}}) = \bigcup_{i \in \mathbf t } \big(L(A^{hom}Alt{1^{*}}_{i}) \cdot L(A^{hom}Alt{2^{*}}_{i})\big). $$

Also, it is easy to see that from $A^{het}_{q_{0},q_{het}}$ (which is (12)^∗(1^{≤ n}|2^{≤ n})-controlled) one can build (12)^∗-controlled automata A ^het A l t(12)^∗ ₁,…, A ^het A l t(12)^∗ _s , 1^{≤ n}-controlled automata A ^het A l t1^∗ ₁,…, A ^het A l t1^∗ _s and 2^{≤ n}-controlled automata A ^het A l t2^∗ ₁,…, A ^het A l t2^∗ _s in polynomial time, so that

$$L(A^{het}_{q_{0},q_{het}}) = \bigcup_{i \in \mathbf s } \big( L(A^{het}Alt{(12)^{*}}_{i}) \cdot L(A^{het}Alt{1^{*}}_{i}) \cdot L(A^{het}Alt{2^{*}}_{i}) \big). $$

We then have that

where $L_{\ell ,q_{het},q_{hom}} =\{(\ell ,a) \mid (q_{het}, (\ell ,a),q_{hom}) \text { in } A\}$. Note that, for ℓ = 1 we have

Since L1, i, j′ is 1^∗2^∗-controlled, we can apply the previous Claim 5 on L1, i, j′ obtaining (12)^∗-controlled automata $A^{\textit {head}}_{1}, \dotsc , A^{\textit {head}}_{m}$ and (1^∗|2^∗)-controlled automata $A^{tail}_{1}, \dotsc , A^{\textit {tail}}_{m}$ so that

$$\left[\kern-0.15em\left[{L^{\prime}_{1,i,j}}\right]\kern-0.15em\right] = \bigcup_{k \in \mathbf m} \left[\kern-0.15em\left[{ L(A^{head}_{k}) \cdot L(A^{tail}_{k}) }\right]\kern-0.15em\right]. $$

in polynomial time. Defining $L^{\prime \prime }_{1,i,j} = \bigcup _{k \in \mathbf m} L(A^{head}_{k}) \cdot L(A^{tail}_{k})$, we obtain that $L^{\prime \prime }_{1,i,j}$ is (12)^∗(1^∗|2^∗)-controlled, and an automaton for $L^{\prime \prime }_{1,i,j}$ can be computed in polynomial time. Thus,

where note that $L^{\prime \prime \prime }_{1} = \bigcup _{i \in \mathbf t, j \in \mathbf s} L(A^{het}Alt{(12)^{*}}_{j}) \cdot L^{\prime \prime }_{1,i,j}$ is (12)^∗(1^∗|2^∗)-controlled, and an automaton for $L^{\prime \prime \prime }_{1}$ can be built in polynomial time.

For ℓ = 2 we apply a similar reasoning,

this time taking

$$L^{\prime}_{2,i,j} = L(A^{het}Alt{1^{*}}_{j}) \cdot L(A^{hom}Alt{1^{*}}_{i}) \cdot L_{2,q_{het},q_{hom}} \cdot L(A^{het}Alt{2^{*}}_{j}) \cdot L(A^{hom}Alt{2^{*}}_{i}). $$

and obtaining, through Claim 5, a (12)^∗(1^∗|2^∗)-controlled language $L^{\prime \prime \prime }_{2}$ so that

Hence,

$$ \left[\kern-0.15em\left[{L_{q_{het},q_{hom}}}\right]\kern-0.15em\right] = \bigcup_{\ell \in \mathbf 2} \left[\kern-0.15em\left[{L^{\prime\prime\prime}_{\ell}}\right]\kern-0.15em\right] $$

and an automaton recognizing $\bigcup _{\ell \in \mathbf 2} L^{\prime \prime \prime }_{\ell }$ can be built in polynomial time. □

(III):

For any $L \in \sf RL_{\textit {lag}}^{\textit {fin}}$ with lag(L) = k, consider the singleton language $L^{\prime } = \{ 1^{k+1} \} \in \sf RL_{\textit {lag}}^{\textit {fin}}$. Note that any nonempty L′-controlled relation cannot have a L-resynchronization. Thus, there cannot be a canonical representative of $\sf RL_{\textit {lag}}^{\textit {fin}}$.

Note that, however, the class $\sf RL_{\textit {lag}}^{\textit {fin}} \cup \{(12)^{*} (1^{*}|2^{*})\}$ has (12)^∗(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. □

6 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 [9]. Even testing whether a rational relation is regular, or whether it has an empty intersection with a regular relation is undecidable [9]. 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 shift l a g(L) = ∞ the intersection problem is undecidable for Rel(L)? The answer to this question is negative: take for instance L = (122)^∗ with shift l a g(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 $\mathcal {C} \subseteq \sf RAT$ that are natural, expressive, and well-behaved, that is, so that

• ${\sf REC} \subsetneq \mathcal {C}$,

• $\mathcal {C}$ is effectively closed under union, intersection and complementation (i.e., is an effective Boolean algebra); and

• $\mathcal {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 $\mathbb {N}_{0}^{k}$ 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 $\mathbb {N}_{0}^{k}$, see [29].

A language L ⊆ k ^∗ is

• Parikh-injective if the function ${\Pi }: L \to \mathbb {N}_{0}^{k}$ is injective, and

• Parikh-surjective if the function ${\Pi }: L \to \mathbb {N}_{0}^{k}$ is surjective.

Example 2

• (12)^∗(1^∗|2^∗) and 1^∗2^∗ are Parikh-injective, while (1|2)^∗ is not.

• It can easily be shown that $L = w_{1}^{*} \cdot w_{2}^{*} \dotsb w_{\ell }^{*} \subseteq \mathbf k^{*}$ is Parikh-injective if ℓ ≤ k and {Π(w ₁), …, Π(w _ℓ )} generate a linear subspace of $(\mathbb {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 Parikh-surjective.

• It is easy to see that L _r/s as defined in (8) is Parikh-injective and Parikh-surjective for any choice of r, s. For example, if r = 1, s = 2, then L _r/s = (122)^∗(2^∗|1^∗2|1^∗), which is Parikh-injective and Parikh-surjective, since , as shown in Fig. 5, every element of $(\mathbb {N}_{0})^{2}$ is covered, and there is only one way to reach any element of $(\mathbb {N}_{0})^{2}$.

  Fig. 5

  

  Example of a Parikh-injective and Parikh-surjective language

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.

Theorem 4

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

• (I) Let $S_{1},S_{2} \subseteq (\mathbf 2 \times \mathbb {A})^{*}$ be two L-controlled relations. It is immediate that the language S _∪ = S ₁∪S ₂ is L-controlled. We then have that ⟦S ₁⟧∪⟦S ₂⟧=⟦S _∪⟧. The fact that it is closed under (inverse) alphabetic morphisms is immediate from the definition of Rel(L).

• (II) Let $S_{1},S_{2} \subseteq (\mathbf 2 \times \mathbb {A})^{*}$ be two L-controlled relations. It is immediate that the language S _∩ = S ₁∩S ₂ is L-controlled and ⟦S _∩⟧⊆⟦S ₁⟧∩⟦S ₂⟧. We show that ⟦S ₁⟧∩⟦S ₂⟧⊆⟦S _∩⟧. Suppose that (u, v) ∈ ⟦S ₁⟧∩⟦S ₂⟧. Then, there must be w ₁ ∈ S ₁ and w ₂ ∈ S ₂ so that ⟦w ₁⟧=⟦w ₂⟧=(u, v). Note that the projection onto the first component of w ₁ must be equal to the projection onto the first component of w ₂ since L is Parikh-injective. Then, we must have that w ₁ = w ₂ and thus (u, v) ∈ ⟦S _∩⟧.

• (III) Let $S \subseteq (\mathbf 2 \times \mathbb {A})^{*}$ be an L-controlled relation. Let S ^c be the complement of S and let ⟦S⟧^c be the complement of ⟦S⟧. We show the following,

  $$\left[\kern-0.15em\left[{S}\right]\kern-0.15em\right]^{c} ~~=~~ \left[\kern-0.15em\left[{S^{c} \cap (L \otimes \mathbb{A}^{*})}\right]\kern-0.15em\right], $$

  where $L \otimes \mathbb {A}^{*}$ denotes the set of all words u ⊗ v where |u|=|v|, u ∈ L and $v \in \mathbb {A}^{*}$.

• [⊆] Suppose (u, v)∉⟦S⟧. We show that there must be some $w \in S^{c} \cap (L \otimes \mathbb {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 $\mathbb {N}_{0}^{2}$, 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^{\prime } \otimes v^{\prime } \in (\mathbf 2 \times \mathbb {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 \in S^{c} \cap (L \otimes \mathbb {A}^{*})$.

• [⊇] Suppose now that $w \in S^{c} \cap (L \otimes \mathbb {A}^{*})$. We show that ⟦w⟧∉⟦S⟧. Assume, by means of contradiction, 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 \in S^{c} \cap (L \otimes \mathbb {A}^{*})$. Since L is Parikh-injective, and both w and w′ are L-controlled, it must be that w = w′, as otherwise ⟦w′⟧≠⟦w⟧, which is not possible as already observed. The contradiction comes from assuming that ⟦w⟧ ∈ ⟦S⟧. Thus, ⟦w⟧∉⟦S⟧ and $\left[\kern-0.15em\left[ {S}\right]\kern-0.15em\right] ^{c} \supseteq \left[\kern-0.15em\left[ { S^{c} \cap (L \otimes \mathbb {A}^{*})}\right]\kern-0.15em\right]$.

□

Corollary 2

If L ⊆ 2 ^∗ is Parikh-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 3

• REC and REG are effective boolean algebras since 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.

• It was shown in [13] 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

Theorem 4 cannot be generalized to finite unions of Parikh-injective languages, since for instance 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. Other directions are as follows.

Containment

One of the classical language-theoretic problems is language containment, which in this case is formulated as follows: given L ₁, L ₂ ⊆ 2 ^∗, is Rel(L ₁) ⊆ Rel(L ₂)? We would like to understand decidability/complexity issues for containment.

Two-wayness

Another way to extend the framework is by using two-way automata. Then, instead of having a synchronization language over the alphabet {1,2}, we have it over the alphabet $\{1,2,\bar 1,\bar 2\}$, where $i,\bar i$ are interpreted as moving the ith head to the right or to the left respectively. For example, in this context, $\textsc {Rel}({ 1^{*} \bar 2^{*}})$ contains the relation $\{(w,w^{r}) \in \mathbb {A}^{*} \times \mathbb {A}^{*} \mid w \text { is the reverse of } w^{r}\}$.

Model theory approach

One way of capturing regularity is by standard model-theoretic techniques: one can find (so-called universal automatic) first-order structures over Σ^∗ so that definable relations are regular (or nice subclasses of regular) relations. For instance, using the binary predicates for prefix and equal length, and unary predicates for each letter a∈Σ checking if the last letter of a word is a, we get one such structure [10]. By virtue of translation into automata, such structures are decidable, and their model-theoretic properties have been investigated [8]. We would like to extend this investigation and connect definability in infinite structures over Σ^∗ with different classes of relations of the form Rel(L).

Context-free relations

Another natural extension is to look for other classes of relations, say analogs of context-free languages. In particular, one can look at a generalization of rational relations, the pushdown relations of [16], which are those recognized by multi-tape automata with a stack or, equivalently, by a context-free grammar. In view of our approach here, this is not the only way of generalizing REC, REG, and RAT with pushdown automata. Indeed, in our framework, the simplest way to generalize these relations with the power of context-free languages, is to consider —instead of Rel(L)— the class Rel ^CF(L) as the set of all relations ⟦S⟧, for any L-controlled context-free language $S \subseteq ( \mathbf 2 \times \mathbb {A} )^{*}$.

In this framework we can show that Rel ^CF(2 ^∗), the context-free analog of rational relations, is the class of pushdown relations of [16]. Analogs of recognizable and regular relations are Rel ^CF((12)^∗(1^∗|2^∗)) and Rel ^CF(1^∗2^∗). Those properly contain REG and REC, respectively, are contained in Rel ^CF(2 ^∗), but are incomparable with each other as well as with RAT. We want to conduct a further study of those, perhaps extending to visibly pushdown languages [2] due to their appeal in both verification and modeling XML.

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 [11] and study logics over them, extending the approach of [5, 6] with data.