Antoine Amarilli

Charles

Antoine Amarilli Ltci

Charles Paperman

Topological Sorting with Regular Constraints

Keywords: 2012 ACM Subject Classification Mathematics of computing → Graph algorithms Topological sorting, shuffle problem, regular language

HAL is

Introduction

Many scheduling or ordering problems amount to computing a topological sort of a directed acyclic graph (DAG), i.e., a totally ordered sequence of the vertices that is compatible with the edge relation: when we enumerate a vertex, all its predecessors must have been enumerated first. However, in some settings, we need a topological sort satisfying additional constraints that cannot be expressed as edges. We formalize this problem as follows: the vertices of the DAG are labeled with some symbols from a finite alphabet A, and we want to find a topological sort that falls into a specific regular language. We call this the constrained topological sort problem, or CTS. For instance, if we fix the language K = ab * c, and consider the example DAGs of Figure 1, then G 1 and G 2 have a topological sort that falls in K.

CTS relates to many applications. For instance, many scheduling applications use a dependency graph [1] of tasks, and it is often useful to express other constraints, e.g., some tasks must be performed by specific workers and we should not assign more than p successive tasks to the same worker. We can express this as a CTS-problem: label each task by the worker which can perform it, and consider the target regular language K containing all words where the same symbol is not repeated more than p times. In concurrency applications, we may consider a program with multiple threads, and want to verify that there is no linearization of its instructions that exhibits some unsafe behavior, e.g., executing a read before a write. To search for such a linearization, we can label each instruction with its type, and consider CTS with a target language describing the behavior that we wish to detect. CTS can also be used in uncertain data management tasks, to reason about the possible answers of aggregate queries on uncertain ordered data [4]. It can also be equivalently phrased in the language of partial order theory: seeing the labeled DAG as a labeled partial order <, we ask if some linear extension achieves a word in K.

We thus believe that the CTS-problem is useful, and natural, but we are not aware of previous work studying it, except for a special case called the shuffle problem. This problem deals with the interleaving of strings, as studied, e.g., in concurrent programming languages [17,20], computational biology [16], and formal languages [9,7,25]. Specifically, we are given a tuple of strings, and we must decide if they have some interleaving that falls in the target language K. This problem was known to be NP-complete [18,[START_REF] Warmuth | On the complexity of iterated shuffle[END_REF]15] when the target language K is given as input (in addition to the tuple of strings), even when K consists of just one target string. To rephrase this shuffle problem in our context, we call constrained shuffle problem (CSh) the special case of CTS where we require input DAGs to be a union of directed path graphs (corresponding to the strings).

Our goal in this paper is to study the complexity of CTS and CSh. We assume that the target regular language K is fixed, and call CTS [K] and CSh[K] the corresponding problems, whose complexity is only a function of the input DAG (labeled on the alphabet A of K). Our central question is: for which regular languages K are the problems CTS [K] or CSh [K] tractable? More precisely, for each of these problems, we conjecture a dichotomy on K: the problem is either in NL or it is NP-complete. However, the tractability boundary is challenging to chart out, and we have not been able to prove these conjectures in full generality. In this paper, we present the results that we have obtained towards this end.

Paper structure. We formally define the CTS and CSh problems in Section 2 and state the conjecture. We then show the following results:

In Section 3, we present our hardness results. We recall the results of [START_REF] Warmuth | On the complexity of iterated shuffle[END_REF] on the shuffle problem, and present a general shuffle reduction technique to show hardness for more languages. We use it in particular to show that CSh[(ab) * ], hence CTS[(ab) * ], are NP-hard, and extend this to several other languages.

In Section 4, we present tractability results. We show that CTS[K], hence CSh [K], is in non-deterministic logspace (NL) when K is a union of monomial languages, i.e., of languages of the form A * 1 a 1 • • • A * n-1 a n-1 A * n , with the a i being letters and the A i being subalphabets. Such languages can be used for applications such as pattern matching, e.g., with the language A * uA * for a fixed pattern u ∈ A * . We also show tractability for other languages that are not of this form, e.g. (ab) * + A * aaA * and variants thereof, using different techniques such as Dilworth's theorem [8]. In Section 5, we use our hardness and tractability results to show a coarser dichotomy result. Specifically, we give an alternative phrasing of the CTS and CSh problems using semiautomata and DAGs with multi-letter labels: this amounts to closing the tractable languages under intersection, inverse morphism, complement, and quotients. In this phrasing, when the semiautomaton is counter-free, we can show that the problems are either in NL or NP-complete. This dichotomy is effective, i.e., the criterion on the semiautomaton is decidable, and it turns out to be the same for CTS and CSh. In Section 6, we focus on the constrained shuffle problem, and lift the counter-free assumption of the previous section. We show that CSh[K] is tractable when K is a group language or more generally a union of district group monomials. This tractability result is the main technical contribution of the paper, with a rather involved proof. It implies, e.g., that the following problem is in NL for any fixed finite group H: given g ∈ H and words w 1 , . . . , w n of elements of H, decide whether there is an interleaving of the w i which evaluates to g according to the group operation.

Problem Statement and Main Results

We give some preliminaries and define the two problems that we study. We fix a finite alphabet A, and call A * the set of all finite words on A. For w ∈ A * , we write |w| for the length of w, and write |w| a for the number of occurrences of a ∈ A in w. We denote the empty word by . A labeled DAG on the alphabet A, or A-DAG, is a triple G = (V, E, λ) where (V, E) is a directed acyclic graph with vertex set V = {1, . . . , n} and edge set E ⊆ V × V , and where λ : V → A is a function giving a label in A to each vertex in V . For u = v in V , we say that u is an ancestor of v if there is a directed path from u to v in G, we say that u is a descendant of v if v is an ancestor of u, and otherwise we call u and v incomparable. A topological sort of G is a bijective function σ from {1, . . . , n} to V such that, for all (u, v) ∈ E, we have σ -1 (u) < σ -1 (v). The word achieved by σ is λ(σ) := λ(σ( 1)

) • • • λ(σ(n)) ∈ A * .
The constrained topological sort problem CTS[K] for a fixed language K ⊆ A * (described, e.g., by a regular expression) is defined as follows: given an A-DAG G, determine if there is a topological sort σ of G such that λ(σ) ∈ K (in which case we say that σ achieves K).

We now define the constrained shuffle problem (CSh). Given two words u, v ∈ A * , the shuffle [START_REF] Warmuth | On the complexity of iterated shuffle[END_REF] of u and v, written u ¡ v, is the set of words that can be obtained by interleaving them. Formally, a word w ∈ A * is in u ¡ v iff there is a partition P Q of {1, . . . , |w|} such that w P = u and w Q = v, where w P denotes the sub-word of w where we keep the letters at positions in P , and likewise for w Q . The shuffle ¡(U) of a tuple of words U is defined by induction as follows: we set ¡() := { }, set ¡(u) := {u}, and set ¡(u 1 , . . . , u n , u n+1 ) := v∈¡(u1,...,un) v ¡ u n+1 . The constrained shuffle problem CSh [K] for a fixed language K ⊆ A * is defined as follows: given a tuple of words U , determine if K ∩¡(U ) is nonempty. Of course, CSh[K] is a special case of CTS[K]: we can code any tuple of words U as an A-DAG G U by coding each u ∈ U as a directed path graph v 1 → • • • → v |u| with λ(v i ) = u i for all 1 ≤ i ≤ |u|. Thus, we will equivalently see inputs to CSh as tuples of words (called strings in this context) or as A-DAGs that are unions of directed path graphs.

Example 2.1. The problem CTS[(ab) * ] on an input {a, b}-DAG G asks if G has a topological sort starting with an a, ending with a b, and alternating between elements of each label. The problem CSh[(aa + b) * ] on a tuple U of strings on {a, b} asks if there is an interleaving w ∈ ¡(U) such that all a * -factors in w are of even length (e.g., bbaabaaaa, but not baaabb).

In this work, we study the complexity of the problems CTS [K] and CSh[K] depending on the language K. Clearly we can always solve these problems by guessing a topological sort (or an interleaving), and verifying that it achieves a word in K. Hence, the complexity is always in NP K , that is, in non-deterministic PTIME with an oracle for the word problem of K, which we can call to test if an input word in is K: Proposition 2.2. For any language K, the problems CTS[K] and CSh [K] are in NP K .

In particular, the problems are in NP when the language K is regular, because the word problem for regular languages is in PTIME. We will study regular languages in this work. We believe that regular languages can be classified depending on the complexity of these problems, and make the following dichotomy conjecture: I C A L P 2 0 1 8 41:4 Topological Sorting with Regular Constraints Conjecture 2.3. For every regular language K, the problem CTS[K] is either in NL or NP-complete. Likewise, the problem CSh[K] is either in NL or NP-complete. Towards this conjecture, we determine in this paper the complexity of CTS and CSh for several languages and classes. We first show in the next section that these problems are hard for some languages such as (ab) * , and we then show tractability results in Section 4, and a coarser dichotomy result in Section 5 under an alternative phrasing of our problems.

Hardness Results

Our hardness results are based on the shuffle problem of formal language theory which asks, given a word w ∈ A * and a tuple U of words of A * , whether w ∈ ¡(U). This problem is known to be NP-hard already on the alphabet {a, b} (see [START_REF] Warmuth | On the complexity of iterated shuffle[END_REF]). The shuffle problem is different from CSh, because the target word of the shuffle problem is given as input, whereas the target regular language of CSh is fixed. However, the hardness of the shuffle problem directly implies the hardness of CSh, hence of CTS, for a well-chosen target language:

Proposition 3.1. Let K 0 := (a 1 a 2 + b 1 b 2 ) * . The problem CSh[K 0 ] is NP-hard.
Proof sketch. We can reduce a shuffle instance (w, U ) to the instance I := w 1 ∪ U 2 for CSh[K 0 ], where w 1 is w but adding the subscript 1 to all labels, and U 2 is defined analogously. A topological sort of I achieving K 0 must then alternate between w 1 and U 2 , and enumerate letters with the same label (up to the subscript), witnessing that w ∈ ¡(U).

In this section, we will refine this approach to show hardness for more languages. We first recall another initial hardness result from [START_REF] Warmuth | On the complexity of iterated shuffle[END_REF]. We then introduce a general shuffle reduction technique to show the hardness of languages by reducing from other hard languages. Last, we show that CTS and CSh are hard for the language (ab) * and for other languages.

Initial hard family.

To bootstrap the hardness results of [START_REF] Warmuth | On the complexity of iterated shuffle[END_REF] on the shuffle problem (on input words) to our CSh-problem (on fixed languages), we generalize the definition of CSh to a regular language family K, i.e., a (generally infinite) family of regular languages, each of which is described as a regular expression. The CSh-problem for K, written CSh[K], asks, given a regular expression K ∈ K and a set of strings U , whether K ∩ ¡(U) is nonempty. In other words, we no longer fix one single target language but a family K of target languages, and the input chooses one target language from the family K. The following is then shown in [START_REF] Warmuth | On the complexity of iterated shuffle[END_REF] by reducing from UNARY-3-PARTITION [12]:

Lemma 3.2. ([31], Lemma 3.2) Let K := {(a i b i ) * | i ∈ N}. Then CSh[K] is NP-hard.
Shuffle reduction. Our goal in this section is to show the hardness of CTS and CSh for more languages, but we do not wish to prove hardness for every language from scratch. Instead, we will introduce a general tool called the shuffle reduction that allows us to leverage the hardness of a language K to show that another language K is also hard. Specifically, if a language K shuffle-reduces to a language K , this will imply that there is a PTIME reduction from CTS[K] to CTS[K ], and from CSh[K] to CSh [K ].

The intuition for the shuffle reduction is as follows: to reduce from K to K , given an input A-DAG G, we build an A-DAG G formed of G plus an additional directed path labeled by a word w. Thus, any topological sort σ of G must be the interleaving of w and of a topological sort σ of G. Now, if we require that σ achieves K , the presence of w can impose specific conditions on σ. Intuitively, if w is sufficiently long and "far away" from all words of K , then σ must "repair" w to a word of K by inserting symbols from G, so the insertions performed by σ may need to be in a specific order, i.e., σ may be forced to achieve a word of K. This means that solving CTS [K ] on G allows us to solve CTS [K] on G. This intuition is illustrated on Figure 2: to achieve a word of K := (ab) * on the DAG G , a topological sort must enumerate elements from G to insert them at the appropriate positions in w, achieving a word of K := (ba) * b. We call filter sequence a family of words like w that allow us to reduce any CTS[K]-instance to CTS [K ]. Formally: Definition 3.3 (Filter sequence). Let K and K be languages on an alphabet A. A filter sequence for K and K is an infinite sequence (f n ) of words of A * having the following property: for every n ∈ N, for every word

v ∈ A * such that |v| = n, we have v ∈ K iff (v ¡ f n ) ∩ K = ∅.
In Figure 2, we can choose f 5 := w when defining a filter sequence for (ba) * b and (ab) * : indeed, if we interleave w with any DAG G of 5 vertices, then a topological sort σ of G achieves K iff some interleaving σ of σ with w achieves K . We can now define our reduction: Definition 3.4 (Shuffle reduction). We say that a language K shuffle-reduces to a language K if there is a filter sequence (f n ) for K and K such that the function i → f i is computable in PTIME (where i is given in unary).

We say that a regular language family K shuffle-reduces to K if each K does, and if we can compute in PTIME the function (K, i) → f K i , which maps a regular expression K of K and an integer i in unary to the i-th word in a filter sequence (f K n ) for K and K .

Theorem 3.5. For any regular language family K and language K , if K shuffle-reduces to K then we can reduce in PTIME from CTS[K] to CTS[K ], and from CSh

[K] to CSh[K ].
Hardness for (ab) * . We now use the shuffle reduction and the language family of Lemma 3.2 to show the hardness of (ab) * . This will be instrumental for our coarser dichotomy in Section 5:

Theorem 3.6. The problem CSh[(ab) * ] (hence CTS[(ab) * ]) is NP-hard.
Proof sketch. We shuffle-reduce from the language family K of Lemma 3.2: for the language K B = (a B b B ) * of K, we define the filter sequence for words of length 2Bn by f B 2Bn := (b B a B ab) n . This ensures that, when interleaving f B 2Bn with a word v of length 2Bn to achieve a word of (ab) * , we must use v to insert in f B 2Bn the letters written in bold: ((ab) B (ab) B ab) n . This can be done iff v = (a B b B ) n , i.e., iff v ∈ K B . We conclude by Theorem 3.5.

Other hard languages.

From the hardness of (ab) * , we can use the shuffle reduction to show hardness for many other languages. For instance, we can show hardness for any language u * , where u ∈ A * is a word with two different letters:

I
b > 0 for a = b in A. Then CSh[u * ] (hence CTS[u * ]) is NP-hard.
Proof sketch. We shuffle-reduce from (ab) * with the filter sequence f 2n := (uu -a uu -b u) n , where u -a (resp. u -b ) is u but removing one occurrence of a (resp. of b). If a word v with |v| = 2n has an interleaving w with f 2n that falls in u * , then in w we must intuitively insert one a from v in each u -a and one b from v in each u -b , so that v = (ab) n . To formalize this, we first rotate u to ensure that its first and last letters are different. We then observe that, as w is in u * , any factor w of length |u| of w must be such that |w | a = |u| a and |w | b = |u| b . We then consider factors of w of length |u| centered on the u -a and u -b in f 2n : we argue that in w we must have inserted at least one a in or around each u -a , and at least one b in or around each u -b , otherwise these factors do not have enough a's and enough b's.

We can also use the shuffle reduction to show hardness for other languages, e.g., (aa + bb) * :

Proposition 3.8. Let L := (aa + bb) * . The problem CSh[L] (hence CTS[L]) is NP-hard.
Proof sketch. We do again a shuffle reduction from (ab) * , with the filter sequence f 2n = (ab) n .

If a word v with |v| = 2n is such that v ¡ f 2n intersects (aa + bb) * nontrivially, it must intuitively insert a's and b's in f 2n alternatively, so it must be (ab) n . Note that a similar proof would also show hardness for the language (a i + b j ) * for any choice of i, j ≥ 2.

We show a last result that does not use the shuffle reduction but an easy consideration on the number of letter occurrences. This result will be useful in Section 5:

Proposition 3.9. The problem CSh[(ab + b) * ] (hence CTS[(ab + b) * ]) is NP-hard.
Proof. We describe an easy PTIME reduction from CSh[(ab) * ] to CSh[(ab + b) * ]. Given an instance I, check if the number of a-labeled and b-labeled vertices is the same, and fail if it is not. Otherwise, then I achieves a word of (ab + b) * iff it achieves one of (ab) * , because we must enumerate one a-labeled vertex with each b-labeled vertex.

We believe that the shuffle reduction applies to many other languages, though we do not know how to characterize them. In particular, we believe that the following could be shown with the shuffle reduction, generalizing all the above hardness results except Proposition 3.8: Conjecture 3.10. Let F be a finite language such that, for some letter a ∈ A, the language F contains no power of a but contains a word which contains a. Then CSh[F * ] is NP-hard.

Tractability Results

Having shown hardness for several languages, we now present our tractability results. We will also rely on some of these results to show our coarser dichotomy result in the next section.

Closure under union.

The first observation on tractable languages is that they are closed under union, as follows (recalling the definition of CTS and CSh for language families):

Lemma 4.1. For any finite family of languages K, there is a logspace reduction from

