Mizuhito Ogawa
email: mizuhito@jaist.ac.jp

Victor Selivanov

On Classes of Regular Languages Related to Monotone WQOs

Keywords: Regular language, monotone WQO, lattice of upper sets, periodic extension, decidability, difference hierarchy

We study relationships of monotone well quasiorders to regular languages and ω-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.

Introduction

In this work, we continue the study of relationships of well quasiorders (WQO) to regular languages and ω-languages initiated in [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF][START_REF] Ogawa | Well-quasi-orders and regular omega-languages[END_REF] and continued by several people (see [START_REF] De Luca | Finiteness and Regularity in Semigroups and Formal Languages[END_REF] 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 ω-languages. We conclude in Section 7 with mentioning some of the remaining open questions.

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 ∪, ∩,¯. For a class C ⊆ P (S) of subsets of S, BC(C) is the Boolean closure of C (i.e., the Boolean algebra generated by C within (P (S); ∪, ∩,¯, ∅, S)), and co-C = { C | C ∈ C} is the class of complements C = S \ C of elements of C.

We use standard notation and terminology on partially ordered sets (posets) and quasiordered sets, which may be found in [START_REF] Davey | Introduction to Lattices and Order[END_REF]. 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 ≤, , , possibly with indices. A partial order on S is an antisymmetric QO. The strict part of a QO (S; ≤) is < = ≤ \ ≥. Any QO (S; ≤) induces the partial order (S/ ; ≤), where the set S/ is the quotient set of S under the equivalence relation = ≤ ∩ ≥ on S, i.e., the set S/ consists of all equivalence classes [a] = {x | x a}, a ∈ S. The partial order ≤ is overloaded by

[a] ≤ [b] ↔ a ≤ b. Definition 1. A QO ≤ on Σ * is monotone if u ≤ v implies xuy ≤ xvy, for all x, y ∈ Σ * .
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 ≤ on S is a WQO iff for every non-empty upward closed set U in (S; ≤) there are finitely many x 1 , . . . ,

x n ∈ U such that U = ↑ x 1 ∪ • • • ∪ ↑ x n where ↑ x={y | x ≤ y} for x ∈ S.
It is known that if (S; ≤) is a WQO then every QO on S that extends ≤, 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; ≤) is QO and P, Q ⊆ S are such that (P ; ≤), (Q; ≤) are WQOs then (P ∪ Q; ≤) is a WQO. There are also many other useful closure properties of WQOs including the following: If Q is a WQO, then (Q * ; ≤ * ) is a WQO where Q * is the set of finite sequences in Q and (x 1 , . . . , x m ) ≤ * (y 1 , . . . , y n ) means that for some strictly increasing ϕ : {1, . . . , m} → {1, . . . , n} we have x i ≤ y ϕ(i) for all i (Higman's lemma [START_REF] Higman | Ordering by divisibility in abstract algebras[END_REF]). 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., ω 2 -WQO) and a better quasiorder (BQO). Since they are more technical than a WQO, we just make corresponding references to the literature [START_REF] Nash-Williams | On well-quasi-ordering transfinite sequences[END_REF][START_REF] Laver | Better-quasi-orderings and a class of trees[END_REF][START_REF] Marcone | Foundations of BQO theory[END_REF][START_REF] Marcone | Fine analysis of the quasi-orderings on the power set[END_REF].

We assume the reader to be familiar with the standard notions and facts of automata theory which may be found in [START_REF] Thomas | Automata on infinite objects[END_REF][START_REF] Perrin | Infinite Words[END_REF]. Throughout the paper, we work with a fixed alphabet Σ (a finite nonempty set the elements of which are called letters). Let Σ * and Σ + be the sets of finite (respectively, of finite non-empty) words over Σ. Sets of words are called languages. The empty word is denoted by ε, uv stands for the concatenation of words u, v ∈ Σ * . By Σ n , Σ ≤n and Σ >n , we denote the set of words u of length n (i.e., |u| = n), length less-than-equal n (i.e., |u| ≤ 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(A) denote the language recognized by a finite automaton A. Languages recognized by finite automata are called regular. The class of such languages is denoted by R Σ or just by R. This class is closed under union, intersection and complement, i.e. (R; ∪, ∩,¯, ∅, Σ * ) is a Boolean algebra.

Let Σ ω be the set of infinite words (also called ω-words

) α = α(0)α(1) • • • , α(i) ∈ Σ, over Σ. For factors of infinite words we sometimes use notation like α[m, n) = α(m) • • • α(n -1) ∈ Σ n-m .
Sets of infinite words are called ωlanguages. We use standard notation and terminology related to automata on ω-words (such as Büchi automata) and ω-regular expressions. E.g.,

v 1 v 2 • • • is the infinite concatenation of v i ∈ Σ + and V 1 .V 2 . • • • = {v 1 v 2 • • • | v i ∈ V i } for all V i ⊆ Σ + . In particular, v ω =vv • • • is the ω-power of v ∈ Σ + . Let L ω (A)
be the ω-language recognized by a Büchi automaton A. Languages recognized by Büchi automata are called regular. The class of such languages is denoted by R ω Σ or just by R ω . This class is closed under union, intersection and complement.

A basic fact of automata theory (Myhill-Nerode theorem) states that a language L ⊆ Σ * is regular iff it is closed w.r.t. some congruence of finite index on Σ * (recall that a congruence is an equivalence relation ≡ such that u ≡ v implies xuy ≡ xvy, for all x, y ∈ Σ * ). In [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF] the following version of Myhill-Nerode theorem was established: Theorem 1 (Theorem 3.3 in [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF]). A language L ⊆ Σ * is regular iff it is upward closed w.r.t. some monotone WQO on Σ * .

Associate with any monotone WQO ≤ the class L ≤ of upward closed sets (also known as upper sets) in (Σ * ; ≤). By the above theorem, L ≤ 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 A, determines whether the language L(A) is in the class). We also study analogous questions on classes of regular ω-languages defined in a similar way based on an ω-version of Theorem 1 established in [START_REF] Ogawa | Well-quasi-orders and regular omega-languages[END_REF]. 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 L of subsets of S which is closed under union and intersection and contains ∅, S as elements. For any k < ω, let L(k) be the class of sets of the form i (L 2i \ L 2i+1 ), where L 0 ⊇ L 1 ⊇ • • • is a descending sequence of sets from L and L i = ∅ for i ≥ k. The sequence {L(k)} k<ω is called the difference hierarchy over L. As is well-known, L(k)∪co-L(k) ⊆ L(k + 1) for each k, and the class k L(k) coincides with the Boolean closure BC(L) of L.

Associate with any QO (Q; ≤) the base L ≤ in Q consisting of all upper sets of Q, including the empty set; a set L ⊆ Q is upper if x ∈ L and x ≤ y imply y ∈ L. By an alternating chain of length k for a set K ⊆ Q we mean a sequence

(x 0 , . . . , x k ) of elements of Q such that x 0 ≤ • • • ≤ x k and x i ∈ K ↔ x i+1 ∈ K for every i < k. Such a chain is called a 1-alternating chain if x 0 ∈ K, otherwise it
is called a 0-alternating chain. Variants of the following fact from [START_REF] Selivanov | Hierarchies and reducibilities on regular languages related to modulo counting[END_REF] frequently appear when treating the difference hierarchies.

Proposition 1. Let (Q; ≤) be a QO, L ≤ the base of upper sets, and K ⊆ Q. For every k < ω, K ∈ L(k) iff K has no 1-alternating chain of length k.

Classes of languages related to monotone WQOs

Here we make some observations on how the classes L ≤ look like.

Let Q(S) be the class of QOs on S. Define binary operations , on Q(S) as follows: let ≤ ≤ be the intersection of ≤, ≤ , and let ≤ ≤ be the transitive closure of ≤ ∪ ≤ . Then ≤ ≤ and ≤ ≤ are respectively the infimum and the supremum of ≤, ≤ in the poset (Q(S); ⊆). Clearly, the equality = S and S ×S are respectively the smallest and the largest elements of this poset. Therefore, the structure (Q(S); , , = S , S ×S) is a bounded lattice. The set W(S) of WQOs on S is closed under both operations, hence (W(S); , , S × S) is the substructure of (Q(S); , , S × S) with the largest element S × S. We removed equality from the signature because if S is infinite then = S is not a WQO. Lemma 1. For every QO ≤ on S, (L ≤ ; ∪, ∩, ∅, S) is a substructure of the structure (P (S); ∪, ∩, ∅, S). The function ≤ → L ≤ is an isomorphic embedding of (Q(S); ⊆) into the poset (Sub(P (S)); ⊇) of substructures of the structure (P (S); ∪, ∩, ∅, S).

Below we consider variants of (Q(S); , , S×S) and (Sub(P (S)); , , {∅, S}) where, for each L, M ∈ Sub(P (S)), L M is the substructure generated by L ∪ M, L M is the intersection of L, M, and {∅, S} is the smallest element of Sub(P (S)). Note that the restriction of ≤ → L ≤ to W(S) is an isomorphic embedding of (W(S); , , S × S) into (Sub(P (S)); , , {∅, P (S)}). In the particular case S = Σ * we can restrict the function ≤ → L ≤ to the class M(Σ * ) of monotone WQOs. We collect some properties of this restriction which show, in particular, that any class L ≤ is a small portion of R.

Proposition 2. 1. ≤ → L ≤ is an embedding of (M(Σ * ); , , Σ * × Σ * ) into the structure (Sub(R); , , {∅, Σ * }) of substructures of (R; ∪, ∩, ∅, Σ * ). 2.
For any monotone WQO ≤, the bounded lattice L ≤ contains no infinite sequence of nonempty pairwise disjoint elements and is a proper subset of R.

For any monotone WQO ≤, the bounded lattice

L ≤ is Boolean iff ≤ is a congruence of finite index. 4. The poset ({L ≤ |≤∈ M(Σ * )}; ⊆) is directed, has no maximal elements and satisfies {L ≤ |≤∈ M(Σ * )} = 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 ≡ L of regular languages L defined by: u

≡ L v iff ∀x, y ∈ Σ * (xuv ∈ L ↔ xvy ∈ 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 ≤ L associated with each regular language L as follows [START_REF] Pin | Positive varieties and infinite words[END_REF]:

u ≤ L v iff ∀x, y ∈ Σ * (xuv ∈ L → xvy ∈ L).
Note that the associated congruence of ≤ L is ≡ L . This class also contains QOs associated with various one-sided Ehrenfeucht-Fraisse games (several examples may be found in [START_REF] Selivanov | Hierarchies and reducibilities on regular languages related to modulo counting[END_REF]). For every such QO ≤, the Boolean algebra BC(L ≤ ), which is equal to L , 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 [START_REF] Glaßer | The Boolean structure of dot-depth one[END_REF][START_REF] Selivanov | A logical approach to decidability of hierarchies of regular star-free languages[END_REF]. For any k < ω the following partial order was studied:

u ≤ k v, if either u = v ∈ A ≤k or u, v ∈ A >k such that p k (u) = p k (v), s k (u) = s k (v), and there is a k-embedding f : u → 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. . . . , |u| -1} to {0. . . . , |v|-1} such that u(i) • • • u(i+k) = v(f (i)) • • • v(f (i)+k) for all i < |u|-k.
In [START_REF] Glaßer | The Boolean structure of dot-depth one[END_REF][START_REF] Selivanov | A logical approach to decidability of hierarchies of regular star-free languages[END_REF], it was shown that every ≤ k is a monotone WQO. Note that the relation ≤ 0 is just the embedding of words.

The fourth infinite series of monotone WQOs was introduced in [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF]. A set I ⊆ Σ * is unavoidable if almost all words contain a word from I as a factor. With any finite unavoidable set I, we associate a QO (Σ * ; ≤ I ) defined by: u ≤ 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 [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF], any such ≤ I is a monotone WQO.

Decidability of levels L ≤ (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 ≤ computable if it is a computable relation on Σ * and there is a computable family {A u } u∈Σ * of finite automata such that L(A u ) =↑ u for each u ∈ Σ * . Theorem 2. For any computable monotone WQO ≤, the levels L ≤ (n) of the difference hierarchy over L ≤ are decidable uniformly on n.

Proof. We have to show that the relation L(A) ∈ L ≤ (n) is decidable. By the Post theorem from computability theory (see [START_REF] Rogers | Theory of Recursive Functions and Effective Computability[END_REF]), it suffices to show that the relation itself and its complement L(A) ∈ L ≤ (n) are semidecidable (i.e., computably enumerable). First we show semidecidability of the relation

L(A) ∈ L ≤ . By the definition of L ≤ , L(A) ∈ L ≤ iff L(A) = ∅ or ∃m < ω∃u 0 , • • • , u m ∈ Σ * (L(A) = L(A u0 ) ∪ • • • ∪ L(A um )).
As is well known, the relations

L(A) = ∅ and L(A) = L(A u0 ) ∪ • • • ∪ L(A um ) are decidable, hence the relation L(A) ∈ L ≤ 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 L ≤ (n), we have:

L(A) ∈ L ≤ (n) iff ∃B 0 , . . . , B n-1 L(B 0 ), . . . , L(B n-1 ) ∈ L ≤ ∧ L(B 0 ) ⊇ • • • ⊇ L(B n-1 ) ∧ L(A) = i<m L(B 2i ) \ L(B 2i+1 ) .
Since the relations in the first conjunct are semidecidable and all other relations in big parenthesis are computable, the relation

L(A) ∈ L ≤ (n) is semidecidable.
On the other hand, by Proposition 1 we have:

L(A) ∈ L ≤ (n) iff ∃u 0 , . . . , u n ∈ Σ * u 0 < • • • < u n ∧u 0 ∈ L(A)∧∀i < n(u i ∈ L(A) ↔ u i+1 ∈ L(A)) .
Since all relations in big parenthesis are computable, the relation

L(A) ∈ L ≤ (n) is semidecidable.
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 < ω, the levels L ≤ k (n) of the difference hierarchy over L ≤ k are decidable uniformly on k, n.

Proof. By Theorem 2, we have to show that the monotone WQOs ≤ k are computable uniformly in k. This was shown in [START_REF] Glaßer | The Boolean structure of dot-depth one[END_REF][START_REF] Selivanov | A logical approach to decidability of hierarchies of regular star-free languages[END_REF].

The above corollary is not new, earlier obtained in [START_REF] Glaßer | The Boolean structure of dot-depth one[END_REF][START_REF] Selivanov | A logical approach to decidability of hierarchies of regular star-free languages[END_REF]. Moreover, in those papers, the decidability of classes BC(L ≤ 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 ⊆ Σ * , the levels L ≤ I (n) of the difference hierarchy over L ≤ I are decidable uniformly on n.

Proof. By Theorem 2, we only have to show that the monotone WQO ≤ I is computable. This follows from an inspection of the proofs of Lemmas 4.6 and 4.7 in [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF]. We also note that, by Theorem 4.13 in [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF], it is decidable whether I is unavoidable. Therefore, we also have uniformity on I.

Extending monotone WQOs to infinite words

Here we discuss how to extend notions and results about monotone WQOs to infinite words, based on [START_REF] Ogawa | Well-quasi-orders and regular omega-languages[END_REF]. Fix a monotone WQO ≤ on Σ

* . A QO (Σ ω , ) is a monotone extension of (Σ * , ≤) if ∀i(u i ≤ v i ) implies u 1 u 2 u 3 • • • v 1 v 2 v 3 • • • .
We define important subclasses of monotone extensions. Definition 3 (Definition 2.1 in [START_REF] Ogawa | Well-quasi-orders and regular omega-languages[END_REF]). Let (Σ * ; ≤) be a monotone WQO.

1. A QO (Σ ω ; ) is a periodic extension of (Σ * ; ≤) if is a monotone extension of ≤, and for each α ∈ Σ ω there exist u, v ∈ Σ * with α uv ω , where = ∩ . The set of periodic extensions of ≤ is denoted by P E(≤). 2. A WQO (Σ ω ; ) is a regular extension of (Σ * ; ≤) if is a monotone extension of ≤, and for each α ∈ Σ ω the upward closed set ↑ α w.r.t. is a regular ω-language. The set of regular extensions of ≤ is denoted by RE(≤). Definition 4 (Definition 3.1 in [START_REF] Ogawa | Well-quasi-orders and regular omega-languages[END_REF]). A monotone extension (Σ ω ; ) of a monotone WQO (Σ * ; ≤), is a continuous extension, if (Σ ω ; ) is a WQO, and -For each u, v ∈ Σ * and α, β ∈ Σ ω , u ≤ v and α β imply uα vβ.

-Let u j , v j ∈ Σ * for each j and let

α i = v 1 • • • v i-1 u i • • • for each i and α ∞ = v 1 v 2 • • • . For β ∈ Σ ω , if u i ≤ v i and α i β for each i, then α ∞ β; and if u i ≥ v i and α i β for each i, then α ∞ β.
The set of continuous extensions of ≤ is denoted by CE(≤).

The following ω-versions of Theorem 1 are fundamental for this paper.

Theorem 4 (Theorem 2.2 and 3.2 in [START_REF] Ogawa | Well-quasi-orders and regular omega-languages[END_REF]). For any L ⊆ Σ ω 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 ≤, CE(≤) ⊆ RE(≤) = P E(≤) ⊆ W(Σ ω ).

Proof. Since Theorem 4 and its proof imply P E(≤) ∪ CE(≤) ⊆ RE(≤) and P E(≤) ⊆ W(Σ ω ), we show RE(≤) ⊆ P E(≤). Let be a regular extension of ≤. For every α ∈ Σ * , we have to find x, y ∈ Σ * such that α xy ω .

The upward closed set ↑ α=L (α) is a regular ω-language so there is a congruence ≈ of finite index on

Σ * that saturates ↑ α, i.e., ↑ α = U.V ω for ≈-classes U, V with V.V ⊆ V such that U.V ω ∩ U .V ω = φ implies U = U and V = V . Since ≤ is a WQO, there are finitely many (modulo ≤ ∩ ≥) minimal elements {x 1 , • • • , x l } and {y 1 , • • • , y k } of U and V , respectively. Since α ∈ U.V ω , let α = uv 1 v 2 • • • with u ∈ U and v i ∈ V .
Then, x i ≤ u for some i, and for all j , s > 0 there is j with

y j ≤ v j • • • v j +s (recall that V.V ⊆ V ). By Ramsey theorem, we have 1 ≤ j 1 < j 2 < • • • and j, j ≤ k such that y j ≤ v j1 • • • v j2-1 , v j2 • • • v j3-1 , • • • and y j ≤ v 1 • • • v j1-1 . For any ≈-class U with x i y j ∈ U , α ∈ U.V ω ∩ U .V ω implies U = U . Let x i ≤ x i y j . Since is a monotone extension of ≤, x i y ω j α. Since x i y ω j ∈ U.V ω ⊆↑ α, α x i y ω j .
Although we do not know whether CE(≤) = P E(≤) for each monotone WQO ≤ at the moment, we guess this holds in natural cases.

Lemma 2. For a monotone WQO (Σ * ; ≤), P E(≤) (resp. CE(≤)) is closed under intersection.

Proof. Let 1 , 2 ∈ P E(≤). Since = 1 ∩ 2 is a monotone extension of ≤, it remains to show that, for each α ∈ Σ ω , there are u, v ∈ Σ * with α uv ω . Let ≈ 1 and ≈ 2 be finite congruences saturating L 1 (α) and L 2 (α), respectively. Then, ≈ = ≈ 1 ∩ ≈ 2 is a finite congruence saturating L 1 (α) ∩ L 2 (α). By the proof of Theorem 5, there exist ≈-classes U, V with α ∈ U.V ω , and minimal elements u ∈ U and v ∈ V with α ≈ uv ω , which leads α uv ω .

For CE(≤), the statement is immediate from Definition 4.

Associate with any monotone WQO ≤, the class L ω ≤ of ω-languages which are upper sets w.r.t. some periodic extension of ≤, i.e., L ω ≤ = {L | ∈P E(≤)}.

Proposition 3. 1. → L is an embedding from (P E(≤); , , Σ ω ×Σ ω ) into the structure (Sub(R ω ); , , {∅, R ω }) of substructures of (R ω ; ∪, ∩, ∅, Σ ω ). 2. For any ∈P E(≤), every sequence of nonempty pairwise disjoint elements of L is finite.

L ω

≤ is closed under union and intersection. 4.

{L ω ≤ |≤ ∈M(Σ * )} = R ω .
The study of classes L ω ≤ becomes simpler if there is the smallest periodic extension of ≤, i.e., the smallest element of (P E(≤); ⊆). The reason is that in this case L ω ≤ = L . Note that, for a periodic (resp. continuous) extension , if a monotonic extension of ≤ holds ⊆ , 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 ≤ is a monotone ω 2 -WQO over Σ * . Lemma 3. Let ≤ be a monotone WQO over Σ * . Assume that a transfinite sequence

( λ ) λ∈Λ with λ ∈P E(≤) holds λ ⊇ λ if λ < λ . Let = λ∈Λ λ . Then, for each α ∈ Σ ω , there is a countable subset ∆ ⊆ Λ such that 1. For λ ∈ Λ, there is λ ∈ ∆ with λ < λ . 2. For λ ∈ Λ, there are ≈ λ -classes U λ , V λ saturating L λ (α) and minimal elements (w.r.t. λ ) u λ ∈ U λ , v λ ∈ V λ such that α ∈ U λ .V ω λ and u λ v ω λ λ α. 3. For λ, λ ∈ ∆ with λ < λ , u λ ≤ u λ and v λ ≤ v λ . 4. α is the upper limit of (u λ v ω λ ) λ∈∆ (w.r.t. ), i.e., lim λ∈∆ u λ v ω λ α.
Proof. From the proof of Theorem 5, for each α ∈ Σ ω and λ ∈ Λ, there exist

≈ λ -classes U λ , V λ saturating L λ (α) with α ∈ U λ .V ω λ and minimal elements u λ ∈ U λ , v λ ∈ V λ with α ≈ λ u λ v ω λ .
Since ≤ is a monotone WQO, there is a countable subset ∆ ⊆ Λ (by Ramsey-type argument [START_REF] Kříž | Ordinal types in Ramsey Theory and Well-Partial-Ordering Theory[END_REF]) such that u λ ≤ u λ , v λ ≤ v λ for λ, λ ∈ ∆ with λ < λ and (*) for each λ ∈ Λ, there is λ ∈ ∆ with λ < λ .

Since κ ∈ P E(≤) for each κ ∈ Λ, u λ v ω λ κ u λ v ω λ . Since α ≈ κ u κ v ω κ , u κ v ω κ κ α. Thus, for each λ, λ ∈ ∆ with λ < λ , u λ v ω λ λ α (by instantiating λ to κ).
With the condition (*), for each λ ∈ ∆, we have u λ v ω λ α. Assume that lim λ∈∆ u λ v ω λ α does not hold. Then, there exists β such that β ≺ α with u λ v ω λ β for each λ ∈ ∆. Since β ≺ α, there exists λ ∈ ∆ with β ≺ λ α, which contradicts to α λ u λ v ω λ .

Corollary 2. Let ≤ be a monotone ω 2 -WQO over Σ * and let { λ } λ∈Λ be a transfinite sequence of regular WQOs such that each λ is a monotone extension of ≤ with λ ⊇ λ for λ < λ . Then, = λ∈Λ λ is a WQO.

Proof. We borrow the notations in Lemma 3. For each α ∈ Σ ω , we set

Seq(α) = ((u λ , v λ )) λ∈∆ . Since ≤ × ≤ is an ω 2 -WQO on Σ * × Σ * , the embedding → on (Σ * × Σ * ) ω is a WQO [9]
. Then, for each infinite sequence α 1 , α 2 , • • • , there are i, j with i < j and Seq(α i ) → Seq(α j ), which implies α i α j by Lemma 3.

Note that the assumption of ω 2 -WQO frequently holds for typical WQOs, e.g., ≤ k [START_REF] Glaßer | The Boolean structure of dot-depth one[END_REF][START_REF] Selivanov | A logical approach to decidability of hierarchies of regular star-free languages[END_REF] and ≤ I [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF]. An exception is Rado's example [START_REF] Rado | Partial well-ordering of sets of vectors[END_REF]. Theorem 6. Let ≤ be a monotone ω 2 -WQO over Σ * . Then, CE(≤) has the smallest element (w.r.t. the set inclusion).

Proof. Note that a continuous extension of ≤ is a periodic extension by Theorem 5. For each descending chain ( λ ) λ∈Λ in CE(≤), there is a lower bound (actually, the lower limit λ∈Λ λ ) by Lemma 3. Since λ∈Λ λ is a WQO by Corollary 2, λ∈Λ λ ∈ CE(≤) from Definition 4. Therefore, there is a minimal element in CE(≤) by Zorn's Lemma. This is the smallest; otherwise, there exists an incomparable element in CE(≤). Since ∩ ⊂ , is a continuous extension of ≤ by Lemma 2, which contradicts to the minimality. 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 < ω, define the binary relation k on Σ ω as follows:

α k β if p k (α) = p k (β) and there is a k-embedding f : α → β. Here p k (α) = α[0, k) is the prefix of α of length k, and the k-embedding f is a monotone injective function on ω such that α[i, i + k] = β[f (i), f (i) + k]
for all i < ω. Note that the relation ≤ 0 is just the embedding of ω-words.

For any α ∈ Σ ω and n ≥ 1, let F n (α) (resp. F ∞ n (α)) be the set of u ∈ Σ n such that u is a factor of α (resp. u occurs in α as a factor infinitely often). Let F n (v) for v ∈ Σ + be defined similarly, F (v) = n F n (v), and F ∞ (α) = n F ∞ n (α). 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 (α) = ∅. 2. If x ∈ F ∞ n (α) and m > n then x is a factor of some y ∈ F ∞ m (α). 3. If x is a factor of y ∈ F ∞ n (α) then x ∈ F ∞ |x| (α). 4. If there is a k-embedding of α into β then F ∞ k+1 (α) ⊆ F ∞ k+1 (β)
. Define the binary relation R k on Σ ω by: αR k β iff there exist factorizations

α = u 0 u 1 • • • , β = v 0 v 1 • • • such that u i , v i ∈ Σ + and u i ≤ k v i for all i. Lemma 5. 1. R k ⊆ k . 2. For any α ∈ Σ ω there exist u, v ∈ Σ + such that αR k βR k α where β = uv ω . 3. αR k β iff α k β and F ∞ 2k (α) ∩ F ∞ 2k (β) = ∅. 4. If u ω k v ω then u ω R k γR k v ω for some γ ∈ Σ ω . Theorem 7. For any k < ω, k is the smallest periodic extension of ≤ k .
Proof. Obviously, k is a QO. By Lemma 5 [START_REF] Davey | Introduction to Lattices and Order[END_REF], k is a monotone extension of ≤ k . By Lemma 5(2), k is a periodic extension of ≤ k .

It remains to show that k ⊆ for every

∈ P E(≤ k ). Since is a monotone extension of ≤ k , R k ⊆ . Since is transitive, T C(R k ) ⊆ k , where T C(R k ) is the transitive closure of R k . Hence, it suffices to show that k ⊆ T C(R k ). Let α k β. By Lemma 5(2), αR k uv ω R k α and βR k u 1 v ω 1 R k β for some u, v, u 1 , v 1 . By Lemma 5(4), uv ω R k γR k u 1 v ω 1 for some γ. Thus, αT C(R k )β. Remark 1.
The analogue R of the relation R k may be defined for any monotone WQO ≤, and again we have T C(R) ⊆ for each ∈ P E(≤). Thus, if T C(R) is a periodic extension of ≤ then it is the smallest one. So in the search of the smallest periodic extension T C(R) is the first candidate. Theorem 8. For any finite unavoidable set I ⊆ Σ + , the relation I =R I is the smallest periodic extension of ≤ I .

Proof Sketch. The relation R I is the smallest monotone extension of ≤ 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 [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF] shows that the relation ≤ I is not only a WQO but also a BQO. The standard technique of BQO-theory applies to show that I is a BQO, hence also a WQO. By Theorem 5, it suffices to show that any upper set ↑ α w.r.t. I is regular.

↑ α 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 α. By Lemma 4.7 in [START_REF] Ehrenfeucht | On regularity of context-free languages[END_REF], the size of the stack is bounded by the smallest number k 0 such that any word in Σ ≥k0 has a factor from I. Thus, the pushdown Büchi automaton is reduced to a finite Büchi automaton.

Decidability of levels L (n)

Here we consider, in parallel to Section 4, decidability issues for the classes of ω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 ≤ be a monotone WQO. By a computable periodic extension of ≤ we mean a periodic extension of ≤ such that the 4-ary relation uv ω u 1 v ω 1 on Σ + is computable and there is a computable family {A u,v } u,v∈Σ + of Büchi automata such that L ω (A u,v ) = {α | uv ω α} for all u, v ∈ Σ + .

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

Theorem 9. For any computable periodic extension of a monotone WQO ≤, the levels L (n) of difference hierarchy over L are decidable uniformly on n.

We illustrate Theorem 9 by the monotone WQOs from Section 3. Note that by Theorem 7 we have

L k = L ω ≤ k and L I = L ω ≤ I .
Theorem 10. The levels L k (n) of the difference hierarchy over L k are decidable uniformly on k, n.

Proof. By Theorem 9, it suffices to show that k is a computable periodic extension of ≤ k uniformly on k. Since

uv ω k u 1 v ω 1 iff u ≤ k u 1 v |u| 1 and v ≤ k v |v| 1
for all k < ω and u, u 1 , v, v 1 ∈ Σ + , the relation uv ω k u 1 v ω 1 is computable uniformly on k.

It remains to find a computable family {A k,u,v } k<ω,u,v∈Σ + of Büchi automata such that L ω (A k,u,v ) = {α | uv ω k α} for all k < ω, u, v ∈ Σ + . From k, u, v it is straightforward to compute a first order sentence ϕ k,u,v of signature {<, Q a | a ∈ Σ} such that L ω ϕ k,u,v = {α | uv ω k α} where L ω ϕ is the set of ω-words that satisfy a given sentence ϕ (see [START_REF] Thomas | Automata on infinite objects[END_REF] 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<ω,u,v∈Σ + of Büchi automata such that L ω (A k,u,v ) = L ω ϕ k,u,v for all k < ω, u, v ∈ Σ + . Theorem 11. For every finite unavoidable set of words I, the levels L I (n) of the difference hierarchy over L I are decidable uniformly on n.

Proof. By Theorem 9, it suffices to show that k is a computable periodic extension of ≤ k . As above, for all u, u 1 , v, v 1 ∈ Σ + we have:

uv ω I u 1 v ω 1 iff u ≤ I u 1 v

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 [START_REF] Glasser | Efficient algorithms for membership in boolean hierarchies of regular languages[END_REF]. 5. Ideas and notions of this paper are related to those in the literature on (ordered) semigroups and ω-semigroups [START_REF] Pin | Positive varieties and infinite words[END_REF][START_REF] Perrin | Infinite Words[END_REF]. Further investigation of these relationships seems promising.

Corollary 3 .

 3 Let ≤ be a monotone ω 2 -WQO over Σ * . If CE(≤)=P E(≤), P E(≤) has the smallest element (w.r.t. the set inclusion).

|u| 1

 1 and v ≤ I v |v| 1 , hence the relation uv ω I u 1 v ω 1 is computable. If α = uv ω then the Büchi automaton A u,v constructed in the proof of Theorem 8 verifies the second condition of the computability of I .

This research was partially supported by Japan Society for the Promotion of Science (JSPS), Core-to-Core Program (A. Advanced Research Networks). The research of V. Selivanov was supported by Russian Science Foundation, project 18-11-00100.


Henning Fernau
email: fernau@uni-trier.de

Lakshmanan Kuppusamy

Descriptional Complexity of Matrix Simple Semi-Conditional Grammars

Keywords: simple semi-conditional grammars, matrix grammars, computational completeness, Geffert normal forms, descriptional complexity

Matrix grammars are one of the first approaches ever proposed in regulated rewriting, prescribing that rules have to be applied in a certain order. Typical descriptional complexity measures incorporate the number of nonterminals or the length, i.e., the number of rules per matrix. In simple semi-conditional (SSC) grammars, the derivations are controlled by a permitting string or by a forbidden string associated to each rule. The maximum length i of permitting strings and the maximum length j of forbidden strings are called the degree of such grammars. Matrix SSC grammars (MSSC) put matrix grammar control on SSC rules. We consider the computational completeness of MSSC grammars with degrees (2, 1), (2, 0) and (3, 0). The results are important in the following aspects. (i) With permitting strings alone, it is unknown if SSC grammars are computational complete, while MSSC grammars describe RE even with severe further restrictions on their descriptional complexity. (ii) Matrix grammars with appearance checking with three nonterminals are computationally complete; however, the length is unbounded. With our constructions for MSSC grammars, we can even bound the length.

Introduction

Matrix grammars (introduced by S. Ábrahám [START_REF] Ábrahám | Some questions of phrase-structure grammars[END_REF]) are regulated grammars in which rules are grouped into finite sequences called matrices. When a matrix is chosen to be applied, all rules in the sequence are applied in the given order. In semi-conditional (SC) grammars (introduced by Gh. Păun [START_REF] Gh | A variant of random context grammars: semi-conditional grammars[END_REF]), each rule is associated with two strings called the permitting string and the forbidden string. A rule can be applied to a sentential form w only if w contains the permitting string and does not contain the forbidden string as a subword. If both these control strings (permitting and forbidden) are absent in a rule, then the rule is called unconditional ; otherwise, the rule is termed conditional. The most interesting case is when the involved rewriting rules are context-free ; we will focus on this case in the following. Clearly, these are the rules which are responsible for a SC grammar to characterize the class of recursively enumerable languages, henceforth denoted RE [START_REF] Meduna | On semi-conditional grammars with productions having either forbidding or permitting conditions[END_REF][START_REF] Meduna | Reduction of simple semi-conditional grammars with respect to the number of conditional productions[END_REF][START_REF] Gy | On the descriptional complexity of some rewriting mechanisms regulated by context conditions[END_REF]. With semi-conditional grammars, two variants are of special interest: (i) simple semi-conditional grammars (denoted as SSCG) in which at most either the permitting string or the forbidden string is present for each rule, see [START_REF] Meduna | On semi-conditional grammars with productions having either forbidding or permitting conditions[END_REF]; (ii) permitting grammars in which the forbidden string is absent for every rule, see [START_REF] Zs | On the power of permitting semi-conditional grammars[END_REF]. Key observations in these domains include:

-Matrix grammars with appearance checking, having three nonterminals, are computationally complete, i.e., they characterize RE [START_REF] Fernau | Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars[END_REF]. However, the lengths of the matrices are unbounded. It is not clear how to restrict the length while still bounding the number of nonterminals. It is known that matrix grammars without appearance checking are not computationally complete; see [START_REF] Hauschildt | Petri net algorithms in the theory of matrix grammars[END_REF]. -The generative power of permitting grammars with no erasing rules is strictly included in the class of context-sensitive languages; refer to [START_REF] Zs | On the power of permitting semi-conditional grammars[END_REF]. It is open if permitting grammars with erasing context-free rules describe RE. -Results on the computational completeness of simple semi-conditional grammars are tabulated in Figure 1(a). It is unknown, for example, if five nonterminals or five conditional rules suffice to describe RE. -Matrix simple semi-conditional (MSSC) grammars, matrix controlled grammars with SSC rules (introduced in [START_REF] Meduna | Simple semi-conditional versions of matrix grammars with a reduced regulating mechanism[END_REF]) have been known to characterize RE while limiting several descriptional complexity measures at the same time. These devices are in the focus of our paper.

The results of the paper are tabulated in Figure 1(b), including results from [START_REF] Meduna | Simple semi-conditional versions of matrix grammars with a reduced regulating mechanism[END_REF].

Our results clearly improve on the previously published ones. The many results we obtained can be viewed as trade-off results between different measures of descriptional complexity. We highlight the record-holders of single measures by putting them in bold-face in the table.

Preliminaries and Definitions

In this paper, it is assumed that the reader is familiar with the fundamentals of language theory and mathematics in general. Let Σ * denote the free monoid generated by a finite set Σ called the alphabet under an operation termed concatenation. Any element of Σ * is called a word or string (over Σ), while the empty word λ is the unit of Σ * . Any subset of Σ * is called a language. A word v is a subword (or substring) of x ∈ Σ * if there are words u, w such that x = uvw. Let sub(x) ⊆ Σ * denote the set of all subwords of x ∈ Σ * . Clearly, sub(x) is a finite language. Given a word w ∈ Σ * , |w| represents the length of w. Recall that a type-0 grammar can be specified by a quadruple G = (N, T, S, P ), where N is the nonterminal alphabet, T is the terminal alphabet, S ∈ N is the start symbol and P is a finite set of re-write rules of the form x → y, with x, y ∈ (N ∪ T ) * . Type-0 grammars characterize the class RE of recursively enumerable languages. Rule x → y is context-free if x ∈ N .

Degree #NT #CR Ref.

(2, 1) 1. Summary of computational completeness results for SSC and MSSC grammars; #NT, #CR and #MAT denote the number of nonterminals, the number of conditional rules, and the number of conditional matrices, respectively. LEN gives an upper bound on the lengths of matrices.

Matrix (and) Semi-conditional Grammars

Matrix and Semi-conditional grammars have been introduced within the area of regulated rewriting [START_REF] Dassow | Regulated Rewriting in Formal Language Theory[END_REF][START_REF] Gh | A variant of random context grammars: semi-conditional grammars[END_REF], mostly to enhance the power of context-free grammars beyond context-free languages. Matrix control allows to express that some rules have to be applied in a certain order, while semi-conditional control attaches permitting and forbidden strings to rules that confine the applicability of these rules. In the special case of simple semi-conditional grammars [START_REF] Meduna | On semi-conditional grammars with productions having either forbidding or permitting conditions[END_REF], only either permitting or forbidden strings may be present.

A matrix simple semi-conditional grammar (MSSC grammar for short) combines simple semi-conditional grammars and matrix grammars [START_REF] Meduna | Simple semi-conditional versions of matrix grammars with a reduced regulating mechanism[END_REF]. Definition 1. An MSSC grammar is a quadruple G = (N, T, S, M ), where N, T and S have the same meaning as in a type-0 grammar and M is a finite set of sequences (called matrices) of the form

m = [(A 1 → x 1 , P 1 , F 1 ), . . . , (A → x , P , F )] , (1)
where Reconsider m from (1). Let α 0 , α ∈ (N ∪T ) * . Then, α 0 ⇒ m α holds if there are strings α 1 , . . . , α -1 ∈ (N ∪ T ) * such that, for all k = 1, . . . , , if P k = 0, then P k ∈ sub(α k-1 ), and if

≥ 1, A k ∈ N , x k ∈ (N ∪ T ) * , P k , F k ∈ (N ∪ T ) + ∪ {0} such that P k = 0 or F k = 0 for each 1 ≤ k ≤ .
F k = 0, then F k / ∈ sub(α k-1
), and furthermore,

α k-1 = α k-1 A k α k-1 and α k = α k-1 x k α k-1 . Define ⇒ G = m∈M ⇒ m . Now, L(G) = {w | S ⇒ * G w ∧ w ∈ T * } is the language described by G.
Observe that all conditions have to be met to successfully apply a matrix to a string; otherwise, the derivation does not succeed. More classical matrix grammars (without appearance checking) can be viewed as MSSC grammars where all matrices are unconditional. Likewise, simple semi-conditional grammars (abbreviated as SSC(G)) correspond to MSSC grammars where all matrices have length one. We now define six measures on the descriptional complexity of MSCC grammars that are crucial for our further studies.

Definition 2. An MSSC grammar G = (N, T, S, M ) is of size (i, j; n; c, p, l), if in every rule (A → x, α, β) of a matrix m ∈ M , we have -|α| ≤ i and |β| ≤ j, (the pair (i, j) is also called the degree of G); 4 -|N | ≤ n (an upper bound on the number of nonterminals); - m∈M c m ≤ c (bounding the total number of conditional rules in G); -|{m ∈ M | m > 1}| ≤ p (upper-bounding the number of multi-production matrices in G); -max{ m | m ∈ M } ≤ l (bounding the matrix lengths in G).
We denote by MSSC(i, j; n; c, p, l) the family of languages generated by MSSC grammars of size (i, j; n; c, p, l). If the forbidding conditions are absent in every rule of M , then the degree of the system is (i, 0) and is denoted as matrix permitting grammar (or MP grammar for short). For brevity, we simplify the notation (A → x, α, 0) to (A → x, α) and (A → x, 0, 0) to (A → x). For MP grammars, we abbreviate for the corresponding classes of languages MP(i; n; c, p, l) = MSSC(i, 0; n; c, p, l). If l = 1, then p = 0, and (as noticed above), we rather face SSC grammars, so that we could write MSSC(i, j; n; c, 0, 1) = SSC(i, j; n, c).

Geffert Normal Forms

In [START_REF] Geffert | Normal forms for phrase-structure grammars[END_REF], quite a number of normal forms for type-0 grammars have been derived. They all differ by the number of nonterminals that are used and also by the number of non-context-free rules. We will hence speak of (n, r)-GNF to refer to a Geffert normal form with n nonterminals and r non-context-free rules. However, all these normal forms characterize the class of recursively enumerable languages, or RE languages for short. The best known normal form is the (5, 2)-GNF with nonterminals S (start symbol) and A, B, C, D that uses context-free rules with S as its left-hand side in its first phase; after using the context-free rules, in a second phase non-context-free erasing rules AB → λ and CD → λ are applied to finally derive a string t ∈ T * . Hence, the derivation in a grammar in (5, 2)-GNF proceeds in two phases, where the first phase splits into two stages. In phase one, stage one, rules of the form S → uSa are used, with u ∈ {A, C} * , a ∈ T . In stage two, rules of the form S → uSv are used, with u ∈ {A, C} * and v ∈ {B, D} * . It is also shown in [START_REF] Geffert | How to generate languages using only two pairs of parentheses[END_REF] that any attempt to mix the applications of rules of these two types cannot yield to a terminal string in view of the chosen encodings. Also, rules of the form S → uv are available that prepare the transition into phase two, where (i.e., in phase two) the erasing non-context-free rules are used exclusively. The normal form variations we discuss next are always derived from (5, 2)-GNF by applying morphisms to all context-free rules, where in particular S → S maintains the start symbol, so that in particular the rules involving the start symbol keep up the same form as with (5, 2)-GNF, without further mentioning this below.

GNF with 4 nonterminals We now discuss another normal form of type-0 grammars due to Geffert [START_REF] Geffert | Normal forms for phrase-structure grammars[END_REF]. We then list some important properties of this normal form that are discussed and proved in [START_REF] Fernau | Improved descriptional complexity results for simple semi-conditional grammars[END_REF][START_REF] Fernau | New nonterminal complexity results for semi-conditional grammars[END_REF]. These follow from the constructions of the normal form and well-known properties of (5, 2)-GNF.

The normal form (4, 1)-GNF is obtained from (5, 2)-GNF normal form (using nonterminals S, A, B, C, D) by applying the morphism A → AB, B → C, C → A and D → BC to all context-free rules. Moreover, we add one non-context-free erasing rule ABC → λ. This means that the following properties hold: Proposition 1. [START_REF] Fernau | New nonterminal complexity results for semi-conditional grammars[END_REF] The following properties hold for (4, 1)-GNF grammars:

1. If S ⇒ * w, then w ∈ {A, AB} * {S, λ}{BC, C} * (T ({BC, C} ∪ T ) * ∪ {λ}). 2. If S ⇒ * w, then sub(w) ∩ ({BBB} ∪ {C}{B} * {A}) = ∅. 3. If S ⇒ * w, with w = w t, where w ∈ {A, AB} + {BC, C} + , t ∈ (T ({BC, C}∪ T ) * ∪{λ}), then w contains exactly one occurrence from {ABC, AC, ABBC} as a substring. We refer to this substring as the central part of w.

Only with ABC as central part, possibly w ⇒ * λ as intended in a derivation that yields a terminal string. If AC or ABBC occur as a central part of the string, then it will not derive to a terminal string. 4. If S ⇒ * w, with w = w t, where w ∈ {A, AB} + ∪ {BC, C} + and t ∈ (T ({BC, C} ∪ T ) * ∪ {λ}), then w does not derive any terminal string. 5. Again, the derivation proceeds in two phases, the first one is split into two stages. Only in phase two (where non-context-free erasing rules are applied), a central part will appear.

The normal form (4, 2)-GNF is obtained from (5, 2)-GNF (using nonterminals S, A, B, C, D) by applying the morphism A → CAA, B → BBC, C → CA and D → BC to all context-free rules. Moreover, the two non-contextfree erasing rules AB → λ and CC → λ are added. Then if S ⇒ * w, then w ∈ {CA, CAA} * {S, λ}{BC, BBC} * (T ({BC, BBC} ∪ T ) * ∪ {λ}).

Remark 1. Though the central part is either AB or CC, unwanted strings like AC or CB can appear in the center; the derivation is stuck in these cases. Similar properties as stated in the previous proposition can be derived for (4, 2)-GNF.

GNF with 3 nonterminals In [START_REF] Geffert | Normal forms for phrase-structure grammars[END_REF], it was also proved that every RE language is generated by a type-0 grammar with three nonterminals only. The contextfree rules of this (3, 1)-GNF normal form (where N = {S, A, B}) are obtained from (5, 2)-GNF by applying the morphism A → AB, B → BBA, C → ABB and D → BA. The only non-context-free rule is ABBBA → λ. It is sometimes more practical to work with the two non-context-free erasing rule BBB → λ and AA → λ instead, leading to a grammar in (3, 2)-GNF.

Remark 2. The central part for (3, 1)-GNF or (3, 2)-GNF is either BBB or AA, but unwanted strings like ABBA or ABBBBA are possible in the center.

Computational completeness of MSSC grammars

In the proofs, we are making use of several variations of Geffert normal form as discussed above, starting with (4, 1)-GNF. Proof. Let L ∈ RE be generated by a grammar in (4, 1)-GNF of the form G = (N, T, P ∪ {ABC → λ}, S) such that P contains only context-free productions and N = {S, A, B, C} (see Prop. 1). Next, we define the MSSC grammar G = (N , T, P ∪ P , S), where N = N ∪ {A , C } (assuming that {A , C } ∩ N = ∅), P contains (single-production) matrices of the form [(S → α, 0, 0)] whenever S → α ∈ P and P contains the following two (multi-production) matrices plus the (single-production) matrix m3 = [(C → λ, 0, A )]:

m1 = [(A → A , 0, C ), (C → C )] , m2 = [(B → λ, A B), (A → λ, A C )] .

We now show that L(G ) = L(G).

First, it is clear that context-free rules like S → α ∈ P can be easily simulated by single-production matrices of the form [(S → α, 0, 0)] and vice versa. In fact, it could be that m1 is applied in-between applying matrices [(S → α, 0, 0)], but then only matrices [(S → α, 0, 0)] can apply until switching to Phase two, where m2 might follow, which is discussed in detail next, assuming that m1 would have been applied last, not changing the resulting sentential form.

According to Prop. 1, then (after Phase one of the GNF grammar), ignoring boundary cases, we face a string of the form αξβt, where α ∈ {A, AB} * , ξ ∈ {ABC, AC, ABBC}, β ∈ {B, BC} * and t ∈ T ({B, BC} ∪ T ) * ∪ {λ}. Assume that ξ = ABC, i.e., we are still in the situation that (in case t ∈ T * ) αξβt might derive a terminal string in G. Applying ABC → λ in G, we could arrive at αβt. This can be simulated by αξβt ⇒ m1 αA BC βt ⇒ m2 αC βt ⇒ m3 αβt .

By induction, this shows that L(G) ⊆ L(G ).

We are now finishing the proof of the converse direction L(G) ⊇ L(G ) by explaining the decisive induction step, starting out with some αξβt (as above) that is derivable both in G and in G . If αξβt is the current sentential form in G with ξ = ABC, then clearly only m1 applies (due to the absence of primed symbols). This means that any occurrence of A (which must be in αξ) and any occurrence of C (from ξβt) is turned into the primed counterparts. Now, the presence of A and C prevents applying m1 or m3, forcing us into applying matrix m2 next. Now, the context checks become important. Both rules check for the presence of a certain symbol to the right of A . As both checked symbols are different and there is only one occurrence of A in the sentential form, the first rule in m2 must remove the occurrence of B to the right of A . Moreover, to the right of that occurrence of B, C must occur in the sentential form, which enforces that in fact the A occurring in ξ must have been turned into A when applying m1, and likewise the C occurring in ξ must have been turned into C before. In other words, we know that αABCβt ⇒ m1 αA BC βt ⇒ m2 αC βt. Due to the presence of C and the absence of A , m3 is the only applicable rule, leading to αβt as intended.

However, there are also situations to study where we know that within G, there will be no terminal string derivable at all, while this might happen within the simulated grammar G . Case 1. Consider the sentential form αACβt. Now, we could apply m1, turning one occurrence of A within αA into A and one occurrence of C within Cβt into C . Now, m2 is the only applicable rule. In order to apply the first rule in m2, B must have been sitting to the right of the A-occurrence that we have replaced when applying m1, but this means that now we find A within the part of the word previously called α, where no C-or C -occurrences are to be found, which would be necessary to apply the second rule of m2. In a sense, the A-occurrence in the central part AC serves as a barrier between the possible substrings AB within α and the C-ocurrences to match with. Hence, the derivation gets stuck. Case 2. Consider the sentential form αABBCβt. Now, again m1 is the only applicable matrix. Turning one occurrence of A within αA into A and one occurrence of C within Cβt into C . With a similar argument as in the previous case, one sees that not both rules of the only applicable matrix m2 can be applied in sequence. Here, the second B-occurrence in the central part ABBC serves as a barrier between the possible substrings AB within αAB and the C-ocurrences to match with. Case 3. Boundary cases. This concerns situations where there is no central part available at all. In particular, this means that we are facing sentential forms like αt or βt with α ∈ {A, AB} * , β ∈ {B, BC} * and t ∈ T ({B, BC}∪T ) * ∪{λ}. Now, either none of the matrices apply, or m1 might apply but then the derivation is stuck, because the permitting context A C in m2 cannot be met.

In summary, we have shown that whenever starting with a string w that is derivable both in G and in G, with G , we will be forced to produce a string that is also derivable in G, which proves that L(G) ⊇ L(G ), so that together with our previous considerations, we have shown that L(G) = L(G ) as claimed.

Notice that in the proof of the preceding theorem, we showed that after applying m2, we were forced to apply m3. So, the idea of simply appending m3 to m2 would work, giving a sort of trade-off result in terms of parameters. As the only purpose of the context check in the rule of m3 was to guarantee that m3 is not applied in another situation, we can furthermore omit context checks in the appended rule C → λ. Hence, otherwise following the same reasoning as before, the two (multi-production) matrices

m1 = [(A → A , 0, A ), (C → C )] , m2 = [(B → λ, A B), (A → λ, A C ), (C → λ)]
provide the simulation of the non-context-free rule ABC → λ of a type-0 grammar G in (4, 1)-GNF. This shows the following result. With a similar intuition, one could observe that an application of matrix m1 should be always followed by an application of m2. By tuning a bit on the roles of A and C , we propose the multi-production matrix

m = [(A → A , 0, A ), (C → C ), (B → λ, A B), (C → λ, A C )]
to work together with the one-production matrix [(A → λ, 0, 0)] in order to simulate the non-context-free rule ABC → λ. This can be worked out to prove: Theorem 3. MSSC(2, 1; 6; 3, 1, 4) = RE.

Working out further the idea of merging matrices of Theorem 1, as m1, m2 and m3 must be applied in order, one can observe that the forbidden context checks become obsolete, leading us to use the following (multi-production) matrix

m = [(A → A ), (C → C ), (B → λ, A B), (A → λ, A C ), (C → λ)]
to simulate the non-context-free rule ABC → λ. This idea yields the following. Theorem 4. MSSC(2, 0; 6; 2, 1, 5) = MP(2; 6; 2, 1, 5) = RE.

So far, we derived our results starting off from (4, 1)-GNF. We needed two more nonterminals in order to uniquely mark the boundaries of the central part of the sentential form. We are first trying to reduce the number of nonterminals at the expense of more conditional rules. To this end, we continue discussing our previous constructions, in particular, those based on the proof of Theorem 1.

Observe that an application of matrix m1 should be always followed by an application of m2. By merging the roles of A and C within #, we propose the multi-production matrix m = [(A → #, 0, #), (B → λ, #B, 0), (C → #, #C, 0), (# → λ, ##, 0)] to work together with the one-production matrix [(# → λ, 0, 0)] in order to simulate the non-context-free rule ABC → λ. This idea can be worked out to prove the following result. In order to aim at the use of fewer nonterminals (but possibly with more small-length matrices), we turn to another GNF, namely, to (4, 2)-GNF, which we are going to use in the following, trading off the number of conditional rules with avoiding forbidden strings. Proof. Let L ∈ RE be generated by a grammar in (4, 2)-GNF of the form G = (N, T, P ∪ {AB → λ, CC → λ}, S) such that P contains only contextfree productions and N = {S, A, B, C} (see Rem. 1). Next, we define the MSSC grammar G = (V , T, P ∪ P , S), where N = N ∪ {#} (assuming that # ∈ N ), P contains (single-production) matrices of the form [(S → α, 0, 0)] whenever S → α ∈ P and P contains the three (multi-production) matrices:

m1 = [(A → #, 0, #), (B → #)] , m2 = [(C → #, 0, #), (C → #)] , m3 = [(# → λ, ##, 0), (# → λ)] .
We can show L(G ) = L(G) by an inductive argument. Theorem 8. MSSC(2, 0; 5; 5, 3, 2) = MP(2; 5; 5, 3, 2) = RE.

Proof. Let L ∈ RE be generated by a grammar in (4, 2)-GNF of the form G = (N, T, P ∪ {AB → λ, CC → λ}, S) such that P contains only contextfree productions and N = {S, A, B, C} (see Rem. 1). Next, we define the MSSC grammar G = (N , T, P ∪ P , S), where N = N ∪ {#} (assuming that # / ∈ N ), P contains (single-production) matrices of the form [(S → α, 0)] whenever S → α ∈ P and P contains the three (multi-production) matrices:

m1 = [(A → #, AB), (B → #, #B)] m2 = [(C → #, CC), (C → #, #C)] m3 = [(# → λ, ##), (# → λ)].
We can show L(G ) = L(G) by an inductive argument.

Observe that in a correct simulation in Theorem 8, m1 must be followed by m3 and m2 must be followed by m3, as well. Hence, by appending m3 to m1 and to m2, we can obtain another computational completeness result with less but longer matrices, omitting the context conditions in the matrices m1 and m2 from the proof of Theorem 8. We are now going to follow the strategy again to merge some of the matrices. Also, we could be more parsimonous with checking contexts in this case. This leads us to the following matrices simulating the non-context-free rules:

m1 = [(B → #, 0), (B → #, 0), (B → λ, #B#), (# → λ, ##), (# → λ, 0)] , m2 = [(A → #, 0), (A → #, 0), (# → λ, ##), (# → λ, 0)] .
These two matrices with three conditional rules form the basis of the following. Alternatively, we could use more conditional rules and longer matrices (but smaller degrees) with the following matrix m1 replacing m1 above: m1

= [(B → #, 0), (B → #, #B), (# → #, B#), (# → #, A#), (B → λ, #A), (# → λ, ##), (# → λ, 0)].
Observe that if we have a string w ∈ {A, B, #} * with two #-occurrences and moreover {#A, #B, A#, B#} ⊆ sub(w), then either A#B and B#A or both A#A and B#B are substrings of w. Now if some B is deleted to produce w , so that afterwards ## is a substring of w , then only A#B#A ∈ sub(w) follows. This implies that BBB → λ is correctly simulated. Theorem 13. MSSC(2, 0; 4; 6, 2, 7) = MP(2; 4; 6, 2, 7) = RE.

Conclusions and discussions

We have tried to describe the frontier of computational completeness for MSSC grammars, obtaining quite a lot of trade-off results between the six descriptional complexity measures that we studied. The natural question is if our bounds can be further improved or if there are more trade-off results than already presented. We are currently working on the idea of re-using the start nonterminal within matrices.

Conversely, it would be also good to know which descriptional complexity restrictions lead to language classes smaller than RE. For instance, we believe that, irrespectively of the size of the other parameters, one nonterminal is insufficient to describe all of RE. This can be seen by inspecting the proof of the corresponding result for graph-controlled grammars in [START_REF] Fernau | Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars[END_REF]Theorem 15]. However, whether or not two or three nonterminals might suffice is open. Let us finally sketch the difficulties that we face when trying to use previous results on matrix languages in particular. In the proof of [START_REF] Fernau | Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars[END_REF]Corollary 6], showing that three nonterminals {A, B, C} suffice to generate any RE-language by using context-free matrix grammars with appearance checking, the appearance checks have been performed on rules X → C g (for some large number g encoding failure). Picking some nonterminal Y = X, this check could be simulated by an SSC rule (Y → Y, 0, X). This bounds the degree to (0, 1), as no permitting string checks are ever needed, and the nonterminals to three, yet, all other interesting parameters are unbounded. In particular, the matrix length is a classical parameter in matrix grammars, so that this observation might revive some interest in the descriptional complexity of more classical rewriting systems (as matrix grammars), as there are still open problems in that area. For instance, it is also still unknown if context-free matrix grammars with two nonterminals only describe RE.

Theorem 1 .

 1 MSSC(2, 1; 6; 4, 2, 2) = RE.

Theorem 2 .

 2 MSSC(2, 1; 6; 3, 2, 3) = RE.

Theorem 5 .

 5 MSSC(2, 1; 5; 4, 1, 4) = RE.Combining the ideas leading to the previous two theorems, we would again combine everything within one long matrix, now having the possibility to remove all forbidden context checks. This leads us to the following result, based onm = [(A → #), (B → λ, #B), (C → #, #C), (# → λ, ##), (# → λ)].Theorem 6. MSSC(2, 0; 5; 3, 1, 5) = MP(2; 5; 3, 1, 5) = RE.

Theorem 7 .

 7 MSSC(2, 1; 5; 3, 3, 2) = RE.

Theorem 11 .

 11 MSSC(3, 0; 4; 7, 4, 2) = MP(3; 4; 7, 4, 2) = RE.

Theorem 12 .

 12 MSSC(3, 0; 4; 3, 2, 5) = MP(3; 4; 3, 2, 5) = RE.

  The strings P k and F k above are called the permitting and forbidding conditions, respectively; 0 is a special symbol,0 ∈ N ∪ T . If P k = F k = 0, then rule (A → x k , P k , F k ) is called unconditional; otherwise, it is called conditional. Let c mdenote the number of conditional rules in matrix m from (1). We call matrix m conditional if c m ≥ 1 and unconditional if c m = 0. Moreover, m is called a multi-production matrix if ≥ 2 and is called a single-production matrix if = 1. Number m := is termed the length of m.

Here, the convention |0| = 0 applies.

Theorem 9. MSSC(2, 0; 5; 2, 2, 4) = MP(2; 5; 2, 2, 4) = RE.

In order to further lower the number of nonterminals that we have to use, we are moving on to GNFs that are more parsimonious in this respect, i.e., to (3, 2)-GNF or (equivalently) to (3, 1)-GNF. Proof. Let L ∈ RE be generated by a grammar in (3, 2)-GNF of the form G = (N, T, P ∪ {AA → λ, BBB → λ}, S) such that P contains only context-free productions and N = {S, A, B}. We define the MSSC grammar G = (N , T, P ∪ P , S), where N = N ∪ {#} (assuming that # / ∈ N ), P contains (singleproduction) matrices of the form [(S → α, 0)] whenever S → α ∈ P and P contains the following three matrices with five conditional rules:

The intended simulation of αABBBAβt ⇒ G αβt works as follows.

Again, we have to prove that L(G) = L(G ) by an inductive argument based on some case analysis.

Can we somehow shorten the matrices involved in the previous construction? What somehow comes to mind that the matrix dealing with A are stronger than those dealing with B in the sense of being more deterministic. As the nondeterminism observed with the matrix m1 dealing with BBB is not a crucial drawback, one could use m2 = [(A → #, AA), (A → ##, #A)] instead. Checking cases one sees that this does not create any additional problems indeed. We can also try to use ## instead of ### for marking purposes, which would allow us to shorten the length of m3 as well. Still, we have to split the matrix dealing with BBB, which is done as follows (at the cost of additional context checks):

We explain the necessity of these context checks by one example: If we omitted the BBB check in the first rule of m1, we might enter the matrix not having BBB as the central part, but without the BB# context of the second rule, it might be that we had replaced two occurrences of B's that are both not within BBB, so that we could re-apply m0, or possibly also directly apply m3. Also observe that with the proposed version, the shortcut of applying m3 immediately after m0 would lead to no continuation, because the central part would have been successfully destroyed, so that from now on no other matrix is applicable. Based on this construction, one can show (analogously to the previous case):


Gerhard Goos

Juris Hartmanis

Jan Van Leeuwen

David Hutchison

Takeo Kanade

Josef Kittler

Jon M Kleinberg

Friedemann Mattern

John C Mitchell

Moni Naor

C Pandu

Bernhard Steffen

Demetri Terzopoulos

Doug Tygar

Michal Hospodár

Galina Jirásková

Stavros Konstantinidis

Descriptional

Preface

This volume contains the papers presented at the 21st International Conference on Descriptional Complexity of Formal Systems (DCFS 2019) held in Košice, Slovakia, during July 17-19, 2019. It was jointly organized by the Working Group 1.02 on Descriptional Complexity of the International Federation for Information Processing (IFIP), by the Košice branch of the Mathematical Institute of the Slovak Academy of Sciences, and by the Slovak Artificial Intelligence Society.

The DCFS conference series is an international venue for the dissemination of new results related to all aspects of descriptional complexity, which is a field in computer science that deals with the costs of description of objects in various computational models, such as Turing machines, pushdown automata, finite automata, grammars, and others.

DCFS became an IFIP working conference in 2016, continuing the former Workshop on Descriptional Complexity of Formal Systems, which was a result of merging together two workshop series: Descriptional Complexity of Automata, Grammars and Related Structures (DCAGRS) and Formal Descriptions and Software Reliability (FDSR). DCAGRS was previously held in Magdeburg, Germany (1999), London, Ontario, Canada (2000), and Vienna, Austria (2001). FDSR was previously held in Paderborn, Germany (1998), Boca Raton, Florida, USA (1999), and San Jose, California, USA (2000). These workshops were merged in DCFS 2002 in London, Ontario, Canada, which is regarded as the 4th DCFS. Since 2003, DCFS has been successively held in Budapest, Hungary (2003), London, Ontario, Canada (2004), Como, Italy (2005), Las Cruces, New Mexico, USA (2006), Nový Smokovec, High Tatras, Slovakia (2007), Charlottetown, Prince Edward Island, Canada (2008), Magdeburg, Germany (2009), Saskatoon, Canada (2010), Giessen, Germany (2011), Braga, Portugal (2012), London, Ontario, Canada (2013), Turku, Finland (2014), Waterloo, Ontario, Canada (2015), Bucharest, Romania (2016), Milan, Italy (2017), and Halifax, Nova Scotia, Canada (2018).

The topics of this volume include: finite state transducers, quantum automata theory, state complexity, syntactic complexity, subword complexity, quasi-Polish spaces, tree automata, jumping automata, pushdown automata with constant height, input-driven pushdown automata, simple semi-conditional grammars, and monotone WQOs.

There were 25 submissions from 15 different countries: Algeria, Canada, Chile, Czech Republic, France, Germany, Hungary, India, Italy, Japan, Latvia, Russia, Slovakia, South Korea, and the USA. The submission, single-blind refereeing process, and the collating of the proceedings were supported by the EasyChair conference system. Each submission was reviewed by at least three, and on average 3.1, Program Committee members.

The committee selected 18 papers for presentation at the conference, and publication in this volume. The program also included four invited talks by Rudolf Freund, Jarkko Kari, Benedek Nagy, and Giovanni Pighizzini.

We would like to thank the Program Committee members and the external reviewers for their help in selecting the papers. We are also very grateful to all invited speakers, contributing authors, session chairs, and all the participants for their valuable contributions that helped DCFS 2019 to be a scientifically successful event in a collaborative and friendly atmosphere.

We are also grateful to the editorial staff at Springer, in particular Alfred Hofmann and Anna Kramer, for their guidance and help during the process of publishing this volume, and for supporting the event through publication in the LNCS series.

Last but not least, we would like to thank the conference sponsors for their financial support, and the local Organizing Committee: Peter Mlynárčik and Matúš Palmovský (social program), Ivana Krajňáková and Peter Gurský (financial issues), Viktor Olejár (IT support), Juraj Šebej (conference materials). Everything was always carefully checked and slightly criticized by Jozef Jirásek to whom our sincere gratitude goes as well.

We all are looking forward to the next DCFS in Vienna, Austria. July 2019 Michal Hospodár Galina Jirásková Stavros Konstantinidis vi Preface Organization Steering Committee Cezar Câmpeanu University of Prince Edward Island, Charlottetown, Canada Erzsébet Csuhaj-Varjú Eötvös Loránd University, Budapest, Hungary Helmut Jürgensen Western University, London, Canada Stavros Konstantinidis Saint Mary's University, Halifax, Canada Martin Kutrib (Chair) Justus Liebig University, Giessen, Germany Giovanni Pighizzini University of Milan, Italy Rogério Reis University of Porto, Portugal Program Committee Suna Bensch University of Umeå, Sweden Erszébet Csuhaj-Varjú Eötvös Loránd University, Budapest, Hungary Szilárd Zsolt Fazekas Akita University, Japan Viliam Geffert P.J. Šafárik University, Košice, Slovakia Yo-Sub Han Yonsei University, Seoul, South Korea Kazuo Iwama Kyoto University, Japan Galina Jirásková Slovak Academy of Sciences, Košice, Slovakia Christos Kapoutsis Carnegie Mellon University in Qatar, Doha, Qatar Ondřej Klíma Masaryk University, Brno, Czech Republic Stavros Konstantinidis Saint Mary's University, Halifax, Canada Martin Kutrib Justus Liebig University, Giessen, Germany Hing Leung New Mexico State University, Las Cruces, USA Christof Löding RWTH Aachen University, Germany Tomáš Masopust Czech Academy of Sciences, Brno, Czech Republic Ian McQuillan University of Saskatchewan, Saskatoon, Canada Carlo Merghetti University of Milan, Italy Nelma Moreira University of Porto, Portugal Alexander Okhotin St. Petersburg State University, Russia Luca Prigioniero University of Milan, Italy Narad Rampersad University of Winnipeg, Canada Kai Salomaa Queen's University, Kingston, Canada Juraj Šebej P.J. Šafárik University, Košice, Slovakia Jeffrey Shallit University of Waterloo, Canada Marek Szykuła University of Wrocław, Poland Matthias Wendlandt Justus Liebig University, Giessen, Germany Lynette van Zijl Stellenbosch University, South Africa