# On Classes of Regular Languages Related to Monotone WQOs

Mizuhito Ogawa, Victor Selivanov

► To cite this version:

Mizuhito Ogawa, Victor Selivanov. On Classes of Regular Languages Related to Monotone WQOs. 21st International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.235-247, 10.1007/978-3-030-23247-4_18. http-02387304

HAL Id: hal-02387304

https://inria.hal.science/hal-02387304

Submitted on 29 Nov 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Classes of Regular Languages
Related to Monotone WQOs

Mizuhito Ogawa¹ * and Victor Selivanov² **

¹ Japan Advanced Institute of Science and Technology
mizuhito@jaist.ac.jp

² A.P. Ershov Institute of Informatics Systems SB RAS
and Kazan Federal University
vseliv@iis.nsk.su

**Abstract.** We study relationships of monotone well quasiorders to regular languages and $\omega$-languages, concentrating on decidability of the lattices of upper sets on words and infinite words. We establish rather general sufficient conditions for decidability. Applying these conditions to concrete natural monotone WQOs, we obtain new decidability results and new proofs of some known results.

**Key words.** Regular language, monotone WQO, lattice of upper sets, periodic extension, decidability, difference hierarchy.

## 1 Introduction

In this work, we continue the study of relationships of well quasiorders (WQO) to regular languages and $\omega$-languages initiated in [2, 12] and continued by several people (see [8] and references therein for languages of finite words). In contrast with these works, we concentrate on the lattices of languages of upper sets of monotone WQOs on words and of induced WQOs on infinite words. In particular, we investigate decidability of such lattices and of levels of difference hierarchies over such lattices.

On this way, we identify natural apparently new classes of regular languages and prove decidability of them. We establish rather general sufficient conditions guaranteeing decidability. Applying these conditions to some natural monotone WQOs, we obtain new decidability results and new proofs of some known results. Our approach also suggests many interesting open questions.

After recalling some preliminaries in the next section we describe in Section 3 some general properties of the mentioned classes of regular languages. In Section 4, we prove decidability of some of those classes. In Sections 5 and 6, we study similar questions for $\omega$-languages. We conclude in Section 7 with mentioning some of the remaining open questions.

<footnote>* This research was partially supported by Japan Society for the Promotion of Science (JSPS), Core-to-Core Program (A. Advanced Research Networks).</footnote>

<footnote>** The research of V. Selivanov was supported by Russian Science Foundation, project 18-11-00100.</footnote>
## 2 Preliminaries

Here we recall some notation, notions and facts used throughout the paper. Some more special information is recalled in corresponding sections below.

We use standard set-theoretic notation, in particular $P(S)$ denotes the set of subsets of a set $S$ which forms a Boolean algebra under $\cup, \cap, \neg$. For a class $\mathcal{C} \subseteq P(S)$ of subsets of $S$, $BC(\mathcal{C})$ is the Boolean closure of $\mathcal{C}$ (i.e., the Boolean algebra generated by $\mathcal{C}$ within $(P(S); \cup, \cap, \neg, \emptyset, S))$, and $\text{co-}\mathcal{C} = \{\bar{C} \mid C \in \mathcal{C}\}$ is the class of complements $\bar{C} = S \setminus C$ of elements of $\mathcal{C}$.

We use standard notation and terminology on partially ordered sets (posets) and quasiordered sets, which may be found in [1]. Recall that a *quasiorder* (QO) on a non-empty set $S$ is a reflexive transitive binary relation on $S$. We denote QOs by symbols like $\leq$, $\leq$, $\sqsubseteq$, possibly with indices. A *partial order* on $S$ is an antisymmetric QO. The strict part of a QO $(S; \leq)$ is $\langle = \leq \setminus \geq$. Any QO $(S; \leq)$ induces the partial order $(S/\simeq; \leq)$, where the set $S/\simeq$ is the quotient set of $S$ under the equivalence relation $\simeq = \leq \cap \geq$ on $S$, i.e., the set $S/\simeq$ consists of all equivalence classes $[a] = \{x \mid x \simeq a\}$, $a \in S$. The partial order $\leq$ is overloaded by $[a] \leq [b] \leftrightarrow a \leq b$.

**Definition 1.** A QO $\leq$ on $\Sigma^*$ is monotone if $u \leq v$ implies $xuy \leq xvy$, for all $x, y \in \Sigma^*$.

A *well quasiorder* (WQO) on $S$ is a QO that has neither infinite strictly descending chains nor infinite antichains. There are several interesting and useful characterizations of WQOs of which we will frequently use the following: a QO $\leq$ on $S$ is a WQO iff for every non-empty upward closed set $U$ in $(S; \leq)$ there are finitely many $x_1, \dots, x_n \in U$ such that $U = \uparrow x_1 \cup \dots \cup \uparrow x_n$ where $\uparrow x = \{y \mid x \leq y\}$ for $x \in S$.