CTS[ K] to CTS[K], and likewise from CSh[ K] to CSh[K].
Proof. To solve a problem for the language K on an input instance I, simply enumerate the languages K ∈ K, and solve the problem on I for each K . Clearly I is a positive instance of the problem for K iff I is a positive instance of the problem for one of the K .

Corollary 4.2. For any finite family of languages

K, if CTS[K ] is in NL for each K ∈ K, then so is CTS[ K]. The same is true of the CSh-problem.
Clearly, tractability is also preserved under the reverse operator, i.e., reversing the order of words in a language; however tractable languages are not closed under many usual operators, as we will show in Section 5. Still, closure under union will often be useful in the sequel.

Monomials.

We will now show that CTS is tractable for an important family of languages (and unions of such languages): the monomial languages. Having fixed the alphabet A, a monomial is a language of the form

A * 1 a 1 A * 2 a 2 • • • a n A * n+1 with a i ∈ A and A i ⊆ A for all i.
In particular, we may have A i = ∅ so that A * i = : hence, for every word u ∈ A * , the language A * uA * is a monomial language, which intuitively tests whether a word contains the pattern u. Several decidable algebraic and logical characterizations of these languages are known; in particular, unions of monomials are exactly the languages that are definable in the first-order logic fragment Σ 2 [<] of formulas with quantifier prefix ∃ * ∀ * , and it is decidable to check if a regular language is in this class [23,21]. We show: Theorem 4.3. For any monomial language K, the problem

CTS[K] is in NL. Proof sketch. Let K be A * 1 a 1 A * 2 a 2 • • • A * n a n A * n+1 .
We can first guess in NL the vertices v 1 , . . . , v n to which the a 1 , . . . , a n are mapped, so all that remains is to check, for each such guess, whether we can match the remaining vertices to the A i . We proceed by induction on n. The base case of n = 0 (i.e., K = A * 1 ) is trivial. For the induction step, using the fact that NL = co-NL (see [14,[START_REF] Szelepcsényi | The method of forced enumeration for nondeterministic automata[END_REF]), we check that the descendants of the last element v n are all in A * n+1 , and then we compute the set S of vertices that must be enumerated before v n : they are the ancestors of the v i , and the ancestors of any vertex labeled by a letter in A \ A n+1 . We then use the induction hypothesis to check in NL whether S has a topological sort that achieves a word in

A * 1 a 1 . . . A * n-1 a n-1 A * n .
Tractability based on width. While unions of monomials are a natural class, it turns out that they do not cover all tractable languages. In particular, we can show:

Proposition 4.4. Let A := {a, b} and K := (ab

) * + A * aaA * . The problem CTS[K] (hence CSh[K]) is in NL.
This result is not covered by Theorem 4.3, because we can show that K cannot be expressed as a union of monomials (see Appendix C.1); and the proof technique is different.

Proof. Let G be an input

A-DAG. We first check in NL if G contains two incomparable vertices v 1 = v 2 such that λ(v 1 ) = λ(v 2 ) = a.
If yes, we conclude that G is a positive instance, as we can clearly achieve K by enumerating v 1 and v 2 contiguously.

If there are no two such vertices, we check in NL if there are two comparable a-labeled vertices v 1 = v 2 that can be enumerated contiguously, i.e., there is an edge v 1 → v 2 but no vertex w that is between v 1 and v 2 , i.e., is a descendant of v 1 and an ancestor of v 2 . If there are two such vertices v 1 and v 2 , we conclude again that G is a positive instance.

Otherwise, our first test implies that G induces a total order on the a-labeled vertices, and our second test implies that any two consecutive a-labeled vertices in this order must have at least one b-labeled vertex between them. This ensures that no topological sort achieves A * aaA * , so it suffices to test whether one can achieve (ab) * . Clearly this is the case iff all consecutive pairs of a-labeled vertices have exactly one b-labeled vertex between them, and there is exactly one additional b-labeled vertex that can be enumerated after the last a-labeled vertex. We can test this in NL, which concludes the proof.

Intuitively, the language of Proposition 4.4 is tractable because it is easy to solve unless the input instance has a very restricted structure, namely, all a's are comparable. We do not know whether this result generalizes to (ab) * + A * a i A * for i > 2. However, following the intuition of this proof, we can show the tractability of a similar kind of regular languages: Proposition 4.5. Let A := {a, b}, let K be a regular language, let i ∈ N, and let

K := K + A * (a i + b i )A * . The problem CTS[K] (hence CSh[K]) is in NL.
As in Proposition 4.4, CTS is trivial for the languages in this proposition unless the input A-DAG G has a restricted shape. Here, the requirement is on the width of G, i.e., the maximal cardinality of a subset of pairwise incomparable vertices (called an antichain), so we can show Proposition 4.5 by distinguishing two cases depending on the width of G:

Proof sketch. We test in NL whether the input A-DAG G contains an antichain C of size 2i: if it does, then at least i vertices in C must have the same label, and we can enumerate them in succession to achieve A * a i A * or A * b i A * , so G is a positive instance. Otherwise, G has width < 2i, and Dilworth's theorem [8] implies that its elements can be partitioned into chains, so that CTS can be solved in NL following a dynamic algorithm on them.

Other tractable case. We close the section with another example of a regular language which is tractable for the CSh-problem for what appears to be a unrelated reason. This is in contrast to (aa + bb) * , for which we showed intractability (Proposition 3.8). We do not know the complexity of the CTS-problem for (aa + b) * , or the complexity for either problem of languages of the form (a i + b) * for i > 2.

Proof sketch. We show that the existence of a suitable topological sort can be rephrased to an NL-testable equivalent condition, namely, there is no string in the input instance whose number of odd "blocks" of a-labeled elements dominates the total number of a-labeled elements available in the other strings. If the condition fails, then we easily establish that no suitable topological sort can be constructed: indeed, eliminating each odd block of a's in the dominating string requires one a from the other strings. If the condition holds, we can simplify the input strings and show that a greedy algorithm can find a topological sort by picking pairs of a's in the two current heaviest strings.

A Coarser Dichotomy Theorem

In the two previous sections, we have established some intractability and tractability results about the constrained topological sort and constrained shuffle problems for various languages. Remember that our end goal would be to characterize the tractable and intractable languages, and show a dichotomy (Conjecture 2.3). This is difficult, and one reason is that the class of tractable languages is not "well-behaved": while it is closed under the union operator (Corollary 4.2), it is is not closed under intersection, complement, and other common operations. This makes it difficult to study tractable languages using algebraic language theory [22].

Proposition 5.1. We have the following counterexamples to closure: Quotient. There exists a word u ∈ A * and a regular language K such that

CSh[K] is in NL but CSh u -1 K is NP-hard.
Intersection. There exists two regular languages K 1 and K 2 such that CTS[K 1 ] and

CTS[K 2 ] are both in PTIME but CSh[K 1 ∩ K 2 ] is NP-hard Complement.
There exists a regular language K such that

CTS[K] is in NL, but CSh[A * \ K] is NP-hard.
Inverse of morphism. There exists a regular language K and morphism ϕ such that

CTS[K] is in NL but CSh ϕ -1 (K) is NP-hard.
The three last results of this proposition also apply to the constrained topological sort problem, but the first one does not, and in fact CTS-tractable languages are closed under quotients. This observation implies that there are regular languages K such that CSh[K] is tractable but CTS[K] is NP-hard; one concrete example is K := b * A * + aaA * + (ab) * (see Appendix D.1). We sketch the proof of Proposition 5.1: Proof sketch. For each operation, we use (ab) * as our NP-hard language (by Theorem 3.6).

For quotient, we take K := bA * + aaA * + (ab) * , and u := ab. We have u -1 K = (ab) * , but CSh[K] is in NL because any shuffle instance with more than one string satisfies K.

For intersection, we take K 1 := (ab) * ( + bA * ) and K 2 := (ab) * ( + aaA * ). We have

K 1 ∩ K 2 = (ab) * , but CSh[K 1 ] and CSh[K 2 ]
are in PTIME using an ad-hoc greedy algorithm.

For complement, we take

K := bA * ∪ A * a ∪ A * aaA * ∪ A * bbA * .
As K is a union of monomials, we know by Theorem 4.3 that CTS[K] is in NL, but we have

A * \ K = (ab) * .
For inverse of morphism, we take A := {a, b} and K := (ab) * + A * (a 3 + b 3 )A * . We know that CTS[K] is in PTIME by Proposition 4.5. Now, defining ϕ : A * → A * by ϕ(a) := aba and ϕ(b) := bab, we have ϕ -1 (K) = (ab) * because no word in the image of ϕ has three identical consecutive symbols.

Proposition 5.1 suggests that tractable languages would be easier to study algebraically if we ensured that they were closed under all these operations, i.e., if they formed a variety [22]. In this section, we enforce this by moving to an alternative phrasing of the CTS and CSh problems. This allows us to leverage algebraic techniques and show a dichotomy theorem in this alternative phrasing, under an additional counter-free assumption. We first present the alternative phrasing, and then present the additional assumption and our dichotomy result.

Alternative phrasing. The first change in our alternative phrasing is that the input DAG G will now be an A * -DAG, i.e., a DAG labeled with words of A * rather than letters of A. As before, a topological sort σ of G achieves a word λ(σ) ∈ A * obtained by concatenating the λ-images of the vertices of G in the order of σ: but vertex labels are now "atomic" words whose letters cannot be interleaved with anything else. The multi-letter CTS and CSh problems are the variants defined with A * -DAGs; intuitively, this ensures that tractable languages are closed under inverse morphisms.

The second change is that we will not fix one single target language, but a semiautomaton [13], i.e., an automaton where initial and final states are not specified. Formally, a semiautomaton is a tuple (Q, A, δ) where Q is the set of states, A is the alphabet, and δ : Q × A → Q is the transition function; we extend δ to words as usual by setting δ(q, ) := q and δ(q, u 1 • • • u n+1 ) := δ(δ(q, u 1 ), u 2 • • • u n+1 ). We will fix the target semiautomaton, and the initial and final states will be given in the input instance (in addition to the DAG). This enforces closure under quotients (by choosing the initial and final states) and complement (by toggling the final states). Further, to impose closure under intersection, the input instance will specify a set of pairs of initial-final states, with a logical AND over them. The question is to determine whether the input DAG achieves a word accepted by all the corresponding automata; and this enforces closure under intersection.

I C A L P 2 0 1 8 41:10

Topological Sorting with Regular Constraints

We can now summarize the formal definition of our problem variants. The multi-letter CTS-problem for a fixed semiautomaton S = (Q, A, δ) takes as input an A * -DAG and a set {(i 1 , F 1 ), . . . , (i k , F k )} of initial-final state pairs, where i j ∈ Q and F j ⊆ Q for all 1 ≤ j ≤ k. The input is accepted if there is a topological sort σ of G such that, for all 1 ≤ j ≤ k, the word λ(σ) is accepted by the automaton (Q, A, δ, i j , F j ), i.e., δ(i j , λ(σ)) ∈ F j . The multi-letter CSh-problem for a fixed semiautomaton is defined in the same way, imposing that the input A * -DAG is a union of directed path graphs.

Dichotomy result. Our dichotomy will apply to the multi-letter CTS and CSh problem for semiautomata. However, we will need to make an additional assumption, namely, that the semiautomaton is counter-free. This assumption means that our dichotomy will only apply to a well-known subset of regular languages, namely, the star-free languages, that are better understood algebraically; it excludes in particular the tricky case of group languages that we will study separately in Section 6. Formally, a semiautomaton is counter-free if, for every state q and word u ∈ A * , if δ(q, u n ) = q for some n > 1, then we have δ(q, u) = q. Under the counter-free assumption, we can prove the following dichotomy, using our hardness and tractability results in Sections 3 and 4: Theorem 5.2. Let S be a counter-free semiautomaton. Then the multi-letter CSh-problem and CTS-problem for S are either both in NL, or both NP-complete. The dichotomy is effective: given S, it is PSPACE-complete to decide which case applies.

We conclude the section by introducing some technical tools used for this result and for Section 6, and by giving a proof sketch. The criterion of the dichotomy on S is phrased in terms of the transition monoid of S, which we now define (see, e.g., [22] for details). Remember that a monoid is a set that has an associative binary operation and a neutral element. The transition monoid T (S) of a semiautomaton S = (Q, A, δ) is the set of functions f : Q → Q that are "achieved" by S in the following sense: there is a word u ∈ A * such that δ(q, u) = f (q) for all q ∈ Q. In particular, the neutral element is the identity function, which is achieved by taking u := ; and the binary operation on T (S) is function composition, which is associative. Note that the transition monoid is finite and can be computed from S.

We assumed that S is counter-free, and this is equivalent [19] to saying that T (S) is in the class A of aperiodic finite monoids (formally defined by the equation x ω+1 = x ω where ω is the idempotent power [22] of the monoid). Within A, our dichotomy criterion on T (S) is based on a certain subclass of A, called DA (see [START_REF] Tesson | Diamonds are forever: the variety DA. Semigroups, algorithms, automata and languages[END_REF]): S is tractable iff T (S) is in DA, and it is PSPACE-complete [START_REF] Thérien | Over words, two variables are as powerful as one quantifier alternation[END_REF] to test whether this holds (using the formal definition of DA by the equation (xy) ω x(xy) ω = (xy) ω ). We can now sketch the proof of Theorem 5.2: Proof sketch. We first show that if T (S) is in DA then the multi-letter CTS and CSh problems for S are in NL. For this, we rely on one characterization of DA (from [START_REF] Tesson | Diamonds are forever: the variety DA. Semigroups, algorithms, automata and languages[END_REF]): if T (S) is in DA then the regular languages recognized by S (for any set of initial-final states) are unions of unambiguous monomials, in particular they are unions of monomials, so we have tractability by Corollary 4.2 and Theorem 4.3.

For the converse direction, we use a second characterization of DA (from [START_REF] Tesson | The computing power of programs over finite monoids[END_REF]): if T (S) is not in DA then there is a choice of initial-final state pairs for which S computes a language K whose inverse image by some morphism is either (ab) * or (ab + b) * . We know that these languages are intractable (Theorem 3.6 and Proposition 3.9) so we conclude by showing a PTIME reduction from one of these two languages: this is possible in our alternative problem phrasing, in particular using the multi-letter labels to invert the morphism. Lifting the Counter-Free Assumption for CSh Our dichotomy theorem in the previous section (Theorem 5.2) was shown for an alternative phrasing of our problems (with semiautomata and multi-letter inputs), and made the additional assumption that the input semiautomaton is counter-free. In this section, we study how to lift the counter-free assumption. In exchange for this, we restrict our study to the constrained shuffle problem (CSh) rather than CTS.

To extend Theorem 5.2 for the CSh-problem, we will again classify the semiautomata S based on their transition monoid T (S). However, instead of DA, we will use the two classes DO and DS introduced in [START_REF] Schützenberger | Sur le produit de concaténation non ambigu[END_REF] (formally DO is defined by the equation ( xy) ω (yx) ω (xy) ω = (xy) ω and DS by the equation ((xy) ω (yx) ω (xy) ω ) ω = (xy) ω for ω the idempotent power). Both DO and DS are supersets of DA, specifically we have DA ⊆ DO ⊆ DS, and we can test in PSPACE in S whether T (S) is in each of these classes [START_REF] Thérien | Over words, two variables are as powerful as one quantifier alternation[END_REF]. Our main result is then:

Theorem 6.1. Let S be a semiautomaton. If T (S) is in DO, then the multi-letter CSh-problem for S is in NL. If T (S) is not in DS, then it is NP-complete.
This result generalizes Theorem 5.2 for the CSh-problem, because both DO and DS collapse to DA for aperiodic monoids (see [START_REF] Schützenberger | Sur le produit de concaténation non ambigu[END_REF] and [2, Chapter 8]); formally, DO ∩ A = DS ∩ A = DA. However, DO covers more languages than DA: the main technical challenge to prove Theorem 6.1 is to show that CSh is tractable for these languages. One important example are the group languages over A: these are the regular languages recognized, for some choice of initial-final state pairs, by a semiautomaton S over A such that T (S) is a group. A more general example are district group monomials, which are the languages of the form

K 1 a 1 • • • K n a n K n+1
where, for all i, we have a i ∈ A and K i is a group language over some alphabet A i ⊆ A. Note that district group monomials are more expressive than the group monomials defined in earlier work [24] (which set A i := A for all i), and they also generalize the monomials that we studied in Section 4 (any A * i is trivially a group language over A i , even though it is not a group language over A). In fact, to prove Theorem 6.1, what we need is to generalize Theorem 4.3 (for CSh) from monomials to district group monomials: Theorem 6.2. Let K be a district group monomial. Then CSh[K] is in NL.

Note that this theorem, like Theorem 4.3, applies to the original phrasing of CSh, not the alternative phrasing with semiautomata and multi-letter DAGs. Thus, Theorem 6.2 implies that the original CSh-problem is tractable for many languages that we had not covered previously, e.g., (ab * a + b) * c(ba * b + a) * , the language testing whether there is one c preceded by an even number of a and followed by an even number of b. The proof of Theorem 6.2 is our main technical achievement, and we sketch it below (see Appendix E for details):

Proof sketch. We focus on the simpler case of a group language, for a finite group H. The problem can be rephrased directly in terms of H: given a tuple I of strings over H and a target element g ∈ H, determine if there is an interleaving of I that evaluates to g under the group operation. Our approach partitions H into the rare elements H rare , that occur in a constant number of strings, and the frequent elements H freq , that occur in sufficiently many strings. For the frequent elements, we can build a large antichain C from the strings where they occur, with each element of H freq occuring many times in C. Now, as topological sorts can choose any order on C, they can intuitively achieve all elements of the subgroup H freq generated by H freq , except that they cannot change "commutative information", e.g., the parity of the number of elements. We formalize the notion of "commutative information" using relational morphisms, and prove an antichain lemma that captures our intuition that all elements of H freq with the right commutative information can be achieved.

For the rare elements, we can simply follow a dynamic algorithm on the constantly many strings where they occur. However, we must account for the possibility of inserting elements of H freq from the other strings, and we must show that it suffices to do constantly many insertions, so that it was sufficient to impose a constant lower bound on |C|. We formalize this as an insertion lemma, which we prove using Ramsey's theorem.

We close the section by commenting on the two main limitations of Theorem 6.1. The first limitation is that it is not a dichotomy: it does not cover the semiautomata with transition monoid in DS \ DO. We do not know if the corresponding languages are tractable or not; we have not identified intractable cases, but we can show tractability, e.g., for (a + b + a + b + ) * , the language of words with an even number of subfactors of the form a + b + .

Proposition 6.3. Let K = (a + b + a + b + ) * . Then CSh[K] is in NL.
However, it would be difficult to show tractability for all of DS, because DS is still poorly understood in algebraic language theory. For instance, characterizing the languages with a syntactic monoid in DS has been open for over 20 years [2, Open problem 14, page 442].

The second limitation of Theorems 6.1 and 6.2 is that they only apply to CSh. New problems arise with CTS: for instance, an {a, b}-DAG G may contain large antichains C a and C b of a-labeled and b-labeled vertices, and yet contain no antichain with many a-labeled and b-labeled vertices (e.g., if G is the series composition of C a and C b ). The missing proof ingredient seems to be an analogue of Dilworth's theorem for labeled DAGs (see also [START_REF]concatenation of its elements is in τ (Com µ (S freq ))[END_REF]).

Conclusion and Open Problems

We have studied the complexity of two problems, constrained topological sort (CTS) and constrained shuffle (CSh): fixing a regular language K, given a labeled DAG (for CTS) or a tuple of strings (for CSh), we ask if the input DAG has a topological sort achieving K. We have shown tractability and intractability for several regular languages using a variety of techniques. These results yield a coarser dichotomy (Theorem 5.2) in an alternate problem phrasing that imposes some closure assumptions.

Our work leaves the main dichotomy conjecture open (Conjecture 2.3). Even in the alternate problem phrasing of Theorem 5.2, our dichotomy only covers counter-free semiautomata: the restriction is lifted in Section 6 but only for CSh, and with a gap between tractability and intractability. In the original phrasing, there are many concrete languages that we do not understand: Does Proposition 4.4 extend to (ab) * + A * a i A * for i > 2? Does Proposition 4.6 extend to (a i + b) * for i > 2, or to CTS rather than CSh? Can we show Conjecture 3.10?

Another direction would be to connect CSh and CTS to the framework of constraint satisfaction problems (CSP) [10], which studies the complexity of homomorphism problems for fixed "constraints" (right-hand-side of the homomorphism). If this were possible, it could lead to a better understanding of our tractable and hard cases. However, CTS does not seem easy to rephrase in CSP terms: topological sorts and regular language constraints seems hard to express in terms of homomorphisms, even in extensions such as temporal CSPs [5,6].

One last question would be to investigate CTS and CSh for non-regular languages. The simplest example is the Dyck language, which appears to be NP-hard for CTS (at least in the multi-letter setting), but tractable for CSh, via a connection to scheduling; see [11], problem SS7. More generally, CTS and CSh could be studied, e.g., for context-free languages, where the complexity landscape may be equally enigmatic.

A Proofs for Section 2 (Problem Statement and Main Results)

Proposition 2.2. For any language K, the problems CTS[K] and CSh[K] are in NP K .

Proof. As explained in the main text, we guess a permutation σ of the input vertices, check that it respects the order constraints, and use the oracle for the word problem to check that the word achieved by σ is in K.

B

Let K 0 := (a 1 a 2 + b 1 b 2 ) * . The problem CSh[K 0 ] is NP-hard.
Proof. We construct the CSh-instance I in PTIME from the input instance to the shuffle problem as explained in the proof sketch, and argue for correctness in more detail. It is clear that, to achieve K 0 , a topological sort σ of I must enumerate alternatively a letter with subscript 1 and a letter with subscript 2, so it must enumerate alternatively from w 1 and from U 2 , and the definition of K 0 ensures that the two letters in w and U corresponding to the enumerated letters in w 1 and U 2 must have the same label in {a, b}. Hence, considering the restriction σ of σ to U 2 , the interleaving of U that corresponds to σ witnesses that

w ∈ ¡(U). Conversely, if w ∈ ¡(U), starting from a witnessing topological sort σ of U 2 , it is clear
that we can construct a topological sort σ of I that achieves K 0 , by enumerating the elements of w 1 alternatively with the elements of U 2 according to σ . This shows correctness and concludes the proof.

B.2 Proof of Lemma 3.2: Initial Hard Family

Lemma 3.2. ([WH84], Lemma 3.2) Let K := {(a i b i ) * | i ∈ N}. Then CSh[K] is NP-hard.
Proof. For completeness, we summarize here the proof of [WH84]: see the statement and proof of Lemma 3.2 in [WH84] for details. The reduction is from UNARY-3-PARTITION:

given a tuple E of 3m positive integers written in unary, such that B := 1 m 1≤i≤3m n i is an integer, and such that B/4 < e < B/2 for each e ∈ E, decide whether E can be partitioned into m triples, with each triple summing to B. This problem is NP-hard [GJ75]. Given a UNARY-3-PARTITION instance (E, B), we create a CSh instance I by writing each integer n as the string a n b n , and we choose the target language K in K to be (a B b B ) * , which is clearly a PTIME reduction. Clearly, if (E, B) can be partitioned in triples summing to B, then we can define a topological sort of I by enumerating, for each triple, the B copies of the a's in that triple, and then the b's, achieving a word of K. Conversely, any topological sort achieving a word of K must start by enumerating B copies of a's followed by the same number of b's, and the only way to free sufficiently many b's is to enumerate completely the initial a segments of some strings: we know that the number of such strings is exactly 3 by our assumption that B/4 < e < B/2 for all e ∈ E. Hence, by applying this argument repeatedly, a topological sort of I achieving K must define a solution to (E, B), completing the proof of the reduction.

B.3 Proof of Theorem 3.5: Shuffle Reduction

Theorem 3.5. For any regular language family K and language K , if K shuffle-reduces to K then we can reduce in PTIME from CTS[K] to CTS[K ], and from CSh

[K] to CSh[K ].
Of course, note that this result also applies to languages and not just to language families, because we can always take K to be a singleton language family containing only one single language.

Proof. We show the result for the CSh-problem; the result for the CTS-problem is shown in exactly the same way. Fix the family K and language K . Let K be the input language of K, and let I be an input instance of the CSh-problem for K. Let (f K n ) be the filter sequence for K and K . Letting n := |I|, let us call I the instance of the CSh-problem for K that contains I and a separate string labeled with f K n : by our computability hypothesis on (f K n ), this is computable in PTIME. We now argue that I is a positive instance to the CSh-problem for K iff I is a positive instance to the CSh-problem for K. Indeed, assuming that there is a word v of K achieved by a topological sort σ of I, we have |v| = n by definition, so by definition of (f

K n ) we have (v ¡ f K n ) ∩ K = ∅. Hence, let v be an element of this set. It is in v ¡ f K n ,
so it can be obtained as a topological sort of I by shuffling f K n with σ, and it is in K so it witnesses that I is a positive instance to the CSh-problem for K .

Conversely, if there is a topological sort σ of I achieving a word v ∈ K , then σ defines a topological sort σ of I achieving a word v such that v ∈ v ¡ f n . As we have |v| = n by definition, and v witnesses that v ¡ f n is non-empty, we must have v ∈ K, so that σ witnesses that I is a positive instance to the CSh-problem for K. This establishes correctness, and concludes the proof.

Note that, for simplicity, we have shown Theorem 3.5 for PTIME reductions. This is because we only use the shuffle reduction in this paper to prove NP-hardness results. However, Theorem 3.5 result can also be shown for NL reductions if we further assume that the filter sequences can be computed in logspace, i.e., the function mapping the unary representation of n to the word f n is computable by a logspace transducer. Proof. Let K be the family of regular languages defined in Lemma 3.2. We define a filter sequence (f B n ) for each such language K B = (a B b B ) * for B ∈ N. We first explain how to define the filter sequence for word lengths of the form 2Bn, for which there are words in K B having the specified length. For such lengths, we define f B 2Bn := (b B a B ab) n . For other word lengths n ∈ N, for which there are no words in K B , we define f B n := a n +1 : this ensures that we can never obtain a word of K B by interleaving n symbols with f B n , which is correct. The filter sequence is clearly computable in PTIME. So we only have to show that, for all n ∈ N, the word f B 2Bn is a filter sequence for word length 2Bn. To do so, fix n ∈ N, and consider a word v of length 2Bn in K B . For the forward direction, if v is (a B b B ) n which is the only word of K B of length 2Bn, then we can interleave v with f B 2Bn to form a word of (ab) * by inserting the letters in bold: ((ab) B (ab) B ab) n .

B.4 Proof of

Conversely, for the backward direction, we are forced to insert at least these letters. More precisely, considering an interleaving of f B 2Bn with a word v that achieves a word w of (ab) * , we know that, in each of the n occurrences of b B a B ab in v, each of the B first b's must be preceded by an a in w (so B insertions of a), then each of the B occurrences of a must be followed by a b in w (so B insertions of b). As we have |v| = 2Bn, we must perform these insertions in this order, and as they do not overlap, this completely specifies v: so we know

that (v ¡ f B 2Bn ) ∩ (ab) * is non-empty iff v = (a B b B ) n . This shows that f B
2Bn is indeed a filter sequence, which establishes that CSh[(ab) * ] is NP-hard thanks to Theorem 3.5 and Lemma 3.2.

B.5 Hardness Proofs for Other Languages

Proposition 3.7. Let u ∈ A * such that |u| a > 0 and |u| b > 0 for a = b in A. Then CSh[u * ] (hence CTS[u * ]) is NP-hard.
Proof. Fix u ∈ A * and the two witnessing letters a and b. We first make a straightforward preliminary observation: for any word w of u * and factor z of w such that |z| = |u|, we must have |z| a = |u| a and |z| b = |u| b . Indeed, when running w through the obvious deterministic finite automaton for u * , we know that, while z is read, the total number of a-transitions and b-transitions will be |u| a and |u| b .

We now write u = xy such that the last letter of x is different from the first letter of y; by assumption on u, this is always possible. We can now write u * = + x(u ) * y, where u := yx; this ensures that the first and last letters of u are different.

We now show that (ab) * shuffle-reduces to u * , by constructing a filter sequence (f n ). To this end, we let u -a be a word obtained by removing some a in u , and u -b be defined likewise. Now, to define the filter sequence, we first deal with odd numbers as in the proof of Proposition 3.8, by defining f 2n+1 for n ∈ N as something that can never be in u * even when inserting 2n + 1 arbitrary symbols, e.g., f 2n+1 := a (2n+1)×|u|+1 , which is clearly computable in PTIME.

For even numbers, we define f 2n := x(u u -a u u -b u ) n y for n ∈ N: this is clearly computable in PTIME. We show that this is a filter sequence by picking n ∈ N and letting v be a word such that |v| = 2n. If v = (ab) n , we can clearly interleave v and f 2n to obtain a word of u * by inserting each a of v in u -a and each b of v in u -b . Conversely, for an interleaving of any word with f 2n to yield a word of u * , we know that we must at least insert one a in or around each u -a , and one b in or around each u -b . Specifically, consider a word v and consider a candidate interleaving w ∈ (v ¡ f 2n ) ∩ u * and assume by contradiction that there is a factor u -a of f 2n such that w did not insert any a from v within this factor or adjacently to this factor (the case of u -b -factors is symmetric). Now, consider the factor w of w that contains this factor u -a , the neighboring letter from the beginning or end of u where we take one such letter which is not a (which is always possible by hypothesis on u ), and all inserted elements (which by hypothesis are all b's). The number of a's in the factor w is |u -a | a , which is |u| a -1, but |w | ≥ |u|, so, by our preliminary observation, this is impossible because we had assumed that w ∈ u * . Hence, indeed, we must insert one a in u -a or adjacently to it, and likewise for the u -b : these insertions are distinct, and they use up all letters of v, so for f 2n ¡ v to intersect u * nontrivially, the only possibility is that v = (ab) n . This shows that (f n ) is indeed a filter sequence, and allows us to conclude by Theorem 3.5 and Theorem 3.6. Proof. We show a shuffle reduction from K := (ab) * to K := (aa + bb) * , which concludes by Theorem 3.5 and Theorem 3.6. We first define the filter sequence for even values of n, and show correctness for them; then we explain how to handle the case of odd n.

I C A L P 2 0 1 8

41:18 Topological Sorting with Regular Constraints

For all even n ∈ N we set f n := (ab) n , which is clearly computable in PTIME. Let us now show correctness. For the forward direction, it is clear that for every even n ∈ N, the only word of length n of (ab) * is (ab) n/2 and we can interleave it with f n to form (aabb) n/2 .

For the backwards direction, fix n ∈ N, take v ∈ A * such that |v| = n, and assume that (v ¡ f n ) ∩ K contains some word w. For each 1 ≤ i ≤ n, consider the position where the i-th letter of f n occurs in w, and call ϕ i the maximal factor of w which contains the i-th letter of f n and consists only of occurrences of the same letter (i.e., is of the form a * or b * ). By definition, these factors must occur in w in the order ϕ 1 ≤ • • • ≤ ϕ n . Now, as any two consecutive letters of f n are different, we know that the ϕ i are disjoint (so we have

ϕ 1 < • • • < ϕ n )
and that there is only one letter in each ϕ i that was taken from f n , namely, the i-th letter of f n : the others were inserted from v. Further, by definition of K , the ϕ i must all be of even length. This means that f 1 contains at least one inserted a, that f 2 contains at least one inserted b, etc. As we have |v| = n, this completely specifies v, specifically as n is even we must have v = (ab) n/2 . This is a word of (ab) * , which concludes the backward direction and establishes correctness for even n.

There remains to define the filter sequence for odd numbers, i.e., 2n + 1 with n ∈ N. As there are no words of odd length in (ab) * , it suffices to define f 2n+1 to be something that can never be in K even when inserting n arbitrary symbols. For instance, we can take f 2n+1 := (ab) 2n+2 , which has the required property by a variant of the proof for the backward direction above. This concludes the proof of the proposition.

C

Proofs for Section 4 (Tractability Results)

C.1 Additional Explanations About (ab) * + A * aaA *

Let A := {a, b}. We first substantiate a claim made in the main text, namely:

Claim C.1. The regular language K = (ab) * + A * aaA * cannot be expressed as a union of monomials.

We have already mentioned that it is decidable to check if a given (regular) language can be expressed as a union of monomials. We explain how this process can be applied to K to prove the claim:

Proof. It is shown in Theorem 8.7 of [PW97] that a regular language K can be expressed as a union of monomials (equivalently called "languages of level 3/2" in the statement of that result) if and only if the ordered syntactic monoid of K satisfies the profinite identity: For all x, y ∈ A * having same content,

x ω ≥ x ω yx ω (1)
where "x and y having the same content" means that, for each letter a ∈ A, we have |x| a > 0 iff |y| a > 0, and where ω denotes the idempotent power in the free profinite monoid (see [PW97] for precise definitions). This can be rephrased in more elementary terms using the notion of syntactic order ≤ K induced by K, which can be thought of as an ordered version of the Myhill-Nerode congruence. Formally, the order ≤ K is defined as follows: for all x, y ∈ A * , we have x ≤ K y iff for all u, v ∈ A * , uyv ∈ K implies uxv ∈ K. Equation 1 can then equivalently be rephrased to the following condition: for all words x, y ∈ A * with same content, and for all integers n such that

x n ≤ K x 2n ≤ K x n , we have x n ≥ K x n yx n .
For our choice of language K, we can show that this rephrased condition does not hold, by taking x := ab and y := bab and n := 1. Indeed, we have (ab) 1 ≤ K (ab) 2 ≤ K (ab) 1 , but the right-hand-side of the implication is wrong: we have x 1 = ab in K, so we can take u = v = in the definition of the syntactic order, however we then have x 1 yx 1 = abbabab which is not in K, so we have shown that x n ≥ K x n yx n .

C.2 Proof of Theorem 4.3: Tractability for Monomials

Theorem 4.3. For any monomial language K, the problem CTS[K] is in NL.

Proof. Let

K be A * 1 a 1 A * 2 a 2 • • • A * n a n A * n+1 .
First, we can guess in NL the vertices v 1 , . . . , v n of G = (V, E, λ) to which the a 1 , . . . , a n are associated, and verify that indeed we have λ(v i ) = a i for all 1 ≤ i ≤ n. Hence, up to making such a guess and relabeling the vertices, we can assume without loss of generality what we call the fresh pivot condition on the input A-DAG: for each a i in our target language, there is exactly one v i in the input instance such that λ(v i ) = a i .

We now prove by induction on n that, for any monomial

K = A * 1 a 1 • • • A * n a n A * n+1
, given an input A-DAG satisfying the fresh pivot condition, we can decide in NL whether A has a topological sort satisfying K.

The base case of n = 0 is trivial because K is of the form A * 1 : we simply check if all element labels are in A * 1 . For the induction step on n + 1, let E,λ) be the input A-DAG satisfying the fresh pivot condition, and let v 1 , . . . , v n+1 be the uniquely defined vertices matched to a 1 , . . . , a n+1 . We define the sub-A-DAG G to be the restriction of G on the following vertex set V : the ancestors of the v 1 , . . . , v n , including v 1 , . . . , v n ; the ancestors of v n+1 except v n+1 itself; for each w incomparable to v n+1 such that λ(w) / ∈ A n+2 , the ancestors of w (including itself). We now claim the following:

K = A * 1 a 1 A * 2 • • • a n+1 A * n+2 and K = A * 1 a 1 A * 2 • • • a n A * n+1 . Let G = (V,
Claim. G is a positive instance to K iff all descendants z of v n+1 are such that λ(z) ∈ A n+2 and G is a positive instance to K .

Note that G is always computable in NL, and the condition on the descendants of v n+1 can be checked in co-NL, hence in NL by the Sze88]. Hence, once this claim is proved, we have an NL algorithm for CTS[K] by running the NL algorithm on the descendants of v n+1 and running the algorithm given by the induction hypothesis on G , which has been implicitly computed in NL.

What remains is to prove the claim. For the backward direction, if the condition of the claim is respected, then we build the topological sort σ of G satisfying K by concatenating the topological sort σ of G satisfying K which exists by assumption, the vertex v n+1 which achieves a n+1 , and any topological sort of G \ (G ∪ {v n+1 }). We must argue that this a topological sort. Indeed, observe first that the condition of the claim and the fresh pivot condition ensures that no descendant of v n+1 has a label in a 1 , . . . , a n , i.e,. v n+1 is not an ancestor of any v i ; in particular v n+1 is not in V . However, by definition of G , all ancestors of v n+1 are in V . So we know that we can indeed concatenate σ , v n+1 , and a topological sort of the remaining elements of G, and the result σ is indeed a topological sort of G. We now argue that σ achieves K: this is because σ achieves K , v n+1 achieves a n+1 , and by assumption all remaining vertices are either descendants of v n+1 so their label is in A n+2 , or they are incomparable to v n+1 so their label must be in A n+2 (they would be in G otherwise). Thus, σ is a topological sort of G that achieves K, establishing the backward implication.

I C A L P 2 0 1 8

41:20 Topological Sorting with Regular Constraints

For the forward direction, consider a topological sort σ of G that achieves K. Thanks to the fresh pivot condition, we know that v n+1 is matched to a n+1 . Let U be the elements enumerated before v n+1 in σ, and let σ be the topological sort induced by σ on U : we know that σ satisfies K . We now claim that V ⊆ U . Indeed, first, by the fresh pivot condition, σ must enumerate a i for all 1 ≤ i ≤ n, so v 1 , . . . , v n and their ancestors must be in V . Second, as σ enumerates v n+1 just after σ , we know that σ must enumerate all ancestors of v n+1 except v n+1 itself. Third, assuming by way of contradiction that V does not contain an ancestor of a vertex w incomparable to v n+1 such that λ(w) / ∈ A n+2 , we would have that V does not contain w either, and as w is incomparable to v n+1 it is different from v n+1 so w must be enumerated after v n+1 by σ, but λ(w) / ∈ A n+2 , which is impossible because we are matching elements to A * n+2 after v n+1 . So indeed V ⊆ U . Further, as V contains the v 1 , . . . , v n , we know that the topological sort σ of V defined as the restriction of σ to V also achieves K : intuitively, given a topological sort that achieves K , we can remove any elements except those matched to the a i and the result still achieves K . So σ witnesses that G is a positive instance to K . Now, as σ must enumerate all descendants z of v n+1 after v n+1 which achieves a n+1 , we know that they must be such that λ(z) ∈ A n+2 , so we have shown the condition and established the forward implication.

We have shown our claim, which concludes the proof of Theorem 4.3.

C.3 Proof of Proposition 4.5: Tractability Based on Width

Proposition 4.5. Let A := {a, b}, let K be a regular language, let i ∈ N, and let

K := K + A * (a i + b i )A * . The problem CTS[K] (hence CSh[K]) is in NL.
To show this result, we will need several preliminary definitions. Recall from the main text that an antichain is a set S ⊆ V of vertices which are pairwise incomparable, and the width of a DAG is the size of its largest antichain. The main claim is then the following: Proposition C.2. For any regular language K, the problem CTS[K] can be solved in space O(k log n), where k is the width of the input DAG and n is its total size. The same bound holds for CSh [K] where k is the number of input strings.

We note that a similar task was already known to be in PTIME by [ABDS17, Theorem 17], but showing the space bound given here will introduce several additional technicalities. From Proposition C.2, it is easy to show Proposition 4.5:

Proof of Proposition 4.5. We follow the proof sketch: we test in NL if the input DAG contains an antichain of size 2i. If it does, as explained in the sketch, the DAG is a positive instance. So the only remaining case is when the input DAG has width ≤ 2i, so we can conclude by Proposition C.2. So all that remains is to show Proposition C.2, which we do in the rest of Appendix C.3. The high-level idea of the proof is to use Dilworth's theorem [Dil50], which essentially shows that the width of any DAG G is equal to the minimal cardinality of a chain partition of G, i.e., a partition of G into disjoint chains, where we may additionally have arbitrary edges between the chains. We will then perform a logspace algorithm following such a partition to guess an accepting path of a (fixed) automaton for K.

We present the complete proof of Proposition C.2 in the rest of Appendix C.3. We first define formally the notion of chain partition. Let G = (V, E) be a DAG, and let (V, E ) be its transitive

closure. A chain partition of G is a partition V 1 • • • V n of V , such that, for all 1 ≤ i ≤ n, the restriction of E to V i × V i
is the transitive closure of a directed path graph: equivalently, for each pair of vertices v = v of V i , either v has a directed path to v in E or v has a directed path to v in E. We call each of the V i a chain of G. Note that, in addition to the edges between vertices of the chain, there may also be arbitrary edges in G between V i and V j for i = j. The width of a chain partition is the number of chains that it contains. The following is then known from partial order theory:

Theorem C.3 [Dil50].
For any DAG G, the width of G is k iff there exists a chain partition of width k of G.

However, to show our desired space bound, we need to look closely into the complexity of computing a chain partition. This task is known to be in PTIME [Ful55] but we are unaware of an existing proof to show that it can be done in NL. Because of this, we must give a custom scheme to compute implicitly a specific chain partition that meets our logspace requirements. One difficulty will be to ensure that, as we compute the chain partition implicitly in NL, we are always looking at the same chain partition each time we recompute it implicitly (i.e., we are not looking at some random chain partition that was nondeterministically chosen for this implicit computation). To fix a canonical choice of chain partition, we look at the minimal one in an order that we will define.

We will see a width-k chain partition as a labeling function χ from V to {1, . . . , k} such that, letting

V i := {v ∈ V | χ(v) = i}, then V 1 • • • V k is indeed a chain partition. Given a DAG (V, E
), the vertices of V are integers, each of them represented in binary by a sequence of size log |n|, and we let < denote the corresponding total order relation on V . We can then talk about the topological sort σ, equivalently seen as a total order < σ , which is minimal according to the lexicographic order defined by <: namely, σ is constructed by picking, at each step, the smallest possible vertex according to < which can be picked (i.e., it has not been picked yet, but all its ancestors have): we write the vertices of V in the order of

< σ as v 1 < • • • < v |V | .
We then lift the total order < σ on V to a total order relation on chain partitions: we write each chain partition as the word χ(v 1 ) • • • χ(v |V | ), and < σ defines an order on the chain partitions given by the lexicographic order on words of {1, . . . , k} |V | . Now, we can talk about the chain partition χ 0 which is minimal according to this total order relation < σ on chain partitions. We will explain how this minimal chain partition can be computed implicitly in logspace. Again, the reason why we are concerned about minimality is simply to ensure that, when using the implicitly-computed chain partition within our logspace algorithm for CTS[K], then the chain partition that we follow is well-defined, i.e., it is the same over all calls to the implicit nondeterministic logspace chain partition oracle. The specific definition of minimality that we use does not matter much.

We now describe the specific implicit representation that we want for the minimal chain partition χ 0 . We want to show that we can evaluate efficiently two functions: one function next, which takes as input a vertex v ∈ V and returns the next vertex of the chain of v in χ 0 , and one function first, which takes as input a chain number 1 ≤ i ≤ k and returns the first vertex of i in χ 0 . Formally, next(v) for v ∈ V is defined as follows: letting c := χ 0 (v) ∈ {1, . . . , k} be the chain to which v belongs in χ 0 , return the vertex next(v) ∈ V which is the successor of v on chain c in χ 0 , if any, or if v is the last vertex of chain c. More formally, next(v) is the vertex of V such that χ 0 (next(v)) = c, the edge v → next(v) is in E , and there is no z ∈ V such that χ 0 (z) = c and the edges v → z and z → next(v) are in E . As for the function first, for any chain number 1 ≤ c ≤ k, we let first(c) be the first element of the chain c in χ 0 , that is, we have χ 0 (first(c)) = c and there is no z ∈ V such that χ 0 (z) = c and the edge z → first(c) is in E . We can now claim: We will do two things in the sequel: prove this lemma, and use it to prove Proposition C.2. To do this, we need to define the notion of a configuration, which will be useful in our algorithms on chain partitions. A configuration is a k-tuple X = (v 1 , . . . , v k ), where each v i is either an element of V or ⊥. Intuitively, X describes the lowest element of each chain, with ⊥ indicating that no element has been assigned to this chain so far; when we consider a configuration X in an algorithm, we assume that the ancestors of X, meaning all vertices w such that for some v i the edge w → v i is in E , have already been assigned to a chain in some fashion. We say that a configuration X is continuable if there exists a chain partition χ which is consistent with X, meaning that χ(v i ) = i for all 1 ≤ i ≤ k such that v i = ⊥. One useful lemma will be the following:

Lemma C.5. There is an algorithm to decide, given a configuration X, whether X is continuable, in space O(k log n).

We will first show how to use this lemma to prove Lemma C.4. We will then explain how to prove Lemma C.5. Last, we will prove Proposition C.2 from Lemma C.4.

We start by proving Lemma C.4. The intuition is that we can use the continuation check of Lemma C.5 as a way to compute implicitly the minimal chain partition, by considering all vertices in the minimal topological sort < σ , and assigning each vertex to the smallest possible chain such that the resulting configuration is continuable. Formally, we show: Proof of Lemma C.4. We maintain a configuration X = (v 1 , . . . , v k ), initially (⊥, . . . , ⊥), and extend it deterministically at each step using the (nondeterministic) oracle for continuation checking described in Lemma C.5. Specifically, at each step of the algorithm, we call S the set of vertices which are ancestors of elements in X, and we consider the vertex v which is as small as possible according to < σ and which is not in S but all its strict ancestors are in S: we can find this vertex in NL. Now, for each 1 ≤ i ≤ k such that the edge v i → v is in E or v i = ⊥, we check whether the configuration X i obtained by replacing v i by v is continuable. We pick the smallest i such that it is, and continue the algorithm with X i : specifically, we guess a suitable i, and guess in co-NL that there is no i < i which is suitable: this is still in NL overall, thanks to the Sze88]. At the end of the process, we have memorized the successor of the vertex of interest on its chain (i.e., the input to next), or the first vertex of the chain of interest (i.e., the input to first), and we return this.