It is known that if $(S; \leq)$ is a WQO then every QO on $S$ that extends $\leq$, as well as every subset of $S$ with the induced QO, are also WQOs. Also, the Cartesian product of two WQOs is a WQO, and if $(S; \leq)$ is QO and $P, Q \subseteq S$ are such that $(P; \leq), (Q; \leq)$ are WQOs then $(P \cup Q; \leq)$ is a WQO. There are also many other useful closure properties of WQOs including the following: If $Q$ is a WQO, then $(Q^*; \leq^*)$ is a WQO where $Q^*$ is the set of finite sequences in $Q$ and $(x_1, \dots, x_m) \leq^* (y_1, \dots, y_n)$ means that for some strictly increasing $\varphi : \{1, \dots, m\} \to \{1, \dots, n\}$ we have $x_i \leq y_{\varphi(i)}$ for all $i$ (Higman's lemma [5]). In particular, the embedding relation on words over a finite alphabet is a WQO.

A couple of our proofs use a stronger notion of the hierarchy of WQOs (e.g., $\omega^2$-WQO) and a better quasiorder (BQO). Since they are more technical than a WQO, we just make corresponding references to the literature [11, 7, 9, 10].

We assume the reader to be familiar with the standard notions and facts of automata theory which may be found in [19, 14]. Throughout the paper, we work with a fixed alphabet $\Sigma$ (a finite nonempty set the elements of which are called letters). Let $\Sigma^*$ and $\Sigma^+$ be the sets of finite (respectively, of finite non-empty) words over $\Sigma$. Sets of words are called languages. The empty word is denoted by $\varepsilon$, $uv$ stands for the concatenation of words $u, v \in \Sigma^*$. By $\Sigma^n$, $\Sigma^{\leq n}$ and $\Sigma^{>n}$,
we denote the set of words $u$ of length $n$ (i.e., $|u| = n$), length less-than-equal $n$ (i.e., $|u| \le n$), and length greater than $n$ (i.e., $|u| > n$), respectively.

We use standard notation and terminology related to automata and regular expressions. In particular, $L(\mathcal{A})$ denote the language recognized by a finite automaton $\mathcal{A}$. Languages recognized by finite automata are called regular. The class of such languages is denoted by $\mathcal{R}_{\Sigma}$ or just by $\mathcal{R}$. This class is closed under union, intersection and complement, i.e. $(\mathcal{R}; \cup, \cap, \neg, \emptyset, \Sigma^*)$ is a Boolean algebra.

Let $\Sigma^\omega$ be the set of infinite words (also called $\omega$-words) $\alpha = \alpha(0)\alpha(1)\cdots$, $\alpha(i) \in \Sigma$, over $\Sigma$. For factors of infinite words we sometimes use notation like $\alpha[m, n) = \alpha(m)\cdots\alpha(n-1) \in \Sigma^{n-m}$. Sets of infinite words are called $\omega$-languages. We use standard notation and terminology related to automata on $\omega$-words (such as Büchi automata) and $\omega$-regular expressions. E.g., $v_1v_2\cdots$ is the infinite concatenation of $v_i \in \Sigma^+$ and $V_1.V_2.\cdots = \{v_1v_2\cdots | v_i \in V_i\}$ for all $V_i \subseteq \Sigma^+$. In particular, $v^\omega = vv\cdots$ is the $\omega$-power of $v \in \Sigma^+$. Let $L^\omega(\mathcal{A})$ be the $\omega$-language recognized by a Büchi automaton $\mathcal{A}$. Languages recognized by Büchi automata are called regular. The class of such languages is denoted by $\mathcal{R}_{\Sigma}^\omega$ or just by $\mathcal{R}^\omega$. This class is closed under union, intersection and complement.

A basic fact of automata theory (Myhill-Nerode theorem) states that a language $L \subseteq \Sigma^*$ is regular iff it is closed w.r.t. some congruence of finite index on $\Sigma^*$ (recall that a congruence is an equivalence relation $\equiv$ such that $u \equiv v$ implies $xuy \equiv xvy$, for all $x, y \in \Sigma^*$). In [2] the following version of Myhill-Nerode theorem was established:

**Theorem 1 (Theorem 3.3 in [2]).** A language $L \subseteq \Sigma^*$ is regular iff it is upward closed w.r.t. some monotone WQO on $\Sigma^*$.

Associate with any monotone WQO $\le$ the class $\mathcal{L}_\le$ of upward closed sets (also known as upper sets) in $(\Sigma^*; \le)$. By the above theorem, $\mathcal{L}_\le$ is a class of regular languages. One of the main objectives of this paper is the study of such and some other related classes. In particular, we are interested in the standard question for automata theory on the decidability of such classes (a class of regular languages is decidable if there is an algorithm which, for a given finite automaton $\mathcal{A}$, determines whether the language $L(\mathcal{A})$ is in the class). We also study analogous questions on classes of regular $\omega$-languages defined in a similar way based on an $\omega$-version of Theorem 1 established in [12]. Since this requires more technicalities, we recall the details in the corresponding sections below.

Let us recall some information on the difference hierarchies. By a *base in* a set $S$ we mean any class $\mathcal{L}$ of subsets of $S$ which is closed under union and intersection and contains $\emptyset, S$ as elements. For any $k < \omega$, let $\mathcal{L}(k)$ be the class of sets of the form $\bigcup_i(L_{2i} \setminus L_{2i+1})$, where $L_0 \supseteq L_1 \supseteq \cdots$ is a descending sequence of sets from $\mathcal{L}$ and $L_i = \emptyset$ for $i \ge k$. The sequence $\{\mathcal{L}(k)\}_{k<\omega}$ is called the *difference hierarchy over* $\mathcal{L}$. As is well-known, $\mathcal{L}(k) \cup \text{co-}\mathcal{L}(k) \subseteq \mathcal{L}(k+1)$ for each $k$, and the class $\bigcup_k \mathcal{L}(k)$ coincides with the Boolean closure $\text{BC}(\mathcal{L})$ of $\mathcal{L}$.

Associate with any QO $(Q; \le)$ the base $\mathcal{L}_\le$ in $Q$ consisting of all upper sets of $Q$, including the empty set; a set $L \subseteq Q$ is upper if $x \in L$ and $x \le y$ imply $y \in L$. By an *alternating chain* of length $k$ for a set $K \subseteq Q$ we mean a sequence
$(x_0, \dots, x_k)$ of elements of $\mathcal{Q}$ such that $x_0 \le \dots \le x_k$ and $x_i \in K \leftrightarrow x_{i+1} \notin K$ for every $i < k$. Such a chain is called a 1-alternating chain if $x_0 \in K$, otherwise it is called a 0-alternating chain. Variants of the following fact from [18] frequently appear when treating the difference hierarchies.

**Proposition 1.** Let $(Q; \leq)$ be a QO, $\mathcal{L}_{\leq}$ the base of upper sets, and $K \subseteq Q$. For every $k < \omega$, $K \in \mathcal{L}(k)$ iff $K$ has no 1-alternating chain of length $k$.

### 3 Classes of languages related to monotone WQOs

Here we make some observations on how the classes $\mathcal{L}_{\leq}$ look like.

Let $\mathcal{Q}(S)$ be the class of QOs on $S$. Define binary operations $\sqcap, \sqcup$ on $\mathcal{Q}(S)$ as follows: let $\leq \sqcap \leq'$ be the intersection of $\leq, \leq'$, and let $\leq \sqcup \leq'$ be the transitive closure of $\leq \sqcup \leq'$. Then $\leq \sqcap \leq'$ and $\leq \sqcup \leq'$ are respectively the infimum and the supremum of $\leq, \leq'$ in the poset $(\mathcal{Q}(S); \subseteq)$. Clearly, the equality $=_{S}$ and $S \times S$ are respectively the smallest and the largest elements of this poset. Therefore, the structure $(\mathcal{Q}(S); \sqcap, \sqcup, =_{S}, S \times S)$ is a bounded lattice. The set $\mathcal{W}(S)$ of WQOs on $S$ is closed under both operations, hence $(\mathcal{W}(S); \sqcap, \sqcup, S \times S)$ is the substructure of $(\mathcal{Q}(S); \sqcap, \sqcup, S \times S)$ with the largest element $S \times S$. We removed equality from the signature because if $S$ is infinite then $=_{S}$ is not a WQO.

**Lemma 1.** For every QO $\leq \subseteq on S$, $(\mathcal{L}_{\leq}; \cup, \cap, \emptyset, S)$ is a substructure of the structure $(P(S); \cup, \cap, \emptyset, S)$. The function $\leq \mapsto \mathcal{L}_{\leq}$ is an isomorphic embedding of $(\mathcal{Q}(S); \subseteq)$ into the poset $(\text{Sub}(P(S)); \supseteq)$ of substructures of the structure $(P(S); \cup, \cap, \emptyset, S)$.

Below we consider variants of $(\mathcal{Q}(S); \sqcap, \sqcup, S \times S)$ and $(\text{Sub}(P(S)); \sqcup, \sqcap, \{\emptyset, S\})$ where, for each $\mathcal{L}, \mathcal{M} \in \text{Sub}(P(S))$, $\mathcal{L} \sqcup \mathcal{M}$ is the substructure generated by $\mathcal{L} \cup \mathcal{M}$, $\mathcal{L} \sqcap \mathcal{M}$ is the intersection of $\mathcal{L}, \mathcal{M}$, and $\{\emptyset, S\}$ is the smallest element of $\text{Sub}(P(S))$. Note that the restriction of $\leq \mapsto \mathcal{L}_{\leq}$ to $\mathcal{W}(S)$ is an isomorphic embedding of $(\mathcal{W}(S); \sqcap, \sqcup, S \times S)$ into $(\text{Sub}(P(S)); \sqcup, \sqcap, \{\emptyset, P(S)\})$. In the particular case $S = \Sigma^*$ we can restrict the function $\leq \mapsto \mathcal{L}_{\leq}$ to the class $\mathcal{M}(\Sigma^*)$ of monotone WQOs. We collect some properties of this restriction which show, in particular, that any class $\mathcal{L}_{\leq}$ is a small portion of $\mathcal{R}$.

**Proposition 2.** 1. $\leq \mapsto \mathcal{L}_{\leq}$ is an embedding of $(\mathcal{M}(\Sigma^*); \sqcap, \sqcup, \Sigma^* \times \Sigma^*)$ into the structure $(\text{Sub}(\mathcal{R}); \sqcup, \sqcap, \{\emptyset, \Sigma^*\})$ of substructures of $(\mathcal{R}; \cup, \cap, \emptyset, \Sigma^*)$.

2. For any monotone WQO $\leq$, the bounded lattice $\mathcal{L}_{\leq}$ contains no infinite sequence of nonempty pairwise disjoint elements and is a proper subset of $\mathcal{R}$.

3. For any monotone WQO $\leq$, the bounded lattice $\mathcal{L}_{\leq}$ is Boolean iff $\leq$ is a congruence of finite index.

4. The poset $(\{\mathcal{L}_{\leq} | \leq \in \mathcal{M}(\Sigma^*)\}; \subseteq)$ is directed, has no maximal elements and satisfies $\bigcup\{\mathcal{L}_{\leq} | \leq \in \mathcal{M}(\Sigma^*)\} = \mathcal{R}$.

There are many examples of monotone WQOs of which we mention here four infinite series. The first one is formed by the congruences of finite index. In
particular, this class contains the so called syntactic congruences $\equiv_L$ of regular languages $L$ defined by: $u \equiv_L v$ iff $\forall x, y \in \Sigma^*(xuv \in L \leftrightarrow xvy \in L)$.

The second one is formed by the monotone WQOs of finite index (i.e., the associated congruence of which is of finite index). This class contains, e.g., the syntactic QOs $\leq_L$ associated with each regular language $L$ as follows [13]: $u \leq_L v$ iff $\forall x, y \in \Sigma^*(xuv \in L \rightarrow xvy \in L)$. Note that the associated congruence of $\leq_L$ is $\equiv_L$. This class also contains QOs associated with various one-sided Ehrenfeucht-Fraisse games (several examples may be found in [18]). For every such QO $\leq$, the Boolean algebra $BC(\mathcal{L}_{\leq})$, which is equal to $\mathcal{L}_{\leq}$, is finite.

Although the examples of monotone WQOs above are important for the general theory, they are not very interesting for this paper because the decidability problem for them is solved in an obvious way. Decidability issues are more interesting for monotone WQOs of infinite index. A typical example is the embedding partial order on words. We will discuss two infinite series of such QOs which will be used below to illustrate our methods.

The third infinite series consists of monotone WQOs studied in [3, 17]. For any $k < \omega$ the following partial order was studied: $u \leq_k v$, if either $u = v \in A^{<k}$ or $u, v \in A^{>k}$ such that $p_k(u) = p_k(v)$, $s_k(u) = s_k(v)$, and there is a $k$-embedding $f: u \to v$. Here $p_k(u)$ (resp. $s_k(u)$) is the prefix (resp. suffix) of $u$ of length $k$, and the $k$-embedding $f$ is a monotone injective function from $\{0, \dots, |u|-1\}$ to $\{0, \dots, |v|-1\}$ such that $u(i) \cdots u(i+k) = v(f(i)) \cdots v(f(i)+k)$ for all $i < |u|-k$. In [3, 17], it was shown that every $\leq_k$ is a monotone WQO. Note that the relation $\leq_0$ is just the embedding of words.

The fourth infinite series of monotone WQOs was introduced in [2]. A set $I \subseteq \Sigma^*$ is unavoidable if almost all words contain a word from $I$ as a factor. With any finite unavoidable set $I$, we associate a QO $(\Sigma^*; \leq_I)$ defined by: $u \leq_I v$ iff $v$ is obtained from $u$ by a finite (possibly, empty) series of subsequent insertions of words from $I$ as a factor. As shown in [2], any such $\leq_I$ is a monotone WQO.

# 4 Decidability of levels $\mathcal{L}_{\leq}(n)$

Here we consider decidability issues for the classes of languages discussed above. First we prove a rather general sufficient condition for decidability and next illustrate this condition for the mentioned examples of monotone WQOs. In this section letters $A, B$, possibly with indices, are used to denote finite automata.

**Definition 2.** We call a monotone WQO $\leq$ computable if it is a computable relation on $\Sigma^*$ and there is a computable family $\{A_u\}_{u \in \Sigma^*}$ of finite automata such that $L(A_u) = \uparrow u$ for each $u \in \Sigma^*$.

**Theorem 2.** For any computable monotone WQO $\leq$, the levels $\mathcal{L}_{\leq}(n)$ of the difference hierarchy over $\mathcal{L}_{\leq}$ are decidable uniformly on $n$.

*Proof.* We have to show that the relation $L(A) \in \mathcal{L}_{\leq}(n)$ is decidable. By the Post theorem from computability theory (see [16]), it suffices to show that the relation itself and its complement $L(A) \notin \mathcal{L}_{\leq}(n)$ are semidecidable (i.e., computably
enumerable). First we show semidecidability of the relation $L(\mathcal{A}) \in \mathcal{L}_{\leq}$. By the definition of $\mathcal{L}_{\leq}$, $L(\mathcal{A}) \in \mathcal{L}_{\leq}$ iff $L(\mathcal{A}) = \emptyset$ or

$$ \exists m < \omega \exists u_0, \dots, u_m \in \Sigma^*(L(\mathcal{A}) = L(\mathcal{A}_{u_0}) \cup \dots \cup L(\mathcal{A}_{u_m})). $$

As is well known, the relations $L(\mathcal{A}) = \emptyset$ and $L(\mathcal{A}) = L(\mathcal{A}_{u_0}) \cup \dots \cup L(\mathcal{A}_{u_m})$ are decidable, hence the relation $L(\mathcal{A}) \in \mathcal{L}_{\leq}$ is semidecidable.

Turning to the level $n$ of the difference hierarchy, we consider for technical reasons only the case $n = 2m$ of even $n$ (the case of odd $n$ is treated in a similar way). By the definition of $\mathcal{L}_{\leq}(n)$, we have: $L(\mathcal{A}) \in \mathcal{L}_{\leq}(n)$ iff

$$ \exists \mathcal{B}_0, \dots, \mathcal{B}_{n-1} (L(\mathcal{B}_0), \dots, L(\mathcal{B}_{n-1}) \in \mathcal{L}_{\leq} \wedge \\ L(\mathcal{B}_0) \supset \dots \supset L(\mathcal{B}_{n-1}) \wedge \\ L(\mathcal{A}) = \bigcup_{i<m} L(\mathcal{B}_{2i}) \setminus L(\mathcal{B}_{2i+1})). $$

Since the relations in the first conjunct are semidecidable and all other relations in big parenthesis are computable, the relation $L(\mathcal{A}) \in \mathcal{L}_{\leq}(n)$ is semidecidable. On the other hand, by Proposition 1 we have: $L(\mathcal{A}) \notin \mathcal{L}_{\leq}(n)$ iff

$$ \exists u_0, \dots, u_n \in \Sigma^* (u_0 < \dots < u_n \wedge u_0 \in L(\mathcal{A}) \wedge \forall i < n (u_i \in L(\mathcal{A}) \leftrightarrow u_{i+1} \notin L(\mathcal{A}))). $$

Since all relations in big parenthesis are computable, the relation $L(\mathcal{A}) \notin \mathcal{L}_{\leq}(n)$ is semidecidable. $\square$

We believe that Theorem 2 applies to many monotone WQOs (maybe, even to all finitely presented ones). One only has to check the computability of a given WQO. Here we observe that this is really the case for the examples of monotone WQOs discussed in Section 3.

**Corollary 1.** For all $k, n < \omega$, the levels $\mathcal{L}_{\leq_k}(n)$ of the difference hierarchy over $\mathcal{L}_{\leq_k}$ are decidable uniformly on $k, n$.

*Proof.* By Theorem 2, we have to show that the monotone WQOs $\leq_k$ are computable uniformly in $k$. This was shown in [3, 17]. $\square$

The above corollary is not new, earlier obtained in [3, 17]. Moreover, in those papers, the decidability of classes $BC(\mathcal{L}_{\leq_k})$ was also established. We hope that this last fact would be generalized to a wider class of monotone WQOs. In contrast, the next corollary of Theorem 2 seems not explicitly mentioned elsewhere.

**Theorem 3.** For any finite unavoidable set $I \subseteq \Sigma^*$, the levels $\mathcal{L}_{\leq_I}(n)$ of the difference hierarchy over $\mathcal{L}_{\leq_I}$ are decidable uniformly on $n$.

*Proof.* By Theorem 2, we only have to show that the monotone WQO $\leq_I$ is computable. This follows from an inspection of the proofs of Lemmas 4.6 and 4.7 in [2]. We also note that, by Theorem 4.13 in [2], it is decidable whether $I$ is unavoidable. Therefore, we also have uniformity on $I$. $\square$
# 5 Extending monotone WQOs to infinite words

Here we discuss how to extend notions and results about monotone WQOs to infinite words, based on [12]. Fix a monotone WQO $\leq$ on $\Sigma^*$. A QO $(\Sigma^*, \leq)$ is a monotone extension of $(\Sigma^*, \leq)$ if $\forall i(u_i \leq v_i)$ implies $u_1u_2u_3\cdots \leq v_1v_2v_3\cdots$. We define important subclasses of monotone extensions.

**Definition 3 (Definition 2.1 in [12]).** Let $(\Sigma^*; \leq)$ be a monotone WQO.

1. A QO $(\Sigma^*; \leq)$ is a periodic extension of $(\Sigma^*; \leq)$ if $\leq$ is a monotone extension of $\leq$, and for each $\alpha \in \Sigma^\omega$ there exist $u, v \in \Sigma^*$ with $\alpha \simeq uv^\omega$, where $\simeq = \leq \cap \geq$. The set of periodic extensions of $\leq$ is denoted by $PE(\leq)$.

2. A WQO $(\Sigma^*; \leq)$ is a regular extension of $(\Sigma^*; \leq)$ if $\leq$ is a monotone extension of $\leq$, and for each $\alpha \in \Sigma^\omega$ the upward closed set $\uparrow \alpha$ w.r.t. $\leq$ is a regular $\omega$-language. The set of regular extensions of $\leq$ is denoted by $RE(\leq)$.

**Definition 4 (Definition 3.1 in [12]).** A monotone extension $(\Sigma^*; \leq)$ of a monotone WQO $(\Sigma^*; \leq)$, is a continuous extension, if $(\Sigma^*; \leq)$ is a WQO, and

- For each $u, v \in \Sigma^*$ and $\alpha, \beta \in \Sigma^\omega$, $u \leq v$ and $\alpha \leq \beta$ imply $u\alpha \leq v\beta$.

- Let $u_j, v_j \in \Sigma^*$ for each $j$ and let $\alpha_i = v_1 \cdots v_{i-1}u_i \cdots$ for each $i$ and $\alpha_\infty = v_1v_2\cdots$. For $\beta \in \Sigma^\omega$, if $u_i \leq v_i$ and $\alpha_i \leq \beta$ for each $i$, then $\alpha_\infty \leq \beta$; and if $u_i \geq v_i$ and $\alpha_i \geq \beta$ for each $i$, then $\alpha_\infty \geq \beta$.

The set of continuous extensions of $\leq$ is denoted by $CE(\leq)$.

The following $\omega$-versions of Theorem 1 are fundamental for this paper.

**Theorem 4 (Theorem 2.2 and 3.2 in [12]).** For any $L \subseteq \Sigma^\omega$ we have:

1. $L$ is regular iff $L$ is upward closed under some periodic extension of a monotone WQO.

2. $L$ is regular iff $L$ is upward closed under some continuous extension of a monotone WQO.

We prove some relationships between introduced classes of extensions.

**Theorem 5.** For a monotone WQO $\leq$, $CE(\leq) \subseteq RE(\leq) = PE(\leq) \subseteq W(\Sigma^\omega)$.

*Proof.* Since Theorem 4 and its proof imply $PE(\leq) \cup CE(\leq) \subseteq RE(\leq)$ and $PE(\leq) \subseteq W(\Sigma^\omega)$, we show $RE(\leq) \subseteq PE(\leq)$. Let $\leq$ be a regular extension of $\leq$. For every $\alpha \in \Sigma^*$, we have to find $x, y \in \Sigma^*$ such that $\alpha \simeq xy^\omega$.

The upward closed set $\uparrow \alpha = L_\leq(\alpha)$ is a regular $\omega$-language so there is a congruence $\approx$ of finite index on $\Sigma^*$ that saturates $\uparrow \alpha$, i.e., $\uparrow \alpha = \bigcup U.V^\omega$ for $\approx$-classes $U, V$ with $V.V \subseteq V$ such that $U.V^\omega \cap U'.V'^\omega \neq \emptyset$ implies $U = U'$ and $V = V'$. Since $\leq$ is a WQO, there are finitely many (modulo $\cap \geq$) minimal elements $\{x_1, \cdots, x_l\}$ and $\{y_1, \cdots, y_k\}$ of $U$ and $V$, respectively. Since $\alpha \in U.V^\omega$, let $\alpha = uv_1v_2\cdots$ with $u \in U$ and $v_i \in V$. Then, $x_i \leq u$ for some $i$, and for all $j', s > 0$ there is $j$ with $y_j \leq v_{j'} \cdots v_{j'+s}$ (recall that $V.V \subseteq V$). By Ramsey theorem, we have $1 \leq j_1 < j_2 < \cdots$ and $j, j' \leq k$ such that $y_j \leq v_{j_1} \cdots v_{j_2-1}, v_{j_2} \cdots v_{j_3-1}, \cdots$ and $y_{j'} \leq v_1 \cdots v_{j_1-1}$. For any $\approx$-class $U'$ with $x_iy_{j'} \in U'$, $\alpha \in U.V^\omega \cap U'.V'^\omega$ implies $U = U'$. Let $x_{i'} \leq x_iy_{j'}$. Since $\leq$ is a monotone extension of $\leq$, $x_{i'}y_j^\omega \leq \alpha$. Since $x_{i'}y_j^\omega \in U.V^\omega \subseteq \uparrow \alpha$, $\alpha \leq x_{i'}y_j^\omega$. $\square$
Although we do not know whether $CE(\leq) = PE(\leq)$ for each monotone WQO $\leq$ at the moment, we guess this holds in natural cases.

**Lemma 2.** For a monotone WQO $(\Sigma^*; \leq)$, $PE(\leq)$ (resp. $CE(\leq)$) is closed under intersection.

*Proof.* Let $\leq_1, \leq_2 \in PE(\leq)$. Since $\leq = \leq_1 \cap \leq_2$ is a monotone extension of $\leq$, it remains to show that, for each $\alpha \in \Sigma^\omega$, there are $u, v \in \Sigma^*$ with $\alpha \simeq uv^\omega$. Let $\approx_1$ and $\approx_2$ be finite congruences saturating $L_{\leq_1}(\alpha)$ and $L_{\leq_2}(\alpha)$, respectively. Then, $\approx = \approx_1 \cap \approx_2$ is a finite congruence saturating $L_{\leq_1}(\alpha) \cap L_{\leq_2}(\alpha)$. By the proof of Theorem 5, there exist $\approx$-classes $U, V$ with $\alpha \in U.V^\omega$, and minimal elements $u \in U$ and $v \in V$ with $\alpha \approx uv^\omega$, which leads $\alpha \simeq uv^\omega$.

For $CE(\leq)$, the statement is immediate from Definition 4.

□

Associate with any monotone WQO $\leq$, the class $\mathcal{L}_{\leq}^{\omega}$ of $\omega$-languages which are upper sets w.r.t. some periodic extension of $\leq$, i.e., $\mathcal{L}_{\leq}^{\omega} = \bigcup\{\mathcal{L}_{\leq} | \leq \in PE(\leq)\}$.

**Proposition 3.** 1. $\leq_1 \to \mathcal{L}_{\leq}$ is an embedding from $(PE(\leq); \sqcup, \sqcup, \Sigma^\omega \times \Sigma^\omega)$ into the structure $(\text{Sub}(\mathcal{R}^\omega); \sqcup, \sqcup, \emptyset, \mathcal{R}^\omega)$ of substructures of $(\mathcal{R}^\omega; \cup, \sqcup, \emptyset, \Sigma^\omega)$.

2. For any $\leq \in PE(\leq)$, every sequence of nonempty pairwise disjoint elements of $\mathcal{L}_{\leq}$ is finite.

3. $\mathcal{L}_{\leq}^{\omega}$ is closed under union and intersection.

4. $\bigcup\{\mathcal{L}_{\leq}^{\omega} | \leq \in \mathcal{M}(\Sigma^*)\} = \mathcal{R}^{\omega}$.

The study of classes $\mathcal{L}_{\leq}^{\omega}$ becomes simpler if there is the smallest periodic extension $\leq$ of $\leq$, i.e., the smallest element of $(PE(\leq); \subseteq)$. The reason is that in this case $\mathcal{L}_{\leq}^{\omega} = \mathcal{L}_{\leq}$. Note that, for a periodic (resp. continuous) extension $\leq$, if a monotonic extension $\leq'$ of $\leq$ holds $\leq \subseteq \leq'$, $\leq'$ is also a periodic (resp. continuous) extension. Currently, we do not know whether every monotone WQO has the smallest periodic extension. Instead, we show the existence of the smallest continuous extension (Theorem 6), if $\leq$ is a monotone $\omega^2$-WQO over $\Sigma^*$.

**Lemma 3.** Let $\leq$ be a monotone WQO over $\Sigma^*$. Assume that a transfinite sequence $(\leq_\lambda)_{\lambda \in \Lambda}$ with $\leq_\lambda \in PE(\leq)$ holds $\leq_\lambda \supseteq \leq_{\lambda'}$ if $\lambda < \lambda'$. Let $\leq = \bigcap_{\lambda \in \Lambda} \geq_{\lambda'}$. Then, for each $\alpha \in \Sigma^\omega$, there is a countable subset $\Delta \subseteq \Lambda$ such that

1. For $\lambda \in \Lambda$, there is $\lambda' \in \Delta$ with $\lambda < \lambda'$.

2. For $\lambda \in \Lambda$, there are $\approx_\lambda$-classes $U_\lambda, V_\lambda$ saturating $L_{\leq_\lambda}(\alpha)$ and minimal elements (w.r.t. $\leq_\lambda$) $u_\lambda \in U_\lambda, v_\lambda \in V_\lambda$ such that $\alpha \in U_\lambda.V_\lambda^\omega$ and $u_\lambda v_\lambda^\omega \simeq_\lambda \alpha$.

3. For $\lambda, \lambda' \in \Delta$ with $\lambda < \lambda'$, $u_\lambda \leq u_{\lambda'}$ and $v_\lambda \leq v_{\lambda'}$.

4. $\alpha$ is the upper limit of $(u_\lambda v_\lambda^\omega)_{\lambda \in \Delta}$ (w.r.t. $\leq$), i.e., $\varlimsup_{\lambda \in \Delta} u_\lambda v_\lambda^\omega \simeq \alpha$.

*Proof.* From the proof of Theorem 5, for each $\alpha \in \Sigma^\omega$ and $\lambda \in \Lambda$, there exist $\approx_\lambda$-classes $U_\lambda, V_\lambda$ saturating $L_{\leq_\lambda}(\alpha)$ with $\alpha \in U_\lambda.V_\lambda^\omega$ and minimal elements $u_\lambda \in U_\lambda, v_\lambda \in V_\lambda$ with $\alpha \approx_\lambda u_\lambda v_\lambda^\omega$. Since $\leq$ is a monotone WQO, there is a countable subset $\Delta \subseteq \Lambda$ (by Ramsey-type argument [6]) such that $u_\lambda \leq u_{\lambda'}$, $v_\lambda \leq v_{\lambda'}$ for $\lambda, \lambda' \in \Delta$ with $\lambda < \lambda'$ and

<footnote>(*) for each $\lambda \in \Lambda$, there is $\lambda' \in \Delta$ with $\lambda < \lambda'$.</footnote>
Since $\leq_{\kappa} \in PE(\leq)$ for each $\kappa \in \Lambda$, $u_{\lambda}v_{\lambda}^{\omega} \leq_{\kappa} u_{\lambda'}v_{\lambda'}^{\omega}$. Since $\alpha \approx_{\kappa} u_{\kappa}v_{\kappa}^{\omega}$, $u_{\kappa}v_{\kappa}^{\omega} \leq_{\kappa} \alpha$. Thus, for each $\lambda, \lambda' \in \Delta$ with $\lambda < \lambda'$, $u_{\lambda}v_{\lambda}^{\omega} \leq_{\lambda'} \alpha$ (by instantiating $\lambda'$ to $\kappa$). With the condition $(*)$, for each $\lambda \in \Delta$, we have $u_{\lambda}v_{\lambda}^{\omega} \leq \alpha$.

Assume that $\overline{lim}_{\lambda \in \Delta} u_{\lambda}v_{\lambda}^{\omega} \simeq \alpha$ does not hold. Then, there exists $\beta$ such that $\beta < \alpha$ with $u_{\lambda}v_{\lambda}^{\omega} \leq \beta$ for each $\lambda \in \Delta$. Since $\beta < \alpha$, there exists $\lambda' \in \Delta$ with $\beta < \lambda'$, $\alpha$, which contradicts to $\alpha \simeq \lambda'$, $u_{\lambda'}v_{\lambda'}^{\omega}$.

**Corollary 2.** Let $\leq$ be a monotone $\omega^2$-WQO over $\Sigma^*$ and let $\{\leq_{\lambda}\}_{\lambda \in \Lambda}$ be a transfinite sequence of regular WQOs such that each $\leq_{\lambda}$ is a monotone extension of $\leq$ with $\leq_{\lambda} \supseteq \leq_{\lambda'}$ for $\lambda < \lambda'$. Then, $\leq = \bigcap_{\lambda \in \Lambda} \leq_{\lambda}$ is a WQO.

*Proof.* We borrow the notations in Lemma 3. For each $\alpha \in \Sigma^\omega$, we set $Seq(\alpha) = ((u_\lambda, v_\lambda))_{\lambda \in \Delta}$. Since $\leq \times \leq$ is an $\omega^2$-WQO on $\Sigma^* \times \Sigma^*$, the embedding $\hookrightarrow$ on $(\Sigma^* \times \Sigma^*)^\omega$ is a WQO [9]. Then, for each infinite sequence $\alpha_1, \alpha_2, \dots$, there are $i, j$ with $i < j$ and $Seq(\alpha_i) \hookrightarrow Seq(\alpha_j)$, which implies $\alpha_i \leq \alpha_j$ by Lemma 3. $\square$

Note that the assumption of $\omega^2$-WQO frequently holds for typical WQOs, e.g., $\leq_k [3, 17]$ and $\leq_I [2]$. An exception is Rado's example [15].

**Theorem 6.** Let $\leq$ be a monotone $\omega^2$-WQO over $\Sigma^*$. Then, $CE(\leq)$ has the smallest element (w.r.t. the set inclusion).

*Proof.* Note that a continuous extension of $\leq$ is a periodic extension by Theorem 5. For each descending chain $(\leq_{\lambda})_{\lambda \in \Lambda}$ in $CE(\leq)$, there is a lower bound (actually, the lower limit $\bigcap_{\lambda \in \Lambda} \leq_{\lambda}$) by Lemma 3. Since $\bigcap_{\lambda \in \Lambda} \leq_{\lambda}$ is a WQO by Corollary 2, $\bigcap_{\lambda \in \Lambda} \leq_{\lambda} \in CE(\leq)$ from Definition 4. Therefore, there is a minimal element $\leq$ in $CE(\leq)$ by Zorn's Lemma. This $\leq$ is the smallest; otherwise, there exists an incomparable element $\leq'$ in $CE(\leq)$. Since $\leq \cap \leq' \subsetneq$, $\leq'$ is a continuous extension of $\leq$ by Lemma 2, which contradicts to the minimality. $\square$

**Corollary 3.** Let $\leq$ be a monotone $\omega^2$-WQO over $\Sigma^*$. If $CE(\leq)=PE(\leq)$, $PE(\leq)$ has the smallest element (w.r.t. the set inclusion).

Although Corollary 3 suggests that many monotone WQOs have smallest periodic extensions, the proof is nonconstructive and gives no hint how such an extension looks like. It makes sense to look for explicit descriptions of smallest periodic extensions for concrete natural monotone WQOs. Here we provide such descriptions for monotone WQOs in Section 3.

For any $k < \omega$, define the binary relation $\leq_k$ on $\Sigma^\omega$ as follows: $\alpha \leq_k \beta$ if $p_k(\alpha) = p_k(\beta)$ and there is a $k$-embedding $f : \alpha \to \beta$. Here $p_k(\alpha) = \alpha[0, k)$ is the prefix of $\alpha$ of length $k$, and the $k$-embedding $f$ is a monotone injective function on $\omega$ such that $\alpha[i, i + k] = \beta[f(i), f(i) + k]$ for all $i < \omega$. Note that the relation $\leq_0$ is just the embedding of $\omega$-words.

For any $\alpha \in \Sigma^\omega$ and $n \ge 1$, let $F_n(\alpha)$ (resp. $F_n^\infty(\alpha)$) be the set of $u \in \Sigma^n$ such that $u$ is a factor of $\alpha$ (resp. $u$ occurs in $\alpha$ as a factor infinitely often). Let $F_n(v)$ for $v \in \Sigma^+$ be defined similarly, $F(v) = \bigcup_n F_n(v)$, and $F^\infty(\alpha) = \bigcup_n F_n^\infty(\alpha)$. The next two lemmas are included without proof in order to help the reader to reconstruct omitted details in the proof of Theorem 7.
**Lemma 4.** 1. $F_n^\infty(\alpha) \neq \emptyset$.

2. If $x \in F_n^\infty(\alpha)$ and $m > n$ then $x$ is a factor of some $y \in F_m^\infty(\alpha)$.

3. If $x$ is a factor of $y \in F_n^\infty(\alpha)$ then $x \in F_{|x|}^\infty(\alpha)$.

4. If there is a $k$-embedding of $\alpha$ into $\beta$ then $F_{k+1}^\infty(\alpha) \subseteq F_{k+1}^\infty(\beta)$.

Define the binary relation $R_k$ on $\Sigma^\omega$ by: $\alpha R_k \beta$ iff there exist factorizations $\alpha = u_0 u_1 \cdots$, $\beta = v_0 v_1 \cdots$ such that $u_i, v_i \in \Sigma^+$ and $u_i \le_k v_i$ for all $i$.

**Lemma 5.** 1. $R_k \subseteq \leq_k$.

2. For any $\alpha \in \Sigma^\omega$ there exist $u, v \in \Sigma^+$ such that $\alpha R_k \beta R_k \alpha$ where $\beta = uv^\omega$.

3. $\alpha R_k \beta$ iff $\alpha \leq_k \beta$ and $F_{2k}^\infty(\alpha) \cap F_{2k}^\infty(\beta) \neq \emptyset$.

4. If $u^\omega \leq_k v^\omega$ then $u^\omega R_k \gamma R_k u^\omega v^\omega$ for some $\gamma \in \Sigma^\omega$.

**Theorem 7.** For any $k < \omega$, $\leq_k$ is the smallest periodic extension of $\leq_k$.

*Proof.* Obviously, $\leq_k$ is a QO. By Lemma 5(1), $\leq_k$ is a monotone extension of $\leq_k$. By Lemma 5(2), $\leq_k$ is a periodic extension of $\leq_k$.

It remains to show that $\leq_k \subseteq \leq$ for every $\leq \in PE(\leq_k)$. Since $\leq$ is a monotone extension of $\leq_k$, $R_k \subseteq \leq$. Since $\leq$ is transitive, $TC(R_k) \subseteq \leq_k$, where $TC(R_k)$ is the transitive closure of $R_k$. Hence, it suffices to show that $\leq_k \subseteq TC(R_k)$.

Let $\alpha \leq_k \beta$. By Lemma 5(2), $\alpha R_k u v^\omega R_k \alpha$ and $\beta R_k u_1 v_1^\omega R_k \beta$ for some $u, v, u_1, v_1$. By Lemma 5(4), $u v^\omega R_k \gamma R_k u_1 v_1^\omega$ for some $\gamma$. Thus, $\alpha TC(R_k) \beta$. $\square$

**Remark 1.** The analogue $R$ of the relation $R_k$ may be defined for any monotone WQO $\leq$, and again we have $TC(R) \subseteq \leq$ for each $\leq \in PE(\leq)$. Thus, if $TC(R)$ is a periodic extension of $\leq$ then it is the smallest one. So in the search of the smallest periodic extension $TC(R)$ is the first candidate.

**Theorem 8.** For any finite unavoidable set $I \subseteq \Sigma^+$, the relation $\leq_I = R_I$ is the smallest periodic extension of $\leq_I$.

*Proof Sketch.* The relation $R_I$ is the smallest monotone extension of $\leq_I$. It is easy to check that $R_I$ is a QO. An inspection of the proofs of Lemma 4.7 and Theorem 4.8 in [2] shows that the relation $\leq_I$ is not only a WQO but also a BQO. The standard technique of BQO-theory applies to show that $\leq_I$ is a BQO, hence also a WQO. By Theorem 5, it suffices to show that any upper set $\uparrow \alpha$ w.r.t. $\leq_I$ is regular.

$\uparrow \alpha$ is accepted by a pushdown Büchi automaton, which pushes when it starts to read an inserted element $u$ of $I$ and pops when $u$ is read while reading $\alpha$. By Lemma 4.7 in [2], the size of the stack is bounded by the smallest number $k_0$ such that any word in $\Sigma^{\geq k_0}$ has a factor from $I$. Thus, the pushdown Büchi automaton is reduced to a finite Büchi automaton. $\square$

# 6 Decidability of levels $\mathcal{L}_{\leq}(n)$

Here we consider, in parallel to Section 4, decidability issues for the classes of $\omega$-languages related to monotone WQOs. First we prove a rather general sufficient condition for decidability and next illustrate this condition for the mentioned examples of periodic extensions of monotone WQOs. Letters $A, B$, possibly with indices, are now used to denote Büchi automata.
**Definition 5.** Let $\leq$ be a monotone WQO. By a computable periodic extension of $\leq$ we mean a periodic extension $\leq$ of $\leq$ such that the 4-ary relation $uv^\omega \leq u_1 v_1^\omega$ on $\Sigma^+$ is computable and there is a computable family $\{A_{u,v}\}_{u,v \in \Sigma^+}$ of Büchi automata such that $L^\omega(A_{u,v}) = \{\alpha \mid uv^\omega \leq \alpha\}$ for all $u,v \in \Sigma^+$.

The proof of next result is similar to that of Theorem 2.

**Theorem 9.** For any computable periodic extension $\leq$ of a monotone WQO $\leq$, the levels $\mathcal{L}_{\leq}(n)$ of difference hierarchy over $\mathcal{L}_{\leq}$ are decidable uniformly on $n$.

We illustrate Theorem 9 by the monotone WQOs from Section 3. Note that by Theorem 7 we have $\mathcal{L}_{\leq_k} = \mathcal{L}_{\leq_k}^\omega$ and $\mathcal{L}_{\leq_I} = \mathcal{L}_{\leq_I}^\omega$.

**Theorem 10.** The levels $\mathcal{L}_{\leq_k}(n)$ of the difference hierarchy over $\mathcal{L}_{\leq_k}$ are decidable uniformly on $k, n$.

*Proof.* By Theorem 9, it suffices to show that $\leq_k$ is a computable periodic extension of $\leq_k$ uniformly on $k$. Since $uv^\omega \leq_k u_1 v_1^\omega$ iff $u \leq_k u_1 v_1^{|u|}$ and $v \leq_k v_1^{|v|}$ for all $k < \omega$ and $u, u_1, v, v_1 \in \Sigma^+$, the relation $uv^\omega \leq_k u_1 v_1^\omega$ is computable uniformly on $k$.

It remains to find a computable family $\{A_{k,u,v}\}_{k<\omega, u,v \in \Sigma^+}$ of Büchi automata such that $L^\omega(A_{k,u,v}) = \{\alpha \mid uv^\omega \leq_k \alpha\}$ for all $k < \omega, u, v \in \Sigma^+$. From $k, u, v$ it is straightforward to compute a first order sentence $\varphi_{k,u,v}$ of signature $\{\langle, Q_a \mid a \in \Sigma\}$ such that $L_{\varphi_{k,u,v}}^\omega = \{\alpha \mid uv^\omega \leq_k \alpha\}$ where $L_\varphi^\omega$ is the set of $\omega$-words that satisfy a given sentence $\varphi$ (see [19] for details of the logical approach to regular languages). By the Büchi-Trakhtenbrot theorem, there is a computable family $\{A_{k,u,v}\}_{k<\omega, u,v \in \Sigma^+}$ of Büchi automata such that $L^\omega(A_{k,u,v}) = L_{\varphi_{k,u,v}}^\omega$ for all $k < \omega, u, v \in \Sigma^+$. $\square$

**Theorem 11.** For every finite unavoidable set of words $I$, the levels $\mathcal{L}_{\leq_I}(n)$ of the difference hierarchy over $\mathcal{L}_{\leq_I}$ are decidable uniformly on $n$.

*Proof.* By Theorem 9, it suffices to show that $\leq_k$ is a computable periodic extension of $\leq_k$. As above, for all $u, u_1, v, v_1 \in \Sigma^+$ we have: $uv^\omega \leq_I u_1 v_1^\omega$ iff $u \leq_I u_1 v_1^{|u|}$ and $v \leq_I v_1^{|v|}$, hence the relation $uv^\omega \leq_I u_1 v_1^\omega$ is computable.

If $\alpha = uv^\omega$ then the Büchi automaton $A_{u,v}$ constructed in the proof of Theorem 8 verifies the second condition of the computability of $\leq_I$. $\square$

# 7 Conclusion and open questions

We hope that the above results clearly demonstrate that the classes of upper sets induced by monotone WQOs and their extensions to infinite words are interesting and deserve further investigation. Many interesting questions remain open, we mention some of them below.

1. It is already clear that the class of monotone WQOs is rich. However, we still do not know whether this class is countable.
2. Is there a nice classification of finitely presented monotone WQOs? Are all such WQOs computable?

3. Does every finitely presented monotone WQO have the smallest periodic extension? Are all such extensions computable?

4. Our methods of proving decidability are easy and natural but they do not provide any upper complexity bounds at all. One has to develop new methods which do provide reasonable upper bounds. Such methods for a natural class of monotone WQOs were developed in [4].

5. Ideas and notions of this paper are related to those in the literature on (ordered) semigroups and $\omega$-semigroups [13, 14]. Further investigation of these relationships seems promising.

## References

1. Davey B.A., Priestley H.A.: *Introduction to Lattices and Order*. Cambridge, 1994.

2. Ehrenfeucht A., Haussler D., Rozenberg G.: On regularity of context-free languages. *Theoretical Computer Science*, 27:311–332 (1983)

3. Glaßer C., Schmitz H.: The Boolean structure of dot-depth one. *Journal of Automata, Languages and Combinatorics*, 6:437–452 (2001)

4. Glasser C., Schmitz H., Selivanov V.: Efficient algorithms for membership in boolean hierarchies of regular languages. *Theoretical Computer Science*, 646(C):86–108 (2016)

5. Higman G.: Ordering by divisibility in abstract algebras. *Proc. Lond. Math. Soc.* 2(3), 326–336 (1952)

6. Kříž I., Thomas R.: Ordinal types in Ramsey Theory and Well-Partial-Ordering Theory. *Mathematics of Ramsey Theory*, Part II, 57–95, Springer (1990)

7. Laver R.: Better-quasi-orderings and a class of trees. In *Studies in foundations and combinatorics, advances in mathematics supplementary studies*, volume 1:31–48. Academic Press (1978)

8. de Luca A., Varricchio S.: Finiteness and Regularity in Semigroups and Formal Languages. *Monographs in Theoretical Computer Science*, Springer (1999)

9. Marcone A.: Foundations of BQO theory. *Trans. AMS*, 345(2):641–660 (1994)

10. Marcone A.: Fine analysis of the quasi-orderings on the power set. *Order*, 18:339–347 (2001)

11. Nash-Williams C.ST.J.A.: On well-quasi-ordering transfinite sequences. *Proc. Cambridge Phil. Soc.*, 61:33–39 (1965)

12. Ogawa M.: Well-quasi-orders and regular omega-languages. *Theoretical Computer Science*, 324(1):55–60 (2004)

13. Pin J.-E.: Positive varieties and infinite words, LATIN 98, LNCS 1380:76-87 (1998)

14. Perrin D., Pin J.-E.: Infinite Words. *Pure and Applied Mathematics*, 141 (2004)

15. R. Rado. Partial well-ordering of sets of vectors. *Mathematika*, 1:89–95 (1954)

16. Rogers H., jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.

17. Selivanov V.L.: A logical approach to decidability of hierarchies of regular star-free languages. *LNCS* 2010:539–550 (2001)

18. Selivanov V. L.: Hierarchies and reducibilities on regular languages related to modulo counting. *RAIRO Theoretical Informatics and Applications*, 41:95–132 (2009)

19. Thomas W.: Automata on infinite objects. *Handbook of Theoretical Computer Science*, volume B, chapter 4:133–192. Elsevier Science Publishers (1990)