We will soon explain why the algorithm does not get stuck, in the sense that, for each vertex v that we consider, there is a choice of i for which the conditions are respected. However, notice first that, if the algorithm does not get stuck, then the algorithm considers all vertices of V exactly once, following the order < σ of the minimal topological sort. Indeed, at each step, the set S contains all vertices that have been seen so far: the only thing to notice is that, whenever we remove a vertex z from the configuration, we replace it by a vertex z such that all of its ancestors are in S and z is an ancestor of z , so that the new value of S becomes S ∪ {z}. This ensures that we are indeed picking at each step the next vertex that < σ has picked.

We now explain why the algorithm does not get stuck, which we show by induction. Initially, the configuration is (⊥, . . . , ⊥), and this configuration is continuable, as we know by Dilworth's theorem (Theorem C.3). Now, at each step of the algorithm, the current configuration X is continuable by induction hypothesis, because it was chosen to be continuable at the previous step of the algorithm. Now, as X = (v 1 , . . . v k ) is continuable, letting χ be a witnessing chain partition, letting v be the next vertex that we consider, we know that, if v χ(v) = ⊥, then we can take i = χ(v). If v χ(v) = ⊥, then v χ(v) must be an ancestor of v in chain i, and by the condition on the ancestors of v, we know that v must be the first descendant of v χ(v) on the chain, justifying that the edge v χ(v) → v must exist in E . Hence, χ witnesses that the algorithm does not get stuck.

Last, we argue that the values computed by the algorithm are correct. To do so, we show by induction that all choices performed by the algorithm actually follow χ 0 , in the sense that, at each step of the algorithm, the current configuration is consistent with χ 0 , and, for each vertex v that we consider, we take i := χ 0 (v). We do this by mutual induction on these two claims. The base case is trivial because (⊥, . . . , ⊥) is of course consistent by χ 0 . Now, assuming consistency of the configuration, as χ 0 is defined to be minimal following < σ , by minimality of the vertex v picked by both < σ and the algorithm, we know that χ 0 (v) is the minimal value such that the resulting configuration is continuable. Indeed, if it were not, then by taking a smaller continuable value, and taking any witnessing continuation afterwards, we would obtain a chain partition which would be smaller in the lexicographic order, contradicting the minimality of χ 0 . So we have shown that our algorithm actually computes next and first following χ 0 , proving the result.

We now come back to the proof of Lemma C.5:

Proof of Lemma C.5. The proof follows similar ideas as in Lemma C.4: we have a current configuration, we consider the vertices following a topological order, and we try to assign them to a chain, updating the configuration. The only difference is that, instead of assigning the minimal chain number following a continuation check, we simply nondeterministically guess a chain to which we assign them. When the nondeterministic guesses succeed, we can show exactly as in Lemma C.4 (but without worrying about minimality) that these guesses witness the existence of a chain partition which is consistent with the input configuration X, so that X is indeed continuable; and conversely, whenever such a chain partition exist, these is a sequence of nondeterministic guesses which make the algorithm succeed.

Thanks to Lemma C.4, we now know that we can implicitly compute the minimal chain partition within the prescribed time bounds. We are now ready to prove Proposition C.2: Proof of Proposition C.2. We fix an automaton A for the regular language K: remember that, as K is fixed, we can compute A in constant time, and the size of its state set Q and transition relation δ

⊆ Q × A × Q is constant.
Our state at any stage of the algorithm will consist of a configuration. Remember that this is a k-tuple X = (v 1 , . . . , v k ) such that each v i is either ⊥ or an element of V , which intuitively codes the lowest element for each chain, or ⊥ if no element of the chain has been seen so far: initially the configuration is (⊥, . . . , ⊥). The state also contains one state q ∈ Q of the automaton, which is initially some initial state, chosen nondeterministically.

At each stage of the algorithm, we nondeterministically guess one chain 1 ≤ i ≤ k to extend. We then replace the current configuration X with the new configuration X i defined as follows: if

v i = ⊥, then we replace v i in X i by v i := first(v i ); if v i = ⊥, then we replace v i in X i by v i := next(v i ) if it
is different from ; otherwise we cannot choose this value of i. We also cannot choose a value of i when the v i that we have defined cannot be enumerated yet, i.e., if it is not the case that all strict ancestors of v i are in X or are ancestors of vertices in X. Once we have made an appropriate choice for i, we also replace the current state q with some element q such that (q, λ(v i ), q ) ∈ δ, nondeterministically chosen. Intuitively, I C A L P 2 0 1 8

41:24

Topological Sorting with Regular Constraints this means that the automaton processes the letter which is the label of the new element v i which is read along the chain i.

The algorithm concludes when we can no longer perform a step, meaning that v i = ⊥ and next(v i ) = for each 1 ≤ i ≤ k. Then, the algorithm accepts if the current state q is final.

It is clear that, whenever the algorithm succeeds, then the sequence of guesses witnesses the existence of a topological sort of G, obtained following the vertices that are chosen at each step: the definition of the steps that we perform ensure that this sequence indeed respects the edge relation of G, for similar reasons as in the proof of Lemma C.4. Conversely, whenever there is a witnessing topological sort, then we can decompose it along the minimal chain partition χ 0 defined earlier. Specifically, the sequence of vertices given by this topological sort can be expressed as a sequence of operations where we enumerate the first vertex of a chain, or enumerate the next vertex of a chain from the preceding one. The definition of the algorithm ensures that these steps can be mimicked by a sequence of nondeterministic guesses (in particular, following these guesses, the algorithm does not "get stuck" and can always pick the right v i at each step), and likewise the accepting path in the automaton can be mimicked by nondeterministic choices of the states in the transition relation. This establishes the correctness of the algorithm, and concludes the proof. Proof. We can first check in NL whether the total number of a-elements is even; if not, clearly there is no suitable topological sort, so in the sequel we assume that it is.

C.4 Proof of Proposition 4.6: Other Tractable Case

Note that, if any string consists only of b's, then we can clearly enumerate these b's first, and the result is equisatisfiable; so without loss of generality we can always remove any input string that consists only of b's as soon as they appear, so we never consider such strings. Now, if there are less than 3 input strings, then we can conclude in NL by Proposition C.2, so we assume that there are at least 3 strings in the input instance (which contain some a by the assumption that we just made).

Given an input instance I to the CSh-problem for K, we call a block a maximal contiguous sub-sequence of a-labeled elements in a string, and call it an even or odd block depending on the number of such elements. The a-weight of a string is its total number of a-labeled elements, and the a-alternation of a string is its total number of odd a-blocks.

We claim that I does not have a topological sort satisfying K if and only if there is a string whose a-alternation is greater than the sum of the a-weights of all other strings. This condition can clearly be checked in NL: compute the maximal a-alternation of a string, and compute the a-weight of the other strings and compare. Hence, all that remains is to show this condition.

The easy direction is the backward one. If there is a string C whose a-alternation is greater than the sum of the a-weights of all other strings, we know that any topological sort satisfying K must enumerate one element of every odd block of C together with an a-element of another string of C: indeed, when enumerating two a-labeled elements from C, they must be in the same block because of the b-elements between blocks, so this cannot change the parity of a block of C. Hence, under our assumption, a topological sort would have to enumerate more a-elements in the other strings than their total a-weight, which is impossible; this concludes the backward direction.

To show the forward direction, we show the contrapositive: if, for each string C, the a-alternation of C is no greater than the total a-weight of the other strings (which we call assumption (*)), then there exist a suitable topological sort.

We first make a simplifying observation. Given an instance I, for any choice of two contiguous a-elements in a string of I, we let I be the result of removing these two elements. If I has a suitable topological sort, then so does I, because we can just mimic the topological sort on I and enumerate the two adjacent a-elements when they become available. Hence, to show that there is a suitable topological sort, we can always decide to remove any two contiguous a's in a block (even at a stage where they are not available). We call this a simplification. Note, however, that we cannot apply this simplification blindly, as the converse implication to the above does not hold in general (consider {ababa, aaa} vs {ababa, a}).

We will define a second assumption (**), and show two things: (i.) given any input instance satisfying (*) with an even number of a's and with at least 3 strings (containing some a), we can rewrite it through simplifications (and removal of strings containing only b) to an instance satisfying (**), and (ii.) that given an instance satisfying (**) and our preliminary assumptions, we can build a suitable topological sort. Condition (**) says: for each string C, the a-weight of C is no greater than the total a-weight of the other strings. (Notice the difference with (*).)

We first show (ii.): under our preliminary assumptions on I, any instance satisfying (**) has a suitable topological sort. We do so by describing a greedy algorithm which enumerates elements in a way that achieves a suitable topological sort. Namely:

1. If we can enumerate a b-element, then enumerate it. 2. Otherwise, pick the two strings whose non-enumerated elements have largest a-weight and enumerate one a from each of these two strings.

If this algorithm does not get stuck, then it clearly constructs a topological sort satisfying K. Now, the only way for this algorithm to get stuck is if there is only one string left, but this would violate (**). Hence, it suffices to show that the algorithm preserves assumption (**). Clearly step 1 preserves it, so we focus on step 2. By assumption (**) there are at least two strings left: if there are exactly two strings left, then condition (**) is preserved as the a-weight of both strings is decreased. Assume now that there are at least three strings left before applying step 2, and let C, C , C be the strings with the largest a-weight (in terms of unenumerated elements) and let n ≥ n ≥ n be their respective a-weights. After step 2, the a-weights are n -1, n -1, and n . It is clear that, as condition (**) held of C and C before step 2, then the condition still holds, as the a-weight of each of these two strings and the total a-weight of the other strings has been decremented, then condition (**) still holds of these strings. We must show that it holds of the other strings, and clearly it suffices to focus on C , which has the largest a-weight in terms of non-enumerated elements. There are three cases, depending on the relationship of n to n.

If n < n -1, then as (**) is still satisfied for C after the step and the a-weight of C is still smaller than C after the step, then (**) is satisfied for C too.

If n = n -1, then after performing the step, C and C have same a-weight, and it is obvious that if condition (**) holds of a string C then it holds of a string with the exact same a-weight (as the a-weight of the two strings is the same, and so is the a-weight of the other strings).

If n = n, then we have n = n = n. Now, the only problematic case would be if, after performing the step, n were strictly greater than the a-weight of all other strings, in particular, we would have n > (n -1) + (n -1). But substituting in this inequality we get n > 2n -2, hence n < 2. Hence, the only bad situation is when all strings have a-weight at most 1, but then, remembering that the number of a's was initially even and I C A L P 2 0 1 8

41:26

Topological Sorting with Regular Constraints clearly remains even throughout the enumeration, we have at least 2 strings left after the step in this case that all have a-weight exactly 1, so condition (**) is always respected.

Hence, we have shown that, on any input instance satisfying condition (**) in addition to our preliminary requirements, the above algorithm succeeds and produces a suitable topological sort.

The only thing left to show is (i.): given an instance satisfying (*) and our preliminary requirements, in particular that of having at least 3 strings containing an a-element, then we can rewrite it using simplifications to an instance satisfying (**). To do so, let us observe that, for any string with a-alternation n and a-weight m, we can clearly perform simplifications to rewrite it to a string of a-weight p for any value n ≤ p ≤ m of the same parity as m (or of n, as m and n have same parity). So let us simplify the string C with the greatest a-alternation to make its a-weight equal to its a-alternation n, and let us rewrite all strings in the following way: if the string has a-weight ≤ n + 1, we do not change it; otherwise we simplify it to n or n + 1 depending on the parity of its a-weight. Let us show that the result of this transformation satisfies assumption (**). Consider a string C and show the condition. If C = C, then C has a-weight n, and thanks to condition (*) we know that the sum of a-weights are greater than n, because the only case where we have reduced the a-weight of another string C than C was to bring it down to n or n + 1, in which case C suffices to witness that (**) is satisfied for C. If C is different from C, then its greatest possible a-weight is n + 1 by construction, however, we know that C achieves a-weight n, and thanks to the assumption that we have at least 3 strings containing a's, we know that there is another string containing some a, hence (**) holds for C . This establishes that (**) now holds after the simplifications, which concludes the proof.

D

K such that CSh[K] is in NL but CSh u -1 K is NP-hard.
Intersection. There exists two regular languages K 1 and K 2 such that CTS[K 1 ] and

CTS[K 2 ] are both in PTIME but CSh[K 1 ∩ K 2 ] is NP-hard Complement.
There exists a regular language K such that

CTS[K] is in NL, but CSh[A * \ K] is NP-hard.
Inverse of morphism. There exists a regular language K and morphism ϕ such that

CTS[K] is in NL but CSh ϕ -1 (K) is NP-hard.
First, we show that tractable languages for CSh are not closed under left quotient. Recall that the left quotient of a language K by a word u ∈ A * is the language u -1 K := {v ∈ A * | uv ∈ K}; right quotients are defined analogously. We only consider left quotients, but of course the same result holds for right quotients because both our problems are symmetric under the reverse operator: Proposition D.1. There exists a word u ∈ A * and a regular language K such that CSh[K] is tractable but u -1 K = (ab) * , so that CSh u -1 K is NP-hard by Theorem 3.6.

Proof. Take A := {a, b} and K := bA * + aaA * + (ab) * . Take u := ab. It is clear that u -1 K = (ab) * . However, CSh[K] is tractable by the following reasoning. Consider an input instance to CSh [K]. If there is a string that starts with b, then we can clearly always construct a topological sort achieving bA * . Hence, we can assume that all strings start with a. If there are two strings or more, by taking their first letters, we can clearly always construct a topological sort achieving aaA * . Hence, we can assume that there is only one string, and we can clearly check in NL whether the only possible topological sort achieves K.

However, we point out that the tractable languages for the CTS-problem are closed under quotient: Proposition D.2. For any word u ∈ A * and regular language K, there is an logspace

reduction from CTS u -1 K to CTS[K].
Thus, for the language K := b * A * + aaA * + (ab) * used in the proof of Proposition 5.1, we know that CTS[K] is NP-hard but CSh[K] is in NL: hence, K separates the problems CSh and CTS.

Proof of Proposition D.2. Fix u ∈ A * and K. Given an A-DAG G, to solve CTS u -1 K on G, construct the DAG G obtained by adding a directed path of elements whose label is u and adding edges from each element of the directed path to all elements of G. It is obvious that there is a topological sort of G achieving K iff there is a topological sort of G achieving u -1 K, which concludes the proof.

Second, we illustrate that tractable languages are not closed under the intersection operator, for both problems:

Proposition D.3. There exists two regular languages

K 1 and K 2 such that CTS[K 1 ] and CTS[K 2 ] are both in PTIME, but K 1 ∩ K 2 = (ab) * , so that CSh[K 1 ∩ K 2 ] is NP-hard by Theorem 3.6.
Note that we do not show that CTS[K 1 ] and CTS[K 2 ] are in NL, although we conjecture that this should hold.

Proof of Proposition D.3. We fix A := {a, b} and take K 1 = (ab) * ( + bA * ) and K 2 = (ab) * ( + aaA * ). It is clear that K 1 ∩ K 2 = (ab) * , so we only need to show that CTS[K 1 ] and CTS[K 2 ] are tractable. Now, observe that a -1 K 1 b -1 = (ba) * ( + bbA * ), which is the result of swapping the symbols a and b in K 2 . Hence, if we establish that CTS[K 1 ] is in PTIME, then by Proposition D.2, as PTIME-membership is clearly preserved by renaming the symbols, we have also shown that CTS[K 2 ] is in PTIME. So we focus on K 1 .

We will show a greedy algorithm in PTIME to solve CTS[K 1 ], and explain why it succeeds. The algorithm has two states: State α (the initial state), where: being out of symbols means that we have succeeded, i.e., we have constructed a topological sort in (ab) * ; enumerating an a allows us to move to state β; enumerating a b allows us to "win", i.e., that we can continue the topological sort in any way and remain in K 1 . State β, where: being out of symbols means that we have failed, i.e., the word that we have formed is of the form (ab) * a and not in K 1 ; enumerating an a is forbidden; enumerating a b allows us to move back to state α.

We accordingly design the algorithm as follows:

I C A L P 2 0 1 8 41:28

Topological Sorting with Regular Constraints

In state β: if there is an available b, enumerate any of them and move to state α; otherwise fail. In state α:

if there is an available b, enumerate it and succeed; otherwise, if there is an available a such that, when enumerating this a, there is an available b (call this a profitable a), then enumerate any one of these a's and move to state β; otherwise, if there are no symbols left, succeed; otherwise fail.

If the algorithm succeeds, then it clearly builds a suitable topological sort, hence we have to argue for the other direction: if there is a suitable topological sort then the algorithm will find it. To do so, we must justify that the choices made by the algorithm are without loss of generality, i.e., any suitable topological sort can be modified to follow the rules of the algorithm, so as to witness that the algorithm succeeds.

Let us thus consider a witnessing topological sort σ, and consider the first point at which σ disagrees with the actions of the algorithm, and change σ to continue like the algorithm did and still achieve K: we can then repeat the argument until σ is exactly what the algorithm does, which allows us to conclude that the algorithm succeeds. When the algorithm did the choice that disagrees with σ, either it was in state α or in state β; note that if the algorithm had already decided that it had succeeded, then there is nothing left to show as indeed the topological sort is suitable no matter how it continues.

If the algorithm was in state β, as σ is suitable, there must be an available b. If there is only one available b, then the algorithm and the topological sort cannot disagree, so the only thing to consider is the case where the algorithm picks one b-labeled element v and σ picks another v . However, in this case, we can modify σ to pick v and then pick v (which is available), and this ensures that σ succeeds immediately, so it is still suitable. So we have modified modify σ to do like the algorithm does (and succeed immediately).

If the algorithm was in state α, if there is an available b, then we can always modify σ to take it and succeed. Likewise, if there is no available symbol, then σ and the algorithm are both finished and both succeed. Hence, the only possible disagreement is if σ picks a different a than what the algorithm chose, of if σ picked an unprofitable a whereas the algorithm failed. However, note that, as σ is a suitable topological sort, it cannot pick an unprofitable a, as it will necessarily be stuck afterwards (only a's, if anything, will be available, and we will be in state β), so the second case is impossible by our assumption that σ is suitable. So the only case to consider is the first case, and we will explain how to modify σ to pick immediately the profitable a that the algorithm enumerates (call it v), followed by the b that the algorithm enumerates after v (call it w).

To do this, consider the later moment at which σ enumerates v. It is possible that, when σ enumerates v, it has already succeeded (meaning, there were two contiguous b's after an a earlier in σ), but in this case there is no constraint on σ and we can simply move v and w in σ to enumerate them at the moment the algorithm does, and σ is still suitable. If σ has not already succeeded when it enumerates v, then either σ enumerates w just after v (subcase 1), or it does not (subcase 2). If it does (subcase 1), then we can modify σ by moving v and w to the beginning: σ is still a topological sort after this change (indeed we can enumerate v and w because the algorithm does it, and for the other elements there is nothing to show), and σ is still suitable (we have added an ab-factor at the beginning, and removed an ab-factor in what follows but this has no effect on the fact that σ realizes K 1 ). Now, if σ does not enumerate w immediately after v (subcase 2), then let w be the element that σ enumerates instead; it must be b-labeled (by our assumption that σ has not already succeeded when it enumerates v). But we know from what the algorithm does that σ can only enumerate w after having enumerated v, and not before it has enumerated v, so σ must enumerate w somewhere after w . We modify σ to enumerate w instead of w and enumerate w immediately after: this is still a topological sort as we just explained, and σ is still suitable (no matter what happens afterwards)because now it enumerates two consecutive b's (namely, w and w ) immediately after an a (namely, v). We are now back to subcase 1, because σ now enumerates w just after v, so we can conclude as in that subcase. This concludes the correctness proof.

Note that the algorithm described here is not in NL; we conjecture that CTS[K 1 ] is in NL, but we do not know how this can be shown.

Third, we show that tractable languages are not closed under complement: Proposition D.4. There exists a regular language K such that

CTS[K] is in NL, but A * \ K = (ab) * , so that CSh[A * \ K] is NP-hard by Theorem 3.6. Proof. Take K = bA * ∪ A * a ∪ A * aaA * ∪ A * bbA * .
As K is a union of monomials, we know by Theorem 4.3 that CTS[K] is in NL, however by construction we have

A * \ K = (ab) * .
Fourth, we show that tractable languages are not closed under inverse morphisms. Recall that a morphism from alphabet B to alphabet A is a function ϕ : B * → A * such that ϕ(uv) = ϕ(u)ϕ(v) for all u, v ∈ B * ; note that a morphism is completely defined by the image of each letter of B. The inverse image of a language K over alphabet A by a morphism ϕ is the language over alphabet B defined by ϕ -1 (K) := {v ∈ B * | ϕ(v) ∈ K}. We show: Proposition D.5. There exists a regular language K and morphism ϕ such that CTS[K] is in NL, but ϕ -1 (K) = (ab) * , so that CSh ϕ -1 (K) is NP-hard by Theorem 3.6.

Proof. We take A := {a, b} and K := (ab) * + A * (a 3 + b 3 )A * , as in Proposition 4.5. We know by this proposition that CTS[K] is in NL. However, let ϕ : A * → A * be defined by ϕ(a) := aba and ϕ(b) := bab. We then have ϕ -1 (K) = (ab) * , for which the CSh-problem is NP-hard by Theorem 3.6. Indeed, no word in the image of ϕ has three consecutive a's or three consecutive b's, so ϕ -1 (K) = ϕ -1 ((ab) * ), and this is clearly equal to (ab) * .

D.2 Proof of Theorem 5.2: Coarser Dichotomy Theorem

Recall from the main text the definition of the transition monoid T (S) of a semiautomaton S. We call transition morphism the morphism η : A * → T (S) defined by η(u) = f u for all u ∈ A * : by construction, this morphism is surjective. Recall that our counter-free assumption on S is equivalent to requiring that T (S) is an aperiodic monoid: formally, it for all x ∈ T (S), we have x ω = x ω+1 , where ω ∈ N is the idempotent power of M , i.e., the least integer ω ∈ N such that for every element x in M , we have x ω = x 2ω .

Our characterization of tractable semiautomata in Theorem 5.2 is based on the class DA of monoids [TT02], which is a subset of A. A monoid M is in DA iff it satisfies the equation (xy) ω x(xy) ω = (xy) ω for all x, y ∈ M , where ω again refers to the idempotent power of M ; this implies in particular that M is aperiodic. Our dichotomy result relies on the following characterization of DA: Theorem D.6 ([TT02], Theorem 5 and Theorem 11). Let K be a regular language of A * . The following conditions are equivalent: I C A L P 2 0 1 8 41:30

Topological Sorting with Regular Constraints

K is an union of unambiguous monomials, i.e., of monomials

K = A * 1 a 1 • • • A * n a n A * n+1 such that every word u ∈ K has a unique decomposition u 1 a 1 • • • u n a n u n+1 where u i ∈ A * i for all 1 ≤ i ≤ n + 1.
There exists a monoid M in DA and a morphism ϕ : A * → M such that K is recognized by M , meaning that K = ϕ -1 (P ) for some subset P ⊆ M .

We will also rely on a characterization of monoids that are not in DA:

Proposition D.7 ([TT01], Lemma 10). An aperiodic monoid M is not in DA iff there exists a morphism θ : {a, b} * → M and P ⊆ M such that θ -1 (P ) is either (ab) * or (ab + b) * .

Proof. This result follows from [TT01], Lemma 10, but the latter result is presented in slightly different terminology. Specifically, that result states that an aperiodic monoid is not in DA iff it is divided by two monoids BA 2 and U , that are respectively the syntactic monoid of (ab) * and (ab + b) * (up to relabeling the symbols of Figure 2 of [TT01]). A monoid N divides another monoid M iff there exists a submonoid K of M such that N is a quotient of K. Our lemma follows from this result thanks to the well-known fact that a language K is recognized by a monoid M iff its syntactic monoid divides

M : see [Str94, Theorem V.1.3].
We are now ready to state and prove our dichotomy theorem: Theorem 5.2. Let S be a counter-free semiautomaton. Then the multi-letter CSh-problem and CTS-problem for S are either both in NL, or both NP-complete. The dichotomy is effective: given S, it is PSPACE-complete to decide which case applies.

Proof. Fix the input semiautomaton S. We wish to show that the multi-letter CTS-problem is tractable for S iff the transition monoid T (S) of S is in DA. We call SL(K) the set of possible languages that can be defined from S depending on the input instance, namely, depending on the set {(i 1 , F 1 ), . . . , (i k , F k )} of pairs of initial and final states. For one direction we prove that: (a) if T (S) is in DA, then for any language K in SL(S), the multi-letter CTS-problem for K is in NL. For the converse direction we prove that: (b) if T (S) is not in DA, then there exists a language K in SL(S) whose multi-letter CSh-problem is NP-complete, so we can show NP-hardness by restricting to input instances that use this language.

Proof of (a). Assume that M := T (S) is in DA. We denote by η : A * → M the transition morphism of S and by ψ : M * → M the morphism on words over the alphabet M defined by ψ(m) := m for all m ∈ M . Intuitively, applying ψ to a sequence of elements of M simply evaluates the sequence in M .

Let I = (G, (i 1 , F 1 ), . . . , (i k , F k )) be an instance of the semiautomaton CTS-problem and let K j be the language recognized by the automaton (Q, A, δ, i j , F j ) for all 1 ≤ j ≤ k. We must determine whether G = (V, E, λ) has a topological sort in K := j K j . We will reduce this to our original definition of the CTS-problem for regular languages, with a language that we know to be in NL. Specifically, we will work on the alphabet M of the transition monoid, and the language that we will use is

K := {u ∈ M * | ψ(u) = η(K)}.
In other words, K = ψ -1 (η(K)), so K is recognized by M which is a monoid in DA: by Theorem D.6, we know that K is a union of monomials.

Our goal is then to reduce to CTS [K ]. Formally, we construct from the A * -DAG G = (V, E, λ) the M -DAG G = (V, E, λ ) where we define λ (v) := η(λ(v)) for all v ∈ V . Intuitively, we have relabeled the multi-letter labels of G to single-letter labels in M . We claim that I is a positive instance to the CTS-problem for S iff G is a positive instance to CTS[K ]. This will allow us to conclude, because, by Theorem 4.3 and Corollary 4.2, we know that CTS[K ] is in NL.

To show the equivalence, we will show that for any topological sort σ of (G, V ), the word λ(σ) achieved by σ in G is in K iff the word λ (σ) achieved by σ in G is in K . In other words, letting

w 1 • • • w n := λ(σ), we must show that w 1 • • • w n ∈ K iff η(w 1 ) • • • η(w n ) ∈ K .
The forward direction is immediate by applying the morphism η. For the backward direction, we have ψ(η(w 1 ) • • • η(w n ))) ∈ η(K), and the left-hand-side is η(w 1 ) • • • η(w n ), which is η(w 1 • • • w k ) because η is a morphism, so applying η -1 concludes. We have shown the equivalence, so we can reduce in NL to CTS [K ] with K a union of monomials, which establishes NL-membership.

Proof of (b). Assume that T (S) is not in DA. Remember that T (S) is still aperiodic because S is counter-free. Hence, we can apply Proposition D.7: there exists a morphism θ : {a, b} * → M , a set P ⊆ M , and a regular language H ∈ {(ab) * , (ab + b) * } such that θ -1 (P ) = H. Our goal is to use θ and P to define a set of pairs of initial and final states of S so that the CSh-problem for S with these states reduces in logspace to the corresponding problem for H. To do this, let x := θ(a) and y := θ(b). As these are elements of the transition monoid, we can pick u, v ∈ A * such that f u = x and f v = y, which we will use to define our reduction.

Let G = (V, E, λ) be an instance of the CSh-problem for H. Let us build G = (V, E, λ ) where we define λ (w) := θ(λ(w)) for all w ∈ V . For each function f ∈ P , let us define an instance I f of the semiautomaton CSh-problem of S by I f = (G , (q 1 , {f (q 1 )}), . . . , (q n , {f (q n )})) where (q i ) i=1,...,n is an arbitrary enumeration of Q, the set of states of S. Note that a word z ∈ A * is accepted by S for the choice of initial and final states in I f iff f z = f in M . This construction is in NL. Let us show that G is a positive instance to CSh[H] iff one of the I f is a positive instance to the semiautomaton CSh-problem of S, which shows that our reduction is correct (but note that this is not a many-one reduction).

For the forward direction, assume that we have a topological sort σ of (V, E) achieving a word z := λ(σ) of H, and let us consider the word λ

(σ) = θ(z 1 ) • • • θ(z n ) = θ(z 1 • • • z n ) because θ is a morphism. As z ∈ H and θ(H) = P , we know that f := θ(z 1 • • • z n ) is in P .
Hence, consider the instance I f . We know that f z = f by definition, hence σ witnesses that I f has a suitable topological sort.

For the backward direction, assume that there is f ∈ P such that we have a solution of I f . This means that there is a topological sort σ of (V, E) such that the word z := λ (σ) achieved by σ in G is such that f z = f . Now, we know that θ -1 (f ) ⊆ H. Hence, the word λ(σ) achieved by σ in G is in H, so G is a positive instance to CSh[H], which establishes the desired equivalence.

We have thus shown a reduction from CSh[H] to the multi-letter CSh-problem for the semiautomaton S. We can then conclude that the latter problem is NP-hard, because CSh[H] is NP-hard: either H = (ab) * and this follows from Theorem 3.6, or H = (ab + b) * , in which case we conclude from Proposition 3.9.

E

Proofs for Section 6 (Lifting the Counter-Free Assumption for CSh)

E.1 Proof of Theorem 6.1: Coarser Dichotomy Theorem for CSh

We first explain how Theorem 6.1 follows from Theorem 6.2, before dealing with the much more difficult task of proving Theorem 6.2. The overall scheme is like in Section 5: show that monoids in DO can be reduced to tractable languages (specifically, to district group I C A L P 2 0 1 8

41:32

Topological Sorting with Regular Constraints monomials), and show that monoids not in DS capture an intractable language. For the upper bound, we use the following result, which is the counterpart of Theorem D.6 but for DO rather than DA:

Theorem E.1 ([TT05], Theorem 1). Let K be a regular language of A * . The following conditions are equivalent:

K is an union of unambiguous district group monomials, i.e., of district group monomials

K = K 1 a 1 • • • K n a n K n+1 such that every word u ∈ K has a unique decomposition u 1 a 1 • • • u n a n u n+1 where u i ∈ K i for all 1 ≤ i ≤ n + 1.
There exists a monoid M in DO and a morphism η : A * → M such that K is recognized by M , meaning that K = η -1 (P ) for some subset P ⊆ M .

For the lower bound, we use the following folklore result, which extends Proposition D.7 to the non-aperiodic case: Proposition E.2 ([Alm94], Exercise 8.1.6). A monoid M is not in DS iff there exists a morphism θ : {a, b} * → M and P ⊆ M such that θ -1 (P ) is either (ab) * or (ab + b) * .

From these two results, we can prove Theorem 6.1 exactly like we proved Theorem 5.2 in the previous section, using Theorem 6.2 instead of Theorem 4.3. The hard work that remains is to prove Theorem 6.2.

E.2 High-Level Presentation of the Proof of Theorem 6.2

This appendix gives a high-level view of the proof of Theorem 6.2. For most of the proof, we focus on the case of group languages: the case of group district monomials is only presented at the very end, in Appendix E.6. The CSh-problem for group languages can essentially be stated directly in terms of the underlying group: we fix a finite group H and a target element g, our instance to the CSh-problem is a tuple I of strings over H, and we want to test if there is an interleaving of I which evaluates to g according to the group operation. So we see A := H as the alphabet of I.

As explained in the proof sketch, given the CSh-instance I, we will split the letters of A between rare letters A rare and frequent letters A freq , which we call a rare-frequent partition. This will ensure that the rare letters A rare only occur in constantly many input strings (called the rare strings), and the frequent letters A freq occur in sufficiently many different input strings (called the frequent strings).

For the frequent letters, the key idea is that we can pick many occurrences of each frequent letter in different strings, and obtain an antichain C (subset of pairwise incomparable elements), which contains many occurrences of each frequent letter of A freq . Now, in a topological sort, we can enumerate all elements of C contiguously, following any permutation on C. Intuitively, as C contains many occurrences of each frequent letter, this should give us the freedom to create many different elements in the subgroup of H generated by A freq . We cannot obtain all elements of this subgroup, because the number of occurrences of each group element is fixed by that of C. To formalize this intuition, the notion of Parikh image is helpful: As it will turn out, the Parikh image is the only constraint on what we can generate using such an antichain C. We formalize this intuition in the antichain lemma (Lemma E.4): we show that, for any finite group, if we have enough copies of each element, we can permute them to realize any element of the group, up to "commutative constraints". Thanks to this, the CSh-problem simply reduces to a test on the Parikh image PI(I) of the instance, under our initial assumption.

We must now explain how to handle the rare letters A rare . We can simply look at the constant number of strings that contain a letter of A rare , and handle these strings with an approach based on dynamic programming, as in the proof of Proposition C.2. So it seems like the problem is solved: apply dynamic programming to the rare strings, and use the antichain lemma to argue that the frequent strings can generate any letter of the subgroup spanned by A freq , up to the commutative constraints. However, one difficulty remains: in a topological sort of the rare strings, we can insert elements from the frequent strings at any point in the dynamic algorithm, and the rare strings may be arbitrarily long; yet the frequent strings cannot create arbitrarily many copies of each group element, because we must use a constant bound when splitting H into A rare and A freq . We address this by proving a result called the insertion lemma (Lemma E.5), which intuitively says that a constant number of insertions always suffice. This is the result whose proof uses Ramsey's theorem. Thanks to the insertion lemma, it suffices to allow constantly many insertions of frequent elements when performing the NL algorithm on the rare strings, which allows us to conclude.

We give some more detail by stating the antichain lemma and insertion lemma as standalone results (and defer their complete proof to the next sections of the appendix, i.e., Appendices E.3 and E.4). We then formalize the rare-frequent partition and sketch the remainder of the proof of Theorem 6.2 (the details about the reminder of the proof are given in Appendix E.5).

Antichain lemma.

Let G be an A-DAG over some alphabet A, let C be an antichain of G, and let n ∈ N. We call C an n-rich antichain if each letter of A appears at least n times in C. The antichain lemma intuitively shows that when G has a rich antichain, then it suffices to look at commutative information of G, namely, its Parikh image, to decide whether it has a topological sort that achieves a group element. In fact, the claim applies to any constant-length sequence of group elements, following our needs for the insertion lemma later. Formally: Lemma E.4 (Antichain lemma). Let H be a finite group and µ : A * → H be a surjective morphism. For any integer k > 0, there exists an integer n k such that, for any A-DAG G = (V, E, λ) with an n k -rich antichain, for any elements g 1 , . . . ,

g k of H, if PI(G) ∈ PI(µ -1 (g 1 • • • g k )) then there is a topological sort σ of G decomposable as σ = σ 1 • • • σ k such that µ(λ(σ i )) = g i for each i ∈ {1, . . . , k}.
Note that this result is not specific to the CSh-problem, and applies to arbitrary DAGs. We now sketch its proof here; the complete proof is given in Appendix E.3: Proof sketch. We capture the "commutative information" contained in the Parikh image of the rich antichain as an element in a commutative monoid N constructed from the commutative closure of H. The elements that we can hope to reach with the antichain I C A L P 2 0 1 8 41:34 Topological Sorting with Regular Constraints are then the images of this element of N by a so-called relational morphism [Eil74] written τ : N → P(H). Intuitively, for n ∈ N capturing some "commutative information", τ (n) are the elements of H which correspond to this information. We then study the elements of N that use sufficiently many copies of each generator of N , called the fully recurrent elements, and show that their images by τ all have the same cardinality. In other words, all antichains that are sufficiently rich can achieve the same number of elements of H. This allows us to conclude, because making the antichain richer always allows us to reach more elements, so an antichain which is richer than this threshold always achieves the maximal possible number of elements.

Insertion lemma. We now turn to the insertion lemma, which allows us to show that we only need to insert group elements at a constant number of places. More precisely, when we achieve a group element by interleaving two sequences, we can always interleave them differently so that there are constantly many insertions and still achieve the same element.

Lemma E.5 (Insertion lemma).

Let H be a finite group and µ : A * → H be a surjective morphism. There exists a constant B ∈ N such that, for any n ∈ N, for any n-tuple w 1 , . . . , w n of words of A * and (n+1)-tuple w 0 , . . . , w n of words of A * , letting u = w 0 w 1 w 1 w 2 w 2 • • • w n w n , there exists a set J ⊆ {0, . . . , n} of cardinality at most B such that, letting w j for 0 ≤ j ≤ n be w j if j ∈ J and the empty word otherwise, letting

v = w 0 w 1 w 1 • • • w n w n , we have µ(u) = µ(v) and µ(w 0 • • • w n ) = µ(w 0 • • • w n ).
We give a sketch of the result; the complete proof is presented in Appendix E.4: Proof sketch. We reason on the complete graph of positions of the word u, coloring each edge by three group elements derived from the corresponding factor: the group element achieved when performing the insertions (from u), the group element achieved when we do not perform them (from v), and the group element achieved by the insertions on their own (from the w i ). We then use Ramsey's theorem to extract a monochromatic triangle in this graph: we show that, in the factor spanned by this triangle, there is no difference between performing the insertions and not performing them. We can repeat this argument as long as the word has sufficiently many letters, so we reach a constant bound B which comes from Ramsey's theorem.

Putting the proof together. We are now ready to explain at a high level the rest of the proof of Theorem 6.2 in the case of group languages. Let K be a group language on the alphabet A = {a 1 , . . . , a k }. We let µ : A * → H be the syntactic morphism of K, where H is a finite group generated by the µ(a i ). We consider an instance I = (S 1 , . . . , S n ) to the CSh-problem, where each S i is a string of vertices labeled with letters of the alphabet A. Let B be the bound whose existence is shown in Lemma E.5, and, using Lemma E.4 for the value k := B, let R be the value of n k given by this lemma. We will decompose I following a rare-frequent partition, which we now define: Definition E.6. A rare-frequent partition of I consists of a partition of A into rare letters A rare and frequent letters A freq , and a partition of the strings into rare strings S rare and frequent strings S freq , where all vertices of S freq are labeled with letters of A freq , and where S freq , when seen as an subinstance of I over the alphabet A freq , contains an R-rich antichain.

Note that, in a partition, rare strings may still contain arbitrarily many frequent letters, and rare letters may still occur a unbounded number of times overall in I, as they can occur arbitrarily many times in each rare string. We can then show the following:

For part (i), we show that |τ (r i )| ≤ |τ (r i+1 )| for all i ≥ 1. By definition of relational morphisms, we have τ (r i )τ (r) ⊆ τ (r i+1 ). Now, remembering that the empty set is not in the image of a relational morphism, pick any x ∈ τ (r). We know that τ (r i ) • {x} ⊆ τ (r i )τ (r). Now, as x ∈ H and H is a group, we know that H acts bijectively on any subset of H, in particular τ (r), hence |τ (r

i )| = |τ (r i ) • {x}| ≤ |τ (r i )τ (r)| ≤ |τ (r i+1 )|. This shows part (i).
We now show part (ii). To do so, let us show first that r ω+1 = r. Indeed, write r = s r1 1 • • • s rn n , and we simply conclude using the fact that

s ri+ω i = s ri-ω i (s ω i ) 2 = s ri-ω i s ω i = s ri i .
This implies that we have r jω+1 = (r ω ) j r = r ω r = r, for any j ≥ 0. As ω ≥ 1, there are arbitrarily large values of jω, so this concludes part (ii) and we have established claim (*), which finishes the proof.

We are now ready to show the antichain lemma (Lemma E.4). Recall its statement: Lemma E.4: Let H be a finite group and µ : A * → H be a surjective morphism. For any integer k > 0, there exists an integer n k such that, for any A-DAG G = (V, E, λ) with an n k -rich antichain, for any elements g

1 , . . . , g k of H, if PI(G) ∈ PI(µ -1 (g 1 • • • g k )) then there is a topological sort σ of G decomposable as σ = σ 1 • • • σ k such that µ(λ(σ i )) = g i for each i ∈ {1, . . . , k}.
Proof of Lemma E.4. Fix the finite group H, and let µ : A * → H be the surjective morphism. We fix γ = max g∈H min u∈µ -1 (g) |u|: this value is well-defined because µ is surjective, and is finite because H is finite. Let Com µ : A * → N be the surjective morphism defined as before, where N is a commutative monoid, and let ω be the idempotent power of N . Finally, let τ : N → H be the relational morphism defined by τ (x) = µ(Com -1 µ (x)). Observe that the Parikh image assumption on the input A-DAG G and on the g 1 , . . . , g k in the statement of the lemma is equivalent to Com

µ (G) ∈ Com µ (µ -1 (g 1 • • • g k ))
. Indeed, the forward implication is immediate, and the converse holds because Com µ recognizes CCl(µ -1 (g 1 • • • g k )), so the rephrased condition implies that CCl(G) ∈ CCl(µ -1 (g 1 • • • g k )), which clearly implies the original condition. Further, by composing with τ and simplifying using the definition of τ , the condition rephrases to g 1 • • • g k ∈ τ (Com µ (G)). We will use this equivalent rephrased condition throughout the proof.

Let us now show the result by induction on k > 0. For every k, we will choose n k := ω + (k -1)γ. Let us first show the base case for k = 1 and n k = ω. Let G = (V, E, λ) be the input A-DAG to the CTS-problem, and let us study the set T = {µ(λ(σ)) | σ is a topological sort of G}. Remembering that all topological sorts of G have the same Parikh image, namely, PI(G), we know from the commutativity of N that all topological sorts of G have the same image by Com µ , namely, Com µ (G). Hence, T is included in τ (Com µ (G)). Our goal is to show that, when G has a ω-rich antichain, we have T = τ (Com µ (G)). Indeed, in this case, we know that, for any g 1 such that PI(G) ∈ PI(µ -1 (g 1 )), we have g 1 ∈ τ (Com µ (G)) as we explained above, so g 1 ∈ T and there is a topological sort σ := σ 1 of G such that µ(λ(σ 1 )) = g 1 . So all that remains to show for the base case is that T = τ (Com µ (G)).

Let C be a ω-rich antichain of G. For simplicity, let us make C maximal: whenever some vertex x of G is not in C but is incomparable to all vertices of C, we add it to C. We choose the vertices arbitrarily. At the end of the process, C is still an antichain, and it is still ω-rich. Further, we can partition G as G -C G + , where G -contains all vertices having a directed path of positive length to a vertex of C, and G + contains all vertices having a directed path of positive length from a vertex of C. To see why this is a partition, observe that it covers G because any counterexample vertex x would contradict the maximality of C. Further, C is disjoint from G + , and from G -, because it is an antichain, and G + and G - I C A L P 2 0 1 8

41:38

Topological Sorting with Regular Constraints are disjoint: any element in G + ∩ G -would witness by transitivity a path from an element of C to an element of C, contradicting the fact that C is an antichain.

Let σ -and σ + be arbitrary topological sorts of G -and G + respectively. Our chosen partition ensures that we can build a topological sort of G as σ -, σ, σ + where σ is a topological sort of C. Hence, T : We now prove the inductive step. Assume the property holds for k > 0. Let G be an instance of the CTS-problem that has a n k+1 -rich antichain: as in the base case we expand it to a maximal such antichain, denote it by C, partition G as G -C G + , and let σ - and σ + be arbitrary topological sorts of G -and G + respectively. Let us choose elements g 1 , . . . , g k+1 of H such that g

= µ(σ -) • τ (Com µ (C)) • µ(σ + ) is a subset of T ,
1 • • • g k+1 ∈ τ (Com µ (G)): remember that this implies that g 1 • • • g k+1 ∈ τ (Com µ (G)).
Now, let us consider g := g k+1 • µ(σ + ) -1 . Let u g ∈ A * be a word that realises the minimum in the definition of γ, and let C g be a subset of C whose elements are labeled with the letters of u g . As C is n k+1 -rich, we can find such a subset, and further C \ C g is still a ((k -1)γ + ω)-rich antichain, i.e., an n k -rich antichain. Further, the definition of C g ensures that it has a topological sort σ that realizes the word u g , so that µ(σ ) = g . By composing it with σ + , we can then construct σ σ + , which is a topological sort of G C g G + such that µ(λ(σ σ + )) = g k+1 .

We now wish to apply the induction hypothesis for g 1 , . . . , g k on the subinstance G := G -(C \ C g ), which still has a n k -rich antichain. To do so, we must check that PI(G ) ∈ PI(µ -1 (g 1 • • • g k )), which as we argued is equivalent to g

1 • • • g k ∈ τ (Com µ (G )).
As G is the disjoint union of G and G , we have Com µ (G) = Com µ (G )Com µ (G ), so by composing by τ and applying the definition of a relational morphism we have:

τ (Com µ (G)) ⊆ τ (Com µ (G )Com µ (G ))
Now, as both G and G contain an antichain which is at least ω-rich, we know that Com µ (G) and Com µ (G) are fully recurrent. By applying Lemma E.9 again, we know that |τ

(Com µ (G))| = |τ (Com µ (G )|. Remember now that σ σ + is a topological sort of G such that µ(λ(σ σ + )) = g k+1 . Hence, g k+1 ∈ τ (Com µ (G )). Now, as g k+1 acts bijec- tively on τ (Com µ (G )) in the group H, we deduce that τ (Com µ (G)) = τ (Com µ (G ))g k+1 . Now, since we have g 1 • • • g k+1 ∈ τ (Com µ (G)) by hypothesis, we deduce that indeed g 1 • • • g k ∈ τ (Com µ (G )
), so we can apply the induction hypothesis.

Hence, we do so and obtain a topological sort σ 1 , . . . , σ k of G such that µ(λ(σ i )) = g i for each i ∈ {1, . . . , k}. Now, letting σ k+1 := σ σ + , it is clear that σ 1 , . . . , σ k , σ k+1 is a topological sort of G, and we have µ(λ(σ σ + )) = g k+1 , so we have shown the induction hypothesis. This concludes the proof.

E.4 Proof of Lemma E.5: Insertion Lemma

We now prove the insertion lemma (Lemma E.5). Recall its statement:

E.5 Proof of Theorem 6.2 for the Case of Group Languages

We give the complete proof of Theorem 6.2 for the case of group languages.

Let K be a group language on the alphabet A = {a 1 , . . . , a k }, let µ : A * → H be the syntactic morphism of K, where H is a finite group generated by the µ(a i ). Consider an instance I = (S 1 , . . . , S n ) to the CSh-problem, where each S i is a directed path of vertices labeled with letters of the alphabet A. Recall from Appendix E.2 that B is the bound whose existence is shown in Lemma E.5, and, using Lemma E.4 for the value k := B, R is the value of n k given by this lemma. Recall the definition of a rare-frequent partition of I (Definition E.6) from Appendix E.2, and recall that we have used Lemma E.7 to compute in NL a rare-frequent partition of I, given by A rare , A freq , S rare , and (implicitly) S freq . We write H freq for the subgroup of H equal to µ(A * freq ), i.e., the subgroup spanned by A freq . Our goal is to determine whether I has some topological sort in K. This is the case iff it has a topological sort mapped to an accepting element of H by µ, so we can equivalently test, for each accepting element of H, whether there is a topological sort that achieves it. Hence, let g be the target element. Recall that the commutative closure of the language µ -1 (g) is a regular language by Lemma E.8, and is obviously commutative. Further recall the morphism Com µ : A * → N from Section E.3, where N is a commutative monoid that recognises the inverse image of all elements of H, in particular g. Recall also the relational morphism τ : N → H defined by τ (x) = µ(Com -1 µ (x)). We will state a condition, called (*), and construct an NL algorithm to check (*). We will then show that (*) holds iff I has a topological sort that achieves g. Condition (*) is: there exists a topological sort ρ of S rare which can be decomposed as ρ 1 • • • ρ n , and a sequence g 0 , . . . , g n of elements of H freq , such that: we write σ 0 ρ 1 σ 1 • • • ρ n σ n , with ρ 1 • • • ρ n being a topological sort of S rare , and σ 0 • • • σ n being a topological sort of S freq (in particular, we have µ(λ(σ 0 • • • σ n )) ∈ τ (Com µ (S freq )), which we call condition (#2 )). We now use the insertion lemma (Lemma E.5) to argue that there exists a set w 0 , . . . , w n of words of A * , with w i = λ(σ i ) for at most B values of i and being the empty word otherwise, such that µ(w 0 λ(ρ 1 )w 1 • • • λ(ρ n )w n ) = µ(σ ) = g, and (#2 ) µ(λ(σ 0 • • • σ n )) = µ(w 0 • • • w n ). We now collapse the ρ i which are contiguous, calling the result ρ 1 , . . . , ρ n , where we have (#3) n < B, and write g i the µ-image of the i-th w i which is non-empty: this image is in H freq because the strings in S freq are only labeled with letters in A freq . This gives us a topological sort ρ 1 , . . . , ρ n of S rare , and a sequence g 0 , . . . , g n of elements of H freq , such that (#1) g 0 µ(λ(ρ 1 ))g 1 • • • µ(λ(ρ n ))g n = g. By (#1), (#2 ) combined with (#2 ), and (#3), we have satisfied condition (*). This concludes the backward direction, and establishes the equivalence proof. Hence, we have shown Theorem 6.2 in the case of group languages.

E.6 Proof of Theorem 6.2 for the Case of District Group Monomials

We now show the complete proof of Theorem 6.2 by adapting the proof of Appendix E.5 from the case of group languages to that of district group monomials. We write K = K 0 a 1 K 1 • • • a m K m , where each a i is a letter of the alphabet (they are not necessarily distinct), and each K i is a group language on some subset A i of the alphabet. We fix as before the instance I = (S 1 , . . . , S n ) of the CSh-problem. A K-slicing of the instance I is an (m + 1)tuple of instances I 0 , . . . , I m , with each I j being a n-tuple (S j 1 , . . . , S j n ) of strings, and an m-tuple of instances I 1 , . . . , I m , with each I j being a n-tuple ((S ) j 1 , . . . , (S ) j n ) as before, with the stipulation that, for each 1 ≤ j ≤ m, all (S ) j i are empty except one which is a singleton whose only element is labeled a j ; and that, for each 1 ≤ i ≤ n, the concatenation S 0 i (S ) 1 i S i i • • • (S ) m i S m i is equal to S i . In other words, a slicing is a partition of each string of I in a way that respects the a i .

Intuitively, we would like to guess a slicing, check the I i in the obvious way, and apply the previous result to the I j for odd j, corresponding to the group languages K j . Unfortunately, while guessing the even I j is immediate, we cannot afford to guess the entire slicing in NL. For this reason, we need a more elaborate approach.

We will follow the previous proof and introduce a notion of rare-frequent partition, generalised to slicings. As before, we let B be the bound whose existence is shown in Lemma E.5, use Lemma E.4 with k := B to obtain n k , and let R := n k . Given a slicing I 0 . . . I m and I 1 . . . I m , a rare-frequent partition of the slicing consists of one partition A j rare , A j freq for all 1 ≤ j ≤ m, and one global partition of the strings S 1 , . . . , S n into rare strings S rare and frequent strings S freq (again, the frequent strings are not explicitly represented). We require that (i) for every string S of S freq , considering its slices S 0 , . . . , S m , for each 1 ≤ j ≤ m, the slice S j contains only letters of A j freq ; that (ii) for every 1 ≤ j ≤ m, the S j for S in S freq , when seen as a subinstance of I over the alphabet A j freq , contains an R-rich antichain; and that (iii) for every 1 ≤ j ≤ m, the one non-empty string of I j is in S rare .

We can show as before that, for any slicing, we can compute a rare-frequent partition. In fact we will only need to show that it exists, as the problem in guessing the slicing prevents us from guessing it anyway.

Lemma E.10. For any slicing I 0 , . . . , I m , I 1 , . . . , I m , there exists a rare-frequent partition such that

|S rare | ≤ m • R • k 2 .
Proof. We apply Lemma E.7 to each I j for 1 ≤ j ≤ m to obtain one rare-frequent partition for it, written A j rare A j freq = A j and S j rare S j freq = I j , except that we take m × (R + 2) I C A L P 2 0 1 8

41:42

Topological Sorting with Regular Constraints instead of m. Now, the only thing that remains is to justify that we can take the set of rare strings to be global instead of local, and to satisfy condition (iii). We simply then take S rare to be the union of the strings S of I such that S j is in S j rare for some 0 ≤ j ≤ m, plus the strings that are non-empty in some I j . We take S freq to be the complement. This ensures that condition (iii) is respected by construction. Now, it is clear that condition (i) is respected, as, for each slice, the frequent strings to consider are a subset of the one given by the previous condition. Now, condition (ii) is respected because it was respected initially for the richness threshold of m × (R + 2), and we have only removed at most m × (R + 1) frequent strings in the modification: ((m + 1) -1) × R for the other slices of the form I j , and m for the slices of the form I j . Hence, we can deduce an R-rich antichain by looking at any preexisting (m × (R + 2))-rich antichain.

While we cannot guess the slices, let us guess partitions A j = A j rare A j freq for 0 ≤ j ≤ m and the set S rare of (globally) rare strings of size at most R • k 2 . Let us further guess the slices S j for 1 ≤ j ≤ m, i.e., we guess elements in I with suitable order and labels. As the number of rare strings is constant and m is constant, we guess, for each string of S rare , the m points at which the slices end, i.e., we guess a slice but restricted to the rare strings. As for the frequent strings, we will not guess the slices globally, as there is generally a non-constant number of frequent strings. However, we will guess the "sequence of insertions" to be performed using the frequent antichains for each slice, i.e., the analogue to the sequence g 0 , . . . , g n in condition (*) in the previous proof. Formally, we guess a sequence g j 0 , . . . , g j nj for all 0 ≤ j ≤ m, with each g j i being an element of H j freq , the subgroup of H j spanned by A j freq . Last, we also guess an element γ 0 , . . . , γ m of H 0 × • • • × H m to describe the accepting elements of the H i achieved in each slice.

Intuitively, we will now do two things: first, verify that our guesses are consistent (except for the choice of the γ i ); second, reduce the problem to a simpler problem by replacing all strings of S freq with an additional string labeled directly with elements of the groups H i of the group languages K i , as in the previous proof.

First, to verify that our guesses are consistent, we check the rare strings. On these strings, it is straightforward to verify that the sub-alphabet for each slice is respected. Further, for the slices I j , the verification is immediate. Now, for the frequent strings, we go over them in succession. We maintain a state that stores, for each slice of the form I j for 0 ≤ j ≤ m, how many occurrences of each letter of A we have seen in the slice j, and in how many different strings are these occurrences. Initially, each letter occurs 0 times. Now, when processing a frequent string S which is in S freq (i.e., not in S rare ), we guess a slicing of S, count the number of occurrences of each letter in each slice and add it to our counter of occurrences, and add one to the counter of strings for the symbols that did occur. At the end, we check that the value of our counters satisfies some conditions, which will witness the existence of a suitable slicing of the frequent strings. Specifically, we verify:

For each 0 ≤ j ≤ m, for each a ∈ A \ A j freq , that our choice of slicing does not contain any occurrence of a in the restriction of the slice I j to S freq . For each 0 ≤ j ≤ m, for each a ∈ A j freq , that our choice of slicing ensures that there are at least R different strings that contain an occurrence of a in the restriction of slice I j to S freq , witnessing that it has an R-rich antichain for the alphabet A j freq . For each 0 ≤ j ≤ m, letting w be the word containing all letters of the restriction of slice S j to S freq with the correct number of occurrences, that g j 0 • • • g j nj ∈ τ j (Com µj (w)), intuitively checking that we have the right commutative image.

Hence, it suffices to handle the case where I has no 3-rich antichain. This implies that there is one symbol α ∈ A which occurs in at most two strings S and S , which means that the other strings S 1 , . . . , S m only contain elements labeled with the other symbol β = α of A. Now, it is easy to see that we obtain exactly the same topological sorts by merging together the S 1 , . . . , S m to one string S of elements labeled β whose length is i |S i |. Hence, we can reduce the problem in NL to the instance {S, S , S }. As it has three strings, we can conclude in NL using Proposition C.2. Hence, we have indeed shown that CSh[K] is in NL.

3 Figure 1

 31 Figure 1 Example labeled DAGs on the alphabet A = {a, b, c}

Figure 2

 2 Figure 2 Example of a shuffle reduction from K := (ba) * b to K := (ab) *

  Let u ∈ A * such that |u| a > 0 and |u|

Proposition 4. 6 .

 6 Let A := {a, b} and K := (aa + b) * . The problem CSh[K] is in NL.

  Theorem 3.6: Hardness of (ab) * Theorem 3.6. The problem CSh[(ab) * ] (hence CTS[(ab) * ]) is NP-hard.

Proposition 3 . 8 .

 38 Let L := (aa + bb) * . The problem CSh[L] (hence CTS[L]) is NP-hard.

  For any input to the functions next and first, we can evaluate them in space O(k log n).

Proposition 4. 6 .

 6 Let A := {a, b} and K := (aa + b) * . The problem CSh[K] is in NL.

  We have the following counterexamples to closure:Quotient. There exists a word u ∈ A * and a regular language

Definition E. 3 .

 3 Write the alphabet A as a 1 , . . . , a k in some fixed order. The Parikh image of a word w ∈ A * is PI(w) := (|w| a1 , . . . , |w| a k ) ∈ N k , where |w| a for a ∈ A denotes the number of occurrences of a in w. The Parikh image of a language K is then the set PI(K) of the Parikh images of the words that K contains: for instance, PI((ab) * ) = {(i, i) | i ∈ N}. The Parikh image PI(G) of an A-DAG G = (V, E, λ) is (|G| a1 , . . . , |G| a k ), with each |G| ai being |{v ∈ V | λ(v) = a i }|.The Parikh image PI(I) of a CSh-instance I is defined in the same way, seeing I as a DAG formed of disjoint paths.

  so |T | ≤ |T |. Let us now write s a := Com µ (a) for each letter a ∈ A. We can write Com µ (C) = Π a∈A s ia a , where i a is the number of vertices labeled by a in C. As C is ω-rich, we have i a ≥ ω. Thus, Com µ (C) is fully recurrent by definition. Now, it is clear that Com µ (G) is also fully recurrent, because G is ω-rich also. Thus, by Lemma E.9, we have |τ (Com µ (C))| = |τ (Com µ (G))|. Now, we know that µ(σ -) (resp. µ(σ + )) act bijectively on the left (resp. right) of H, so we also have |τ (Com µ (C))| = |T |. We have thus shown that |τ (Com µ (G))| = |T | ≤ |T |. As T ⊆ τ (Com µ (G)), we deduce that T = τ (Com µ (G)). As we have argued, this concludes the proof of the base case k = 1.

Lemma E.7. For any fixed alphabet A of size k, given an input CSh-instance I = (S 1 , . . . , S n ), we can compute a rare-frequent partition of I in NL, represented as the partition A freq A rare of A and the set of rare strings S rare , such that

Proof. We first argue for the existence of a suitable rare-frequent partition by giving a naive algorithm to construct it, and then justify that we can do it in NL instead.

The naive algorithm initializes A rare = ∅, A freq = A, S rare = ∅, S freq = S, and does the following until convergence: if a letter a ∈ A freq occurs in less than R • k strings of S freq , then remove a from A freq , add a to A rare , remove the ≤ R • k strings that contain a from S freq , and add them to S rare . As we perform the move operation at most once for each letter, it is immediate that the algorithm terminates, and that at the end there are at most R • k 2 rare strings: now the definition of the algorithm clearly ensures that S freq cannot contain any letter of A rare and that each letter of A freq occurs in at least R • k different strings of S freq . By picking R strings of S freq for each letter of A freq in a way that does not overlap, we see that S freq contains an R-rich antichain for the alphabet A freq . Hence, a suitable rare-frequent partition exists.

To construct the rare-frequent partition in NL, simply guess the partition A rare A freq of A, guess the set S rare of rare strings of size ≤ R•k 2 (which is constant), guess R occurrences for each letter of A freq , check that they are all in different strings and that they are not in strings of S rare , and check that the strings which are not in S rare contain only frequent letters.

Hence, we assume that we have computed in NL a rare-frequent partition of I, given by A rare , A freq , S rare , and (implicitly) S freq . We write H freq for the subgroup of H equal to µ(A * freq ), i.e., the subgroup spanned by A freq . We can now sketch the remainder of the proof of Theorem 6.2: Proof sketch. Our goal is to determine whether I has some topological sort in K. We relabel all elements of I with their image in H by µ, and equivalently test whether I has a topological sort achieving a target group element g ∈ H. We do so by an NL algorithm: we perform the analogue of Proposition C.2 on the rare strings S rare , with some insertions of a constant number of elements from H freq which respect the constraints on the Parikh image (again formalized via the notion of relational morphisms). To show correctness, we rely on the antichain lemma (Lemma E.4) to argue that any such pattern of insertions can indeed be performed using S freq , thanks to the rich antichain that it contains. To show completeness, we rely on the insertion lemma (Lemma E.5) to argue that any topological sort achieving an element of H can indeed be rewritten to an equivalent one where we only perform constantly many insertions.

In the rest of the appendix, we first prove the antichain lemma in Appendix E.3, and then prove the insertion lemma in Appendix E.4. We then complete our presentation of the proof of Theorem 6.2 for group languages in Appendix E.5, using the two lemmas and some of the notions introduced in Appendices E. 3 and E.4. Last, we extend the proof to district group monomials in Appendix E.6.

E.3 Proof of Lemma E.4: Antichain Lemma

To prove the antichain lemma, let us fix the finite group H and morphism µ. Recall the definition of the Parikh image (Definition E.3), and let us define the commutative closure CCl(K) of a regular language K as PI -1 (PI(K)), where PI denotes the Parikh image I C A L P 2 0 1 8

41:36

Topological Sorting with Regular Constraints (Definition E.3). Remark that, for any element g ∈ H, the inverse image µ -1 (g) is a group language. Relying on some more standard notions from algebraic language theory, we will say that a language K is recognized by the morphism µ if there exists P ⊆ H such that K = µ -1 (P ). We will also talk about the syntactic monoid of K, which is the transition monoid of the minimal automaton which recognizes K.

We will use the following result on the group languages defined as µ -1 (g) for g ∈ H:

Lemma E.8 ([GGP08], Theorem 3.1). The commutative closure of a group language is regular.

Remark that this result does not hold for the commutative closure of arbitrary regular languages (e.g., (ab) * ), and that the commutative closure of a group language is not necessarily a group language (see [GGP08] for a counterexample). Let us accordingly define a finite monoid N , and let Com µ : A * → N be a surjective morphism such that, for each g ∈ H, the morphism Com µ recognizes CCl(µ -1 (g)). We can construct N , for instance, by taking the direct product of the syntactic monoids recognizing the commutative closure of each µ -1 (g), using Lemma E.8. Further, thanks to commutativity, we can choose N to be a finite commutative monoid. Let ω be a positive idempotent power of N , that is, a value ω ∈ N \ {0} such that we have p 2ω = p ω for every p ∈ N . (Such an idempotent power exists: indeed, for every p in N , there exists k such that p k = p 2k , and we can take ω to be the least common multiple of the idempotent powers of all elements of N .)

To characterize the "commutative information" of elements of H, we will study the connection between H and the commutative monoid N . We will do so using relational morphisms. A relational morphism [Eil74] between two monoids M and M is a map from M to the powerset P(M ) of M , such that for all m ∈ M we have τ (m) = ∅, and for all m, m ∈ M , we have τ (m) • τ (m ) ⊆ τ (mm ), where we extend the product operator of M to the powerset monoid of M in the expected way, that is, S • S = {g • g | g ∈ S, g ∈ S }. For any surjective morphism η : A * → M and morphism µ : A * → M , the map m → µ(η -1 (m)) is a relational morphism. We write τ : M → M if τ is a relational morphism between M and M .

We can now introduce the crucial notion of fully recurrent elements for our purposes, which will formalize the connection to rich antichains. An element p of a commutative monoid N is said to be fully recurrent if there exists a generator S of N and positive integers r 1 , . . . , r n such that p = s r1 1 • • • s rn n , where n = |S|, and r i ≥ ω for all 1 ≤ i ≤ n. The notion of fully recurrent elements is motivated by the following lemma: Lemma E.9. Let τ : N → H be any relational morphism from a commutative monoid to a finite group. For any fully recurrent elements p and q of N , the sets τ (p) and τ (q) have the same size.

Proof. We will show the result using the following claim (*): for any fully recurrent element r, we have |τ (r)| = |τ (r i )| for any i ≥ 1. This suffices to conclude the lemma, because for any fully recurrent elements p and q, we have

and similarly for q. This allows us to conclude from (*) because we have

So we simply show claim (*). Let r be a fully recurrent element, and let us study the sequence (x i ) defined by x i := |τ (r i )| for all i ≥ 1. We must show that the sequence (x i ) is constant. We do this in two parts: (i) we show that it is nondecreasing, and (ii) we show that there are arbitrary large b ∈ N such that x b = x 1 . Parts (i) and (ii) clearly imply that the sequence is constant, which establishes (*).

Lemma E.5:

Let H be a finite group and µ : A * → H be a surjective morphism. There exists a constant B ∈ N such that, for any n ∈ N, for any n-tuple w 1 , . . . , w n of words of A * and (n + 1)-tuple w 0 , . . . , w n of words of A * , letting u = w 0 w 1 w 1 w 2 w 2 • • • w n w n , there exists a set J ⊆ {0, . . . , n} of cardinality at most B such that, letting w j for 0 ≤ j ≤ n be w j if j ∈ J and the empty word otherwise,

Proof of Lemma E.5. Fix the alphabet A, the morphism µ, and the group H. By Ramsey's theorem, there exists a constant B such that, for any complete graph Γ whose edges are labeled with triples of elements of H, if Γ has at least B vertices, then it contains a monochromatic triangle, that is, three vertices v 1 , v 2 , v 3 such that the edges {v 1 , v 2 }, {v 2 , v 3 }, and {v 1 , v 3 } are labeled by the same triple of elements of H.

Let us now show the rest of the claim by strong induction on n ∈ N. The base case of the induction is when n < B, and in this case there is nothing to show: we can simply take J = {0, . . . , n} which achieves the cardinality bound, and then we have u = v so clearly µ(u) = µ(v).

Let us now show the induction step. We take an arbitrary n ∈ N with n ≥ B, assume that the result is true for all smaller n, and show the result for n. Fix the words w i and w i . Now, let us construct the complete graph Γ with n vertices v 1 , . . . , v n and with edges colored by triples of elements of H in the following way: the edge between v i and v j for i < j is colored with the triple (g i,j , g i,j , g i,j ), where we define g i,j := µ(w i . . . w j-1 )),

Now, by Ramsey's theorem, as Γ has more than B vertices, it has a monochromatic triangle. This implies that there are 1 ≤ l < m < r ≤ n such that g l,m = g m,r = g l,r , and g l,m = g m,r = g l,r . Now, as by definition we have g l,r = g l,m g l,r , this means that we have g l,r = g 2 l,r , and as H is a group we can simplify and deduce that g l,r = e, the neutral element of H. We deduce in the same way that g l,r = e. Hence, we have shown g l,r = g l,r , which means that (*): µ(w l w l • • • w r-1 w r-1 ) = µ(w l • • • w r-1 ). Further, we deduce in the same way that (**) g l,r = e.

We will now conclude using the induction hypothesis. Let n = n -(r -l), and consider the n -tuple w 1 , . . . , w l-1 , (w l • • • w r-1 ), w r , • • • , w n of words of A * , and the (n + 1)-tuple w 0 , . . . , w l-1 , w r , . . . , w n . Using the induction hypothesis for n , we deduce the existence of J ⊆ {0, . . . , n } of cardinality at most B such that, defining w j for all 0 ≤ j ≤ n as the empty word if j / ∈ J, as w j if j ∈ J and j < l, and as w j+(r-l) if j ∈ J and j ≥ l, letting

) with v and the w i defined from this choice of J. From the equality (*), we know that we can replace (w l • • • w r-1 ) by (w l w l • • • w r-1 w r-1 ) in u without changing its image by µ, so we have µ(u) = µ(u ). Second, from the fact that J does not contain any element in {l, . . . , r -1}, we know that w j is empty for all j ∈ {l, . . . , r -1}, so we have

; further, from this and our definition of J, we observe that v = v , hence µ(v) = µ(v ). We thus deduce that µ(u) = µ(v). Last, we can use (**) to insert in (***) the product w l • • • w r-1 , to establish the second required equality. This concludes the proof.

Second, we check the following condition (**), inspired from condition (*) in the previous proof: for all 0 ≤ j ≤ m, there exist a topological sort ρ j 0 • • • ρ j nj of the slice S j rare of S rare whose concatenation, interleaved with the singleton elements of the I j , is a topological sort of S rare , and g j 0 λ(ρ j 0 ) • • • g j nj -1 λ(ρ j nj -1 )g j n j = γ j . This can be decided in NL by adapting the algorithm of Proposition C.2 as previously, running it on each slice with one additional string.

Overall, our algorithm succeeds iff there is a guess of γ i , of S rare (at most Rk 2 of them), partitions A j freq A j rare , and sequences g j 0 , . . . , g j nj , such that the verification stage succeeds, and condition (**) holds.

We have described our NL algorithm. We now argue that it works as intended. There are two directions: the forward direction is to show that if the algorithm succeeds then there is a suitable topological sort of I, and the backward direction is to show the converse.

For the forward direction, assume that the algorithm succeeds. We deduce the existence of a set S rare of rare strings (whose slices are written S j rare ), and frequent strings S freq (with the same convention for slices), partitions A j freq A j rare , a slicing I 0 , . . . , I m and I 1 , . . . , I m , a topological sort of S freq constituting of topological sorts ρ j 0 • • • ρ j nj of each S j rare for 0 ≤ j ≤ m interleaved with the singleton elements of the I j for 1 ≤ j ≤ m, sequences g j 0 , . . . , g j nj of elements of H j for 0 ≤ j ≤ m, and an element γ 0 , . . . , γ m of

For all 0 ≤ j ≤ m, the element γ j is accepting in H j . For all 0 ≤ j ≤ m, for all S ∈ S freq , the slice S j contains only letters from A j freq , and contains an R-rich antichain on the sub-alphabet A j freq . For all 0 ≤ j ≤ m, for all S ∈ S rare , the slice S j contains only letters from A j . For all 0 ≤ j ≤ m, letting S j freq be the slice of S freq defined in the expected way, we have

We claim that we can deduce from this the existence of a witnessing topological sort. To do this, as before, we will use Lemma E.4 in the S j freq for all 0 ≤ j ≤ m. From our definition of R, as n j < B, as S j freq contains an n k -rich antichain (seen as an instance on the sub-alphabet A j freq ), as

, there is a topological sort σ j 1 . . . σ j nj of S j freq such that µ j (λ(σ j i )) = g j i for each 0 ≤ j ≤ m and 1 ≤ i ≤ n j . This allows us to deduce our witnessing topological sort of I, consisting of a topological sort of each slice I j of I achieving γ j , interleaved with the trivial topological sorts of the I j that achieve the required a j : the topological sort of I j is formed of the guessed topological sort

rare interleaved with the topological sort σ j 1 , . . . , σ j nj of S j freq , each v j i achieving g j i , so that the topological sort of I j indeed achieves γ j by point (#).

We now show the backward direction. We show that if there is a suitable topological sort, then the algorithm succeeds. The witnessing topological sort must define a slicing of I such that each I j for 0 ≤ j ≤ m has a topological sort achieving an element γ j which is accepting for H j . We now use Lemma E.10 to argue that there exists a rare-frequent partition consisting of a partition S rare S freq of the strings, and A j rare A j freq of the alphabets

In each slice, the witnessing topological sort must consist of a topological sort of the S j rare interleaved with topological sorts of the S j freq . As in the previous proof, we now use Lemma E.5 to argue that we can assume that there are at most n j such insertions, without changing the µ j -image of the result or the µ j -image of the inserted elements. Now, we define the g 1 , . . . , g j nj as the µ j -images of these insertions. We I C A L P 2 0 1 8

41:44

Topological Sorting with Regular Constraints now consider the run of the algorithm where we guess the right rare-frequent partition, the right slices in the rare strings, the right topological sort of the rare strings. We first check that the verification phase of the algorithm does not fail. This is the case: the first condition is by definition of a witnessing topological sort (for A\A j ) and of a rare-frequent partition (for A j \A j rare ); the second condition is by definition of a rare-frequent partition; the third condition is by definition of g 1 , . . . , g j nj being achieved as a topological sort of S j rare . We next explain why the second phase works, by explaining why condition (**) is satisfied. This can be seen by considering when the insertions of the S j freq are performed in the S j rare : we perform the same additions with the additional string. Hence, this run of the algorithm succeeds. This concludes the backwards direction of the correctness proof, so our NL algorithm is correct. This concludes the proof of Theorem 6.2.

E.7 Proof of Proposition 6.3: Example in DS \ DO

We show the side result on the language in DS \ DO. Note that the fact that this language is indeed in DS and not in DO can be simply checked from the equations that define DS and DO, as can be performed, e.g., using [Pap18].

Proof. Consider an input instance I to the CSh-problem for K. Observe first that, if I has no string whose first element is a, then clearly no topological sort of I achieves K. Likewise, if I has no string whose last element is b, then clearly no topological sort of I achieves K. We can check these two conditions in NL and fail if one of them does not hold, so in the sequel we assume that I has a string whose first element is a and a string whose last element is b.

Recall that a 3-rich antichain for A in I is an antichain containing at least 3 elements labeled by a and 3 elements labeled by b. We show that if I contains a 3-rich antichain then it is necessarily a positive instance to CSh [K]. Of course, note that we can easily test in NL if such a 3-rich antichain exists.

To show the claim, let C be such an antichain, and C be a subset of C containing exactly three occurrences of each letter; it is still an antichain. We now define C as a subset of C containing exactly two occurrences of each letter, and ensuring that there is an a-labeled element v a which is the first element of a string and is not in a string of C, and likewise there is a b-labeled element v b which is the last element of a string and is not in a string of C: we can ensure this because we can choose which a-labeled element and which b-labeled element we remove from C to construct C. Now, consider a topological sort σ 1 of I formed by concatenating v a , a topological sort σ - of the ancestors of elements of C and of the elements incomparable to C except v a and v b , a topological sort σ 1 of C achieving the word aabb, a topological sort σ + of the successors of C, and v b . The word w 1 achieved by σ 1 starts with a and ends with b, so it must be of the form (a + b + ) * . Let n 1 be the number of repetitions of a + b + in w 1 . Now, consider the topological sort σ 2 obtained by concatenating v a , σ -, σ 2 , σ + , and v b , where σ 2 is a topological sort of C achieving the word abab. Again, the word w 2 achieved by σ 2 must be of the form (a + b + ) * : let n 2 be the number of repetitions of a + b + in w 2 . We claim that n 2 = n 1 + 1. Indeed, consider the subfactor a + b + that contains σ 1 in σ 1 . In σ 2 , the other subfactors are unchanged, and this subfactor is split into two subfactors, one ending at the first b of σ 2 , the other one starting at the second a of σ 2 . So indeed n 2 = n 1 + 1. Hence, one of n 1 , n 2 is even, and the corresponding σ i witnesses that I is a positive instance to CSh [K].