Constrained Topological Sorting
Antoine Amarilli1 and Charles Paperman2
1
2

LTCI, Télécom ParisTech, Université Paris-Saclay
Université de Lille

arXiv:1707.04310v2 [] 19 Feb 2018

Abstract
We introduce the constrained topological sorting problem (CTS): given a regular language K and
a directed acyclic graph G with labeled vertices, determine if G has a topological sort that forms
a word in K. This natural problem applies to several settings, e.g., scheduling with costs or
verifying concurrent programs. We consider the problem CTS[K] where the target language K
is fixed, and study its complexity depending on K. We show that CTS[K] is tractable when
K falls in several language families, e.g., unions of monomials, which can be used for pattern
matching. However, we show that CTS[K] is NP-hard for K = (ab)∗ and introduce a shuffle
reduction technique to show hardness for more languages. We also study the special case of the
constrained shuffle problem (CSh), where the input graph is a disjoint union of strings, and show
that CSh[K] is additionally tractable when K is a group language or a union of district group
monomials. We conjecture that a dichotomy should hold on the complexity of CTS[K] or CSh[K]
depending on K, and substantiate this by proving a coarser dichotomy under a different problem
phrasing which ensures that tractable languages are closed under common operators.

1

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 wish to compute topological sorts 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 just CTS. For instance, if we fix the language
K = ab∗ c, and consider the example DAGs of Figure 1, then DAGs (a) and (b) 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
© Antoine Amarilli and Charles Paperman;
licensed under Creative Commons License CC-BY
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

XX:2

Constrained Topological Sorting

(a)

b
a

b

c

(b)

b
a

c
b

(c)

a

c

b

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

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, 31, 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 [31] 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 a1 · · · A∗n−1 an−1 A∗n , with the ai being letters and the Ai 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 w1 , . . . , wn of elements of H, decide whether there is an interleaving of the wi
which evaluates to g according to the group operation.

A. Amarilli and C. Paperman

XX:3

We then conclude in Section 7. In the interest of brevity, the complete proofs of most
results are deferred to the appendix.

2

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 =
6 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 [31] 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 t Q of
{1, . . . , |w|} such that wP = u and wQ = v, where wP denotes the sub-word of w where
we keep the letters at positions in P , and likewise for wQ . The shuffle (U ) of a tuple of
words U is defined by induction as follows: we set () := {}, set (u) := {u}, and set
S
(u1 , . . . , un , un+1 ) := v∈(u1 ,...,un ) v un+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 GU by coding each u ∈ U as a directed path graph v1 → · · · → v|u|
with λ(vi ) = ui 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.

















I 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-labeled element, ending with a b-labeled element, and where we
alternate 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 factors of a∗ 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 NPK , 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:
I Proposition 2.2. For any language K, the problems CTS[K] and CSh[K] are in NPK .
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 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.

XX:4

Constrained Topological Sorting

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.

3

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



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



In this section, we will refine this approach to show hardness for more languages. We first
recall another initial hardness result from [31]. 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 [31] 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 [31] by reducing from UNARY-3-PARTITION [12]:



I Lemma 3.2. ([31], Lemma 3.2) Let K := {(ai bi )∗ | 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 0 is also hard. Specifically,
if a language K shuffle-reduces to a language K 0 , this will imply that there is a PTIME
reduction from CTS[K] to CTS[K 0 ], and from CSh[K] to CSh[K 0 ].
The intuition for the shuffle reduction is as follows: to reduce from K to K 0 , given an
input A-DAG G, we build an A-DAG G0 formed of G plus an additional directed path
labeled by a word w. Thus, any topological sort σ 0 of G0 must be the interleaving of w and
of a topological sort σ of G. Now, if we require that σ 0 achieves K 0 , the presence of w can
impose specific conditions on σ. Intuitively, if w is sufficiently long and “far away” from all
words of K 0 , then σ 0 must “repair” w to a word of K 0 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. Amarilli and C. Paperman

w

a

a

b

a

b

XX:5

a

b

b

a

a

b

a
b
G

a

b
b

Global resulting word: abababababababab
Resulting word on G: babab

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

a word of K. This means that solving CTS[K 0 ] on G0 allows us to solve CTS[K] on G. This
intuition is illustrated on Figure 2: to achieve a word of K 0 := (ab)∗ on the DAG G0 , 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 0 ]. Formally:
I Definition 3.3 (Filter sequence). Let K and K 0 be languages on an alphabet A. A filter
sequence for K and K 0 is an infinite sequence (fn ) 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 fn ) ∩ K 0 6= ∅.



In Figure 2, we can choose f5 := 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 σ 0 of σ with w achieves K 0 . We can now define our reduction:
I Definition 3.4 (Shuffle reduction). We say that a language K shuffle-reduces to a
language K 0 if there is a filter sequence (fn ) for K and K 0 such that the function i 7→ fi is
computable in PTIME (where i is given in unary).
We say that a regular language family K shuffle-reduces to K 0 if each K does, and if we
can compute in PTIME the function (K, i) 7→ fiK , which maps a regular expression K of K
and an integer i in unary to the i-th word in a filter sequence (fnK ) for K and K 0 .
I Theorem 3.5. For any regular language family K and language K 0 , if K shuffle-reduces
to K 0 then we can reduce in PTIME from CTS[K] to CTS[K 0 ], and from CSh[K] to CSh[K 0 ].
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:
I 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
B
:=
KB = (aB bB )∗ of K, we define the filter sequence for words of length 2Bn by f2Bn
B B
B
n
(b a ab) . This ensures that, when interleaving f2Bn with a word v of length 2Bn to achieve
B
a word of (ab)∗ , we must use v to insert in f2Bn
the letters written in bold: ((ab)B (ab)B ab)n .
B B n
This can be done iff v = (a b ) , i.e., iff v ∈ KB . We conclude by Theorem 3.5.
J
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 Proposition 3.7. Let u ∈ A∗ such that |u|a > 0 and |u|b > 0 for a 6= b in A. Then CSh[u∗ ]
(hence CTS[u∗ ]) is NP-hard.

XX:6

Constrained Topological Sorting

Proof sketch. We shuffle-reduce from (ab)∗ with the filter sequence f2n := (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 f2n 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 w0 of length |u| of w must be such that |w0 |a = |u|a and |w0 |b = |u|b .
We then consider factors of w of length |u| centered on the u−a and u−b in f2n : 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.
J
We can also use the shuffle reduction to show hardness for other languages, e.g., (aa + bb)∗ :
I 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 f2n = (ab)n .
If a word v with |v| = 2n is such that v f2n intersects (aa + bb)∗ nontrivially, it must
intuitively insert a’s and b’s in f2n alternatively, so it must be (ab)n . Note that a similar
proof would also show hardness for the language (ai + bj )∗ for any choice of i, j ≥ 2.
J



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:
I 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.
J
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:
I 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.

4

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):
I Lemma 4.1. For any finite family of languages K, there is a logspace reduction from
S
S
CTS[ K] to CTS[K], and likewise from CSh[ K] to CSh[K].
S
Proof. To solve a problem for the language K on an input instance I, simply enumerate
the languages K 0 ∈ K, and solve the problem on I for each K 0 . Clearly I is a positive instance
S
of the problem for K iff I is a positive instance of the problem for one of the K 0 .
J

A. Amarilli and C. Paperman

I Corollary 4.2. For any finite family of languages K, if CTS[K 0 ] is in NL for each K 0 ∈ K,
S
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 a1 A∗2 a2 · · · an A∗n+1 with ai ∈ A and Ai ⊆ A for
all i. In particular, we may have Ai = ∅ 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:
I Theorem 4.3. For any monomial language K, the problem CTS[K] is in NL.
Proof sketch. Let K be A∗1 a1 A∗2 a2 · · · A∗n an A∗n+1 . We can first guess in NL the vertices
v1 , . . . , vn to which the a1 , . . . , an are mapped, so all that remains is to check, for each such
guess, whether we can match the remaining vertices to the Ai . 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, 27]), we check that the descendants of the last element vn are all
in A∗n+1 , and then we compute the set S of vertices that must be enumerated before vn : they
are the ancestors of the vi , and the ancestors of any vertex labeled by a letter in A \ An+1 .
We then use the induction hypothesis to check in NL whether S has a topological sort that
achieves a word in A∗1 a1 . . . A∗n−1 an−1 A∗n .
J
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:
I 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 v1 6= v2 such that λ(v1 ) = λ(v2 ) = a. If yes, we conclude that G is a positive instance,
as we can clearly achieve K by enumerating v1 and v2 contiguously.
If there are no two such vertices, we check in NL if there are two comparable a-labeled
vertices v1 6= v2 that can be enumerated contiguously, i.e., there is an edge v1 → v2 but no
vertex w that is between v1 and v2 , i.e., is a descendant of v1 and an ancestor of v2 . If there
are two such vertices v1 and v2 , 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.
J

XX:7

XX:8

Constrained Topological Sorting

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∗ ai A∗ for i > 2. However, following the
intuition of this proof, we can show the tractability of a similar kind of regular languages:
I Proposition 4.5. Let A := {a, b}, let K 0 be a regular language, let i ∈ N, and let
K := K 0 + A∗ (ai + bi )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∗ ai A∗ or A∗ bi 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.
J
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.
I Proposition 4.6. Let A := {a, b} and K := (aa + b)∗ . The problem CSh[K] is in NL.
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 (ai + 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.
J

5

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].
I Proposition 5.1. We have the following counterexamples to closure:
Quotient. There
a word u ∈ A∗ and a regular language K such that CSh[K] is in
 −1 exists

NL but CSh u K is NP-hard.

A. Amarilli and C. Paperman

Intersection. There exists two regular languages K1 and K2 such that CTS[K1 ] and
CTS[K2 ] are both in PTIME but CSh[K1 ∩ K2 ] 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 K1 := (ab)∗ ( + bA∗ ) and K2 := (ab)∗ ( + aaA∗ ). We have
K1 ∩ K2 = (ab)∗ , but CSh[K1 ] and CSh[K2 ] 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∗ (a3 + b3 )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.
J
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, u1 · · · un+1 ) := δ(δ(q, u1 ), u2 · · · un+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.

XX:9

XX:10

Constrained Topological Sorting

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
{(i1 , F1 ), . . . , (ik , Fk )} of initial-final state pairs, where ij ∈ Q and Fj ⊆ 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, δ, ij , Fj ), i.e., δ(ij , λ(σ)) ∈ Fj . 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, un ) = 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:
I 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 [29]): S is tractable iff T (S) is in DA, and
it is PSPACE-complete [30] 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 [29]): 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 [28]): 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.
J

A. Amarilli and C. Paperman

6

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 [26] (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 [30]. Our main result is then:
I 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 [26] 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
K1 a1 · · · Kn an Kn+1 where, for all i, we have ai ∈ A and Ki is a group language over some
alphabet Ai ⊆ A. Note that district group monomials are more expressive than the group
monomials defined in earlier work [24] (which set Ai := 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 Ai ,
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:
I 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 Hrare , that occur in a
constant number of strings, and the frequent elements Hfreq , 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 Hfreq occuring many times in C. Now, as topological sorts
can choose any order on C, they can intuitively achieve all elements of the subgroup hHfreq i
generated by Hfreq , except that they cannot change “commutative information”, e.g., the
parity of the number of elements. We formalize the notion of “commutative information”

XX:11

XX:12

Constrained Topological Sorting

using relational morphisms, and prove an antichain lemma that captures our intuition that
all elements of hHfreq i 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 hHfreq i 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.
J
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+ .
I 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 Ca
and Cb 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 Ca and Cb ). The missing proof
ingredient seems to be an analogue of Dilworth’s theorem for labeled DAGs (see also [3]).

7

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∗ ai A∗ for i > 2? Does Proposition 4.6
extend to (ai + 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. Amarilli and C. Paperman

References
1
2
3
4
5
6
7
8
9
10

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Kunal Agrawal, Jing Li, Kefu Lu, and Benjamin Moseley. Scheduling parallel DAG jobs
online to minimize average flow time. In Proc. SODA, 2016.
J. Almeida. Finite Semigroups and Universal Algebra. Series in algebra. World Scientific,
1994.
Antoine Amarilli. Generalization of Dilworth’s theorem for labeled DAGs, 2016. https:
//cstheory.stackexchange.com/q/37062.
Antoine Amarilli, M. Lamine Ba, Daniel Deutch, and Pierre Senellart. Possible and certain
answers for queries over order-incomplete data. In Proc. TIME, 2017.
Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. JACM, 57(2):9, 2010.
Manuel Bodirsky, Barnaby Martin, and Antoine Mottet. Discrete temporal constraint
satisfaction problems, 2015. arXiv:1503.08572.
Sam Buss and Michael Soltys. Unshuffling a square is NP-hard. JCSS, 80(4), 2014.
Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 1950.
Joey Eremondi, Oscar H Ibarra, and Ian McQuillan. On the complexity and decidability
of some problems involving shuffle, 2016. arXiv:1606.01199.
Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP
and constraint satisfaction: A study through Datalog and group theory. SIAM J. Comput.,
28(1), 1998.
M. R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory
of NP-Completeness. W. H. Freeman and Company, 1979.
Michael R. Garey and David S. Johnson. Complexity results for multiprocessor scheduling
under resource constraints. SIAM J. Comput, 1975.
M. Holcombe. Algebraic Automata Theory. Cambridge Studies in Advanced Mathematics.
Cambridge University Press, 1982.
Neil Immerman. Nondeterministic space is closed under complementation. SIAM J. Comput, 17(5), 1988.
David S. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms,
5(2), 1984.
John Kececioglu and Dan Gusfield. Reconstructing a history of recombinations from a set
of sequences. Discrete Applied Mathematics, 88(1-3), 1998.
Takayuki Kimura. An algebraic system for process structuring and interprocess communication. In Proc. STOC, 1976.
Anthony Mansfield. On the computational complexity of a merge recognition problem.
Discrete Applied Mathematics, 5(1), 1983.
Robert McNaughton and Seymour Papert. Counter-Free Automata. MIT Press, 1971.
W. F. Ogden, W. E. Riddle, and W.C. Rounds. Complexity of expressions allowing concurrency. In Proc. POPL, 1978.
Charles Paperman. Semigroup online, 2018. https://www.paperman.name/semigroup/.
Jean-Éric Pin. Syntactic semigroups. In Handbook of formal languages, Vol. 1, pages
679–746. Springer, Berlin, 1997.
Jean-Éric Pin and Pascal Weil. Polynominal closure and unambiguous product. TCS, 30(4),
1997.
Jean-Éric Pin. Polynomial closure of group languages and open sets of the Hall topology.
TCS, 169(2), 1996.
Romeo Rizzi and Stéphane Vialette. On recognizing words that are squares for the shuffle
product. TCS, 2017.

XX:13

XX:14

Constrained Topological Sorting

26
27
28
29
30
31

M. P. Schützenberger. Sur le produit de concaténation non ambigu. Semigroup forum, 13,
1976/77.
Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata.
Acta Informatica, 26(3), 1988.
Pascal Tesson and Denis Thérien. The computing power of programs over finite monoids.
J. Autom. Lang. Comb., 7(2), 2001.
Pascal Tesson and Denis Thérien. Diamonds are forever: the variety DA. Semigroups,
algorithms, automata and languages, 1, 2002.
Denis Thérien and Thomas Wilke. Over words, two variables are as powerful as one
quantifier alternation. In Proc. STOC, 1998.
Manfred K. Warmuth and David Haussler. On the complexity of iterated shuffle. JCSS,
28(3), 1984.

A. Amarilli and C. Paperman

A

Proofs for Section 2 (Problem Statement and Main Results)

I Proposition 2.2. For any language K, the problems CTS[K] and CSh[K] are in NPK .
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.
J

B

Proofs for Section 3 (Hardness Results)

B.1

Proof of Proposition 3.1: Direct Hardness Result

I Proposition 3.1. Let K0 := (a1 a2 + b1 b2 )∗ . The problem CSh[K0 ] 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 K0 , 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 w1 and
from U2 , and the definition of K0 ensures that the two letters in w and U corresponding to
the enumerated letters in w1 and U2 must have the same label in {a, b}. Hence, considering
the restriction σ 0 of σ to U2 , the interleaving of U that corresponds to σ 0 witnesses that
w ∈ (U ).
Conversely, if w ∈ (U ), starting from a witnessing topological sort σ 0 of U2 , it is clear
that we can construct a topological sort σ of I that achieves K0 , by enumerating the elements
of w1 alternatively with the elements of U2 according to σ 0 . This shows correctness and
concludes the proof.
J



B.2



Proof of Lemma 3.2: Initial Hard Family

I Lemma 3.2. ([WH84], Lemma 3.2) Let K := {(ai bi )∗ | 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:
P

1
given a tuple E of 3m positive integers written in unary, such that B := m
n
i
1≤i≤3m
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 an bn , and we choose the target language K in K to be (aB bB )∗ ,
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.
J

XX:15

XX:16

Constrained Topological Sorting

B.3

Proof of Theorem 3.5: Shuffle Reduction

I Theorem 3.5. For any regular language family K and language K 0 , if K shuffle-reduces
to K 0 then we can reduce in PTIME from CTS[K] to CTS[K 0 ], and from CSh[K] to CSh[K 0 ].
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 0 . Let K be the input language of K,
and let I be an input instance of the CSh-problem for K. Let (fnK ) be the filter sequence
for K and K 0 . Letting n := |I|, let us call I 0 the instance of the CSh-problem for K 0 that
contains I and a separate string labeled with fnK : by our computability hypothesis on (fnK ),
this is computable in PTIME. We now argue that I 0 is a positive instance to the CSh-problem
for K 0 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 (fnK ) we have (v fnK ) ∩ K 0 6= ∅. Hence, let v 0 be an element of this set. It is
in v fnK , so it can be obtained as a topological sort of I 0 by shuffling fnK with σ, and it is
in K 0 so it witnesses that I 0 is a positive instance to the CSh-problem for K 0 .
Conversely, if there is a topological sort σ 0 of I 0 achieving a word v 0 ∈ K 0 , then σ 0 defines
a topological sort σ of I achieving a word v such that v 0 ∈ v fn . As we have |v| = n
by definition, and v 0 witnesses that v fn 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.
J









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 fn is computable by a logspace transducer.

B.4

Proof of Theorem 3.6: Hardness of (ab)∗

I Theorem 3.6. The problem CSh[(ab)∗ ] (hence CTS[(ab)∗ ]) is NP-hard.
Proof. Let K be the family of regular languages defined in Lemma 3.2. We define a filter
sequence (fnB ) for each such language KB = (aB bB )∗ 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 KB
B
:= (bB aB ab)n . For other word
having the specified length. For such lengths, we define f2Bn
0
0
lengths n ∈ N, for which there are no words in KB , we define fnB0 := an +1 : this ensures that
we can never obtain a word of KB by interleaving n0 symbols with fnB0 , which is correct. The
filter sequence is clearly computable in PTIME. So we only have to show that, for all n ∈ N,
B
the word f2Bn
is a filter sequence for word length 2Bn.
To do so, fix n ∈ N, and consider a word v of length 2Bn in KB . For the forward direction,
if v is (aB bB )n which is the only word of KB of length 2Bn, then we can interleave v with
B
f2Bn
to form a word of (ab)∗ by inserting the letters in bold: ((ab)B (ab)B ab)n .
Conversely, for the backward direction, we are forced to insert at least these letters. More
B
precisely, considering an interleaving of f2Bn
with a word v that achieves a word w of (ab)∗ ,
we know that, in each of the n occurrences of bB aB 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

A. Amarilli and C. Paperman

XX:17

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
B
B
that (v f2Bn
) ∩ (ab)∗ is non-empty iff v = (aB bB )n . This shows that f2Bn
is indeed a
∗
filter sequence, which establishes that CSh[(ab) ] is NP-hard thanks to Theorem 3.5 and
Lemma 3.2.
J



B.5

Hardness Proofs for Other Languages

I Proposition 3.7. Let u ∈ A∗ such that |u|a > 0 and |u|b > 0 for a 6= 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(u0 )∗ y, where u0 := yx;
this ensures that the first and last letters of u0 are different.
We now show that (ab)∗ shuffle-reduces to u∗ , by constructing a filter sequence (fn ).
To this end, we let u0−a be a word obtained by removing some a in u0 , and u0−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 f2n+1 for n ∈ N as something that can never be in u∗ even when
inserting 2n + 1 arbitrary symbols, e.g., f2n+1 := a(2n+1)×|u|+1 , which is clearly computable
in PTIME.
For even numbers, we define f2n := x(u0 u0−a u0 u0−b u0 )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 f2n to obtain a word
of u∗ by inserting each a of v in u0−a and each b of v in u0−b . Conversely, for an interleaving
of any word with f2n to yield a word of u∗ , we know that we must at least insert one a
in or around each u0−a , and one b in or around each u0−b . Specifically, consider a word v
and consider a candidate interleaving w ∈ (v f2n ) ∩ u∗ and assume by contradiction that
there is a factor u0−a of f2n such that w did not insert any a from v within this factor or
adjacently to this factor (the case of u0−b -factors is symmetric). Now, consider the factor
w0 of w that contains this factor u0−a , the neighboring letter from the beginning or end
of u0 where we take one such letter which is not a (which is always possible by hypothesis
on u0 ), and all inserted elements (which by hypothesis are all b’s). The number of a’s in the
factor w0 is |u0−a |a , which is |u|a − 1, but |w0 | ≥ |u|, so, by our preliminary observation, this
is impossible because we had assumed that w ∈ u∗ . Hence, indeed, we must insert one a
in u0−a or adjacently to it, and likewise for the u0−b : these insertions are distinct, and they
use up all letters of v, so for f2n v to intersect u∗ nontrivially, the only possibility is that
v = (ab)n . This shows that (fn ) is indeed a filter sequence, and allows us to conclude by
Theorem 3.5 and Theorem 3.6.
J





I Proposition 3.8. Let L := (aa + bb)∗ . The problem CSh[L] (hence CTS[L]) is NP-hard.
Proof. We show a shuffle reduction from K := (ab)∗ to K 0 := (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.

XX:18

Constrained Topological Sorting

For all even n ∈ N we set fn := (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 fn to form (aabb)n/2 .
For the backwards direction, fix n ∈ N, take v ∈ A∗ such that |v| = n, and assume
that (v fn ) ∩ K 0 contains some word w. For each 1 ≤ i ≤ n, consider the position where
the i-th letter of fn occurs in w, and call ϕi the maximal factor of w which contains the
i-th letter of fn 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 fn 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 fn ,
namely, the i-th letter of fn : the others were inserted from v. Further, by definition of K 0 ,
the ϕi must all be of even length. This means that f1 contains at least one inserted a, that
f2 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 f2n+1 to be something
that can never be in K 0 even when inserting n arbitrary symbols. For instance, we can
take f2n+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.
J



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:
I 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 xn ≤K x2n ≤K xn , we have xn ≥K xn yxn .
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

A. Amarilli and C. Paperman

right-hand-side of the implication is wrong: we have x1 = ab in K, so we can take u = v = 
in the definition of the syntactic order, however we then have x1 yx1 = abbabab which is not
in K, so we have shown that xn 6≥K xn yxn .
J

C.2

Proof of Theorem 4.3: Tractability for Monomials

I Theorem 4.3. For any monomial language K, the problem CTS[K] is in NL.
Proof. Let K be A∗1 a1 A∗2 a2 · · · A∗n an A∗n+1 . First, we can guess in NL the vertices v1 , . . . , vn
of G = (V, E, λ) to which the a1 , . . . , an are associated, and verify that indeed we have
λ(vi ) = ai 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 ai in our target language, there is exactly one vi in the input instance such
that λ(vi ) = ai .
We now prove by induction on n that, for any monomial K = A∗1 a1 · · · A∗n an 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 K = A∗1 a1 A∗2 · · · an+1 A∗n+2 and
K 0 = A∗1 a1 A∗2 · · · an A∗n+1 . Let G = (V, E, λ) be the input A-DAG satisfying the fresh pivot
condition, and let v1 , . . . , vn+1 be the uniquely defined vertices matched to a1 , . . . , an+1 . We
define the sub-A-DAG G0 to be the restriction of G on the following vertex set V 0 :
the ancestors of the v1 , . . . , vn , including v1 , . . . , vn ;
the ancestors of vn+1 except vn+1 itself;
for each w incomparable to vn+1 such that λ(w) ∈
/ An+2 , the ancestors of w (including
itself).
We now claim the following:
Claim. G is a positive instance to K iff all descendants z of vn+1 are such that λ(z) ∈ An+2
and G0 is a positive instance to K 0 .
Note that G0 is always computable in NL, and the condition on the descendants of vn+1
can be checked in co-NL, hence in NL by the Immerman-Szelepcsényi theorem [Imm88, Sze88].
Hence, once this claim is proved, we have an NL algorithm for CTS[K] by running the NL
algorithm on the descendants of vn+1 and running the algorithm given by the induction
hypothesis on G0 , 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 σ 0 of G0 satisfying K 0 which exists by assumption, the vertex vn+1 which
achieves an+1 , and any topological sort of G \ (G0 ∪ {vn+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 vn+1 has a label in a1 , . . . , an , i.e,. vn+1 is not an
ancestor of any vi ; in particular vn+1 is not in V 0 . However, by definition of G0 , all ancestors
of vn+1 are in V 0 . So we know that we can indeed concatenate σ 0 , vn+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 σ 0 achieves K 0 , vn+1 achieves an+1 , and by
assumption all remaining vertices are either descendants of vn+1 so their label is in An+2 , or
they are incomparable to vn+1 so their label must be in An+2 (they would be in G0 otherwise).
Thus, σ is a topological sort of G that achieves K, establishing the backward implication.

XX:19

XX:20

Constrained Topological Sorting

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

C.3

Proof of Proposition 4.5: Tractability Based on Width

I Proposition 4.5. Let A := {a, b}, let K 0 be a regular language, let i ∈ N, and let
K := K 0 + A∗ (ai + bi )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:
I 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.
J
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 0 ) be
its transitive closure. A chain partition of G is a partition V1 t · · · t Vn of V , such that,
for all 1 ≤ i ≤ n, the restriction of E 0 to Vi × Vi is the transitive closure of a directed path

A. Amarilli and C. Paperman

graph: equivalently, for each pair of vertices v =
6 v 0 of Vi , either v has a directed path to v 0
0
in E or v has a directed path to v in E. We call each of the Vi 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 Vi and Vj for i =
6 j. The width of a chain partition is the number of chains that it
contains. The following is then known from partial order theory:
I 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 Vi := {v ∈ V | χ(v) = i}, then V1 t · · · t Vk 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 v1 < · · · < 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 χ(v1 ) · · · χ(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 0 , and there is no z ∈ V such that χ0 (z) = c and the edges v → z and z → next(v) are
in E 0 . 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 0 . We can now claim:

XX:21

XX:22

Constrained Topological Sorting

I Lemma C.4. For any input to the functions next and first, we can evaluate them in space
O(k log n).
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 = (v1 , . . . , vk ), where each vi
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 vi the edge w → vi is in E 0 , 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 χ(vi ) = i for all 1 ≤ i ≤ k such that vi 6= ⊥. One
useful lemma will be the following:
I 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 = (v1 , . . . , vk ), 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 vi → v
is in E 0 or vi = ⊥, we check whether the configuration Xi obtained by replacing vi by v
is continuable. We pick the smallest i such that it is, and continue the algorithm with Xi :
specifically, we guess a suitable i, and guess in co-NL that there is no i0 < i which is suitable:
this is still in NL overall, thanks to the Immerman-Szelepcsényi theorem [Imm88, 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 0 such that all of its ancestors are in S and z is an ancestor of z 0 , 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

A. Amarilli and C. Paperman

at the previous step of the algorithm. Now, as X = (v1 , . . . vk ) 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) 6= ⊥, 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 0 . 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.
J
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.
J
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 = (v1 , . . . , vk ) such that each vi 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 Xi defined
as follows: if vi = ⊥, then we replace vi in Xi by vi0 := first(vi ); if vi 6= ⊥, then we replace vi
in Xi by vi0 := next(vi ) if it is different from >; otherwise we cannot choose this value of i.
We also cannot choose a value of i when the vi0 that we have defined cannot be enumerated
yet, i.e., if it is not the case that all strict ancestors of vi0 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 0 such that (q, λ(vi0 ), q 0 ) ∈ δ, nondeterministically chosen. Intuitively,

XX:23

XX:24

Constrained Topological Sorting

this means that the automaton processes the letter which is the label of the new element vi0
which is read along the chain i.
The algorithm concludes when we can no longer perform a step, meaning that vi =
6 ⊥ and
next(vi ) = > 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 vi0 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.
J

C.4

Proof of Proposition 4.6: Other Tractable Case

I Proposition 4.6. Let A := {a, b} and K := (aa + b)∗ . The problem CSh[K] is in NL.
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.
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

A. Amarilli and C. Paperman

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 0 be the result of removing these two elements.
If I 0 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 0 , C 00 be the strings with the largest a-weight (in terms
of unenumerated elements) and let n ≥ n0 ≥ n00 be their respective a-weights. After step 2,
the a-weights are n − 1, n0 − 1, and n00 . It is clear that, as condition (**) held of C and C 0
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 00 , which has the largest a-weight in terms of non-enumerated elements. There are
three cases, depending on the relationship of n00 to n.
If n00 < n − 1, then as (**) is still satisfied for C after the step and the a-weight of C 00 is
still smaller than C after the step, then (**) is satisfied for C 00 too.
If n00 = n − 1, then after performing the step, C and C 00 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 n00 = n, then we have n00 = n0 = n. Now, the only problematic case would be if, after
performing the step, n00 were strictly greater than the a-weight of all other strings, in
particular, we would have n00 > (n − 1) + (n0 − 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

XX:25

XX:26

Constrained Topological Sorting

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 0 and show the
condition. If C 0 = 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 00 than C was to bring it down to n or n + 1, in which case C 00
suffices to witness that (**) is satisfied for C. If C 0 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 0 . This establishes that (**)
now holds after the simplifications, which concludes the proof.
J

D
D.1

Proofs for Section 5 (A Coarser Dichotomy Theorem)
Proofs of Proposition 5.1: Closure Counterexamples

I Proposition 5.1. We have the following counterexamples to closure:
Quotient. There
a word u ∈ A∗ and a regular language K such that CSh[K] is in
 −1 exists

NL but CSh u K is NP-hard.
Intersection. There exists two regular languages K1 and K2 such that CTS[K1 ] and
CTS[K2 ] are both in PTIME but CSh[K1 ∩ K2 ] 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:
∗
I Proposition D.1. There exists a word u ∈
and
 A
 a regular language K such that CSh[K]
−1
∗
−1
is tractable but u K = (ab) , so that CSh u 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

A. Amarilli and C. Paperman

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.
J
However, we point out that the tractable languages for the CTS-problem are closed under
quotient:
∗
I Proposition D.2. For any
 word u ∈ A and regular language K, there is an logspace
−1
reduction from CTS u 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 G0 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 G0 achieving K iff there is a topological sort of G achieving
u−1 K, which concludes the proof.
J
Second, we illustrate that tractable languages are not closed under the intersection
operator, for both problems:
I Proposition D.3. There exists two regular languages K1 and K2 such that CTS[K1 ] and
CTS[K2 ] are both in PTIME, but K1 ∩ K2 = (ab)∗ , so that CSh[K1 ∩ K2 ] is NP-hard by
Theorem 3.6.
Note that we do not show that CTS[K1 ] and CTS[K2 ] are in NL, although we conjecture
that this should hold.
Proof of Proposition D.3. We fix A := {a, b} and take K1 = (ab)∗ ( + bA∗ ) and K2 =
(ab)∗ ( + aaA∗ ). It is clear that K1 ∩ K2 = (ab)∗ , so we only need to show that CTS[K1 ]
and CTS[K2 ] are tractable. Now, observe that a−1 K1 b−1 = (ba)∗ ( + bbA∗ ), which is the
result of swapping the symbols a and b in K2 . Hence, if we establish that CTS[K1 ] is in
PTIME, then by Proposition D.2, as PTIME-membership is clearly preserved by renaming
the symbols, we have also shown that CTS[K2 ] is in PTIME. So we focus on K1 .
We will show a greedy algorithm in PTIME to solve CTS[K1 ], 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 K1 .
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 K1 ;
enumerating an a is forbidden;
enumerating a b allows us to move back to state α.
We accordingly design the algorithm as follows:

XX:27

XX:28

Constrained Topological Sorting

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 0 . However, in this case, we can modify σ to pick v 0 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 K1 ).

A. Amarilli and C. Paperman

Now, if σ does not enumerate w immediately after v (subcase 2), then let w0 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 w0 . We modify σ to enumerate w instead of w0 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 w0 ) 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[K1 ] is in
NL, but we do not know how this can be shown.
J
Third, we show that tractable languages are not closed under complement:
I 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)∗ . J
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:
I 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∗ (a3 + b3 )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)∗ .
J

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) = fu 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ω = x2ω .
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:
I Theorem D.6 ([TT02], Theorem 5 and Theorem 11). Let K be a regular language of
A∗ . The following conditions are equivalent:

XX:29

XX:30

Constrained Topological Sorting

K is an union of unambiguous monomials, i.e., of monomials K = A∗1 a1 · · · A∗n an A∗n+1
such that every word u ∈ K has a unique decomposition u1 a1 · · · un an un+1 where ui ∈ 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:
I 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 BA2 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].
J
We are now ready to state and prove our dichotomy theorem:
I 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 {(i1 , F1 ), . . . , (ik , Fk )} 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, (i1 , F1 ), . . . , (ik , Fk )) be an instance of the semiautomaton CTS-problem and
let Kj be the language recognized by the automaton (Q, A, δ, ij , Fj ) for all 1 ≤ j ≤ k. We
T
must determine whether G = (V, E, λ) has a topological sort in K := j Kj . 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 0 := {u ∈ M ∗ | ψ(u) = η(K)}. In other words,
K 0 = ψ −1 (η(K)), so K 0 is recognized by M which is a monoid in DA: by Theorem D.6, we
know that K 0 is a union of monomials.
Our goal is then to reduce to CTS[K 0 ]. Formally, we construct from the A∗ -DAG
G = (V, E, λ) the M -DAG G0 = (V, E, λ0 ) where we define λ0 (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 G0 is a positive instance to

A. Amarilli and C. Paperman

CTS[K 0 ]. This will allow us to conclude, because, by Theorem 4.3 and Corollary 4.2, we
know that CTS[K 0 ] 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 λ0 (σ) achieved by σ in G0 is in K 0 . In other
words, letting w1 · · · wn := λ(σ), we must show that w1 · · · wn ∈ K iff η(w1 ) · · · η(wn ) ∈ K 0 .
The forward direction is immediate by applying the morphism η. For the backward direction,
we have ψ(η(w1 ) · · · η(wn ))) ∈ η(K), and the left-hand-side is η(w1 ) · · · η(wn ), which is
η(w1 · · · wk ) because η is a morphism, so applying η −1 concludes. We have shown the
equivalence, so we can reduce in NL to CTS[K 0 ] with K 0 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 fu = x and fv = 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 G0 = (V, E, λ0 )
where we define λ0 (w) := θ(λ(w)) for all w ∈ V . For each function f ∈ P , let us define an instance If of the semiautomaton CSh-problem of S by If = (G0 , (q1 , {f (q1 )}), . . . , (qn , {f (qn )}))
where (qi )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 If iff fz = f in M . This
construction is in NL. Let us show that G is a positive instance to CSh[H] iff one of the If 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 λ0 (σ) = θ(z1 ) · · · θ(zn ) = θ(z1 · · · zn )
because θ is a morphism. As z ∈ H and θ(H) = P , we know that f := θ(z1 · · · zn ) is in P .
Hence, consider the instance If . We know that fz = f by definition, hence σ witnesses that
If has a suitable topological sort.
For the backward direction, assume that there is f ∈ P such that we have a solution of
If . This means that there is a topological sort σ of (V, E) such that the word z := λ0 (σ)
achieved by σ in G0 is such that fz = 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.
J

E
E.1

Proofs for Section 6 (Lifting the Counter-Free Assumption for
CSh)
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

XX:31

XX:32

Constrained Topological Sorting

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:
I 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 = K1 a1 · · · Kn an Kn+1 such that every word u ∈ K has a unique decomposition
u1 a1 · · · un an un+1 where ui ∈ Ki 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:
I 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 Arare and frequent letters Afreq , which we call a rare–frequent partition.
This will ensure that the rare letters Arare only occur in constantly many input strings (called
the rare strings), and the frequent letters Afreq 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 Afreq . 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 Afreq .
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:
I Definition E.3. Write the alphabet A as a1 , . . . , ak in some fixed order. The Parikh image
of a word w ∈ A∗ is PI(w) := (|w|a1 , . . . , |w|ak ) ∈ Nk , 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}.

A. Amarilli and C. Paperman

The Parikh image PI(G) of an A-DAG G = (V, E, λ) is (|G|a1 , . . . , |G|ak ), with each |G|ai
being |{v ∈ V | λ(v) = ai }|. 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.
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 Arare . We can simply look at the
constant number of strings that contain a letter of Arare , 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 Afreq , 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 Arare and Afreq . 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:
I 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 nk such that, for any A-DAG
G = (V, E, λ) with an nk -rich antichain, for any elements g1 , . . . , gk of H, if PI(G) ∈
PI(µ−1 (g1 · · · gk )) then there is a topological sort σ of G decomposable as σ = σ1 · · · σk such
that µ(λ(σi )) = gi 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

XX:33

XX:34

Constrained Topological Sorting

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.
J
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.
I 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 w1 , . . . , wn
of words of A∗ and (n+1)-tuple w00 , . . . , wn0 of words of A∗ , letting u = w00 w1 w10 w2 w20 · · · wn wn0 ,
there exists a set J ⊆ {0, . . . , n} of cardinality at most B such that, letting wj00 for 0 ≤ j ≤ n be
wj0 if j ∈ J and the empty word otherwise, letting v = w000 w1 w100 · · · wn wn00 , we have µ(u) = µ(v)
and µ(w00 · · · wn0 ) = µ(w000 · · · wn00 ).
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 wi0 ). 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.
J
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 = {a1 , . . . , ak }. We let µ : A∗ → H be the syntactic morphism of K, where H
is a finite group generated by the µ(ai ). We consider an instance I = (S1 , . . . , Sn ) to the
CSh-problem, where each Si 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 nk given by this lemma. We will decompose I following a
rare–frequent partition, which we now define:
I Definition E.6. A rare–frequent partition of I consists of a partition of A into rare letters
Arare and frequent letters Afreq , and a partition of the strings into rare strings Srare and
frequent strings Sfreq , where all vertices of Sfreq are labeled with letters of Afreq , and where
Sfreq , when seen as an subinstance of I over the alphabet Afreq , 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:

A. Amarilli and C. Paperman

I Lemma E.7. For any fixed alphabet A of size k, given an input CSh-instance I =
(S1 , . . . , Sn ), we can compute a rare–frequent partition of I in NL, represented as the partition
Afreq t Arare of A and the set of rare strings Srare , such that |Srare | ≤ R · k 2 .
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 Arare = ∅, Afreq = A, Srare = ∅, Sfreq = S, and does the
following until convergence: if a letter a ∈ Afreq occurs in less than R · k strings of Sfreq , then
remove a from Afreq , add a to Arare , remove the ≤ R · k strings that contain a from Sfreq ,
and add them to Srare . 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 Sfreq cannot contain any
letter of Arare and that each letter of Afreq occurs in at least R · k different strings of Sfreq . By
picking R strings of Sfreq for each letter of Afreq in a way that does not overlap, we see that
Sfreq contains an R-rich antichain for the alphabet Afreq . Hence, a suitable rare–frequent
partition exists.
To construct the rare–frequent partition in NL, simply guess the partition Arare t Afreq
of A, guess the set Srare of rare strings of size ≤ R·k 2 (which is constant), guess R occurrences
for each letter of Afreq , check that they are all in different strings and that they are not
in strings of Srare , and check that the strings which are not in Srare contain only frequent
letters.
J
Hence, we assume that we have computed in NL a rare–frequent partition of I, given
by Arare , Afreq , Srare , and (implicitly) Sfreq . We write Hfreq for the subgroup of H equal to
µ(A∗freq ), i.e., the subgroup spanned by Afreq . 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 Srare , with some insertions of a
constant number of elements from Hfreq 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 Sfreq , 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.
J
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

XX:35

XX:36

Constrained Topological Sorting

(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:
I 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 p2ω = pω for every p ∈ N . (Such an idempotent power exists: indeed, for
every p in N , there exists k such that pk = p2k , 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 0 is a map from
M to the powerset P(M 0 ) of M 0 , such that for all m ∈ M we have τ (m) 6= ∅, and for all
m, m0 ∈ M , we have τ (m) · τ (m0 ) ⊆ τ (mm0 ), where we extend the product operator of M 0 to
the powerset monoid of M 0 in the expected way, that is, S · S 0 = {g · g 0 | g ∈ S, g 0 ∈ S 0 }. For
any surjective morphism η : A∗ → M and morphism µ : A∗ → M 0 , the map m 7→ µ(η −1 (m))
is a relational morphism. We write τ : M → M 0 if τ is a relational morphism between M
and M 0 .
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
r1 , . . . , rn such that p = sr11 · · · srnn , where n = |S|, and ri ≥ ω for all 1 ≤ i ≤ n.
The notion of fully recurrent elements is motivated by the following lemma:
I 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)| = |τ (ri )| for any i ≥ 1. This suffices to conclude the lemma, because for any
fully recurrent elements p and q, we have pω = q ω . Indeed, writing p = sr11 · · · srnn , we have
r1
ω rn
ω
pω = (sω
= sω
1 ) · · · (sn )
1 · · · sn , and similarly for q. This allows us to conclude from (*)
ω
because we have |τ (p)| = |τ (p )| = |τ (q ω )| = |τ (q)|.
So we simply show claim (*). Let r be a fully recurrent element, and let us study the
sequence (xi ) defined by xi := |τ (ri )| for all i ≥ 1. We must show that the sequence (xi ) 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 xb = x1 . Parts (i) and (ii) clearly imply that
the sequence is constant, which establishes (*).

A. Amarilli and C. Paperman

For part (i), we show that |τ (ri )| ≤ |τ (ri+1 )| for all i ≥ 1. By definition of relational
morphisms, we have τ (ri )τ (r) ⊆ τ (ri+1 ). Now, remembering that the empty set is not in
the image of a relational morphism, pick any x ∈ τ (r). We know that τ (ri ) · {x} ⊆ τ (ri )τ (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 |τ (ri )| = |τ (ri ) · {x}| ≤ |τ (ri )τ (r)| ≤ |τ (ri+1 )|. This shows part (i).
We now show part (ii). To do so, let us show first that rω+1 = r. Indeed, write r =
r1
ri −ω ω
2
s1 · · · srnn , and we simply conclude using the fact that sri i +ω = sri i −ω (sω
si = sri i .
i ) = si
This implies that we have rjω+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.
J
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 nk such that, for any A-DAG G =
(V, E, λ) with an nk -rich antichain, for any elements g1 , . . . , gk of H, if PI(G) ∈
PI(µ−1 (g1 · · · gk )) then there is a topological sort σ of G decomposable as σ = σ1 · · · σk
such that µ(λ(σi )) = gi 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 γ = maxg∈H minu∈µ−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 g1 , . . . , gk in the statement of the
lemma is equivalent to Comµ (G) ∈ Comµ (µ−1 (g1 · · · gk )). Indeed, the forward implication
is immediate, and the converse holds because Comµ recognizes CCl(µ−1 (g1 · · · gk )), so the
rephrased condition implies that CCl(G) ∈ CCl(µ−1 (g1 · · · gk )), which clearly implies the
original condition. Further, by composing with τ and simplifying using the definition of τ ,
the condition rephrases to g1 · · · gk ∈ τ (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
:=
nk
ω + (k − 1)γ. Let us first show the base case for k = 1 and nk = ω. 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 g1 such that PI(G) ∈ PI(µ−1 (g1 )), we have g1 ∈ τ (Comµ (G))
as we explained above, so g1 ∈ T and there is a topological sort σ := σ1 of G such that
µ(λ(σ1 )) = g1 . 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− t C t 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−

XX:37

XX:38

Constrained Topological Sorting

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 0 := µ(σ − ) · τ (Comµ (C)) · µ(σ + ) is a subset of T , so |T 0 | ≤ |T |. Let
us now write sa := Comµ (a) for each letter a ∈ A. We can write Comµ (C) = Πa∈A siaa ,
where ia is the number of vertices labeled by a in C. As C is ω-rich, we have ia ≥ ω. 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 0 |. We have thus shown that |τ (Comµ (G))| = |T 0 | ≤ |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.
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 nk+1 -rich antichain: as in the base case we expand
it to a maximal such antichain, denote it by C, partition G as G− t C t G+ , and let σ −
and σ + be arbitrary topological sorts of G− and G+ respectively. Let us choose elements
g1 , . . . , gk+1 of H such that g1 · · · gk+1 ∈ τ (Comµ (G)): remember that this implies that
g1 · · · gk+1 ∈ τ (Comµ (G)).
Now, let us consider g 0 := gk+1 · µ(σ + )−1 . Let ug0 ∈ A∗ be a word that realises the
minimum in the definition of γ, and let Cg0 be a subset of C whose elements are labeled with
the letters of ug0 . As C is nk+1 -rich, we can find such a subset, and further C \ Cg0 is still a
((k − 1)γ + ω)-rich antichain, i.e., an nk -rich antichain. Further, the definition of Cg0 ensures
that it has a topological sort σ 0 that realizes the word ug0 , so that µ(σ 0 ) = g 0 . By composing
it with σ + , we can then construct σ 0 σ + , which is a topological sort of G00 t Cg0 t G+ such
that µ(λ(σ 0 σ + )) = gk+1 .
We now wish to apply the induction hypothesis for g1 , . . . , gk on the subinstance G0 :=
−
G t (C \ Cg0 ), which still has a nk -rich antichain. To do so, we must check that PI(G0 ) ∈
PI(µ−1 (g1 · · · gk )), which as we argued is equivalent to g1 · · · gk ∈ τ (Comµ (G0 )). As G is the
disjoint union of G0 and G00 , we have Comµ (G) = Comµ (G0 )Comµ (G00 ), so by composing
by τ and applying the definition of a relational morphism we have:
τ (Comµ (G)) ⊆ τ (Comµ (G0 )Comµ (G00 ))
Now, as both G and G0 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µ (G0 )|. Remember now that σ 0 σ + is a topological sort of G00
such that µ(λ(σ 0 σ + )) = gk+1 . Hence, gk+1 ∈ τ (Comµ (G00 )). Now, as gk+1 acts bijectively on τ (Comµ (G0 )) in the group H, we deduce that τ (Comµ (G)) = τ (Comµ (G0 ))gk+1 .
Now, since we have g1 · · · gk+1 ∈ τ (Comµ (G)) by hypothesis, we deduce that indeed
g1 · · · gk ∈ τ (Comµ (G0 )), so we can apply the induction hypothesis.
Hence, we do so and obtain a topological sort σ1 , . . . , σk of G0 such that µ(λ(σi )) = gi
for each i ∈ {1, . . . , k}. Now, letting σk+1 := σ 0 σ + , it is clear that σ1 , . . . , σk , σk+1 is a
topological sort of G, and we have µ(λ(σ 0 σ + )) = gk+1 , so we have shown the induction
hypothesis. This concludes the proof.
J

E.4

Proof of Lemma E.5: Insertion Lemma

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

A. Amarilli and C. Paperman

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 w1 , . . . , wn of words
of A∗ and (n + 1)-tuple w00 , . . . , wn0 of words of A∗ , letting u = w00 w1 w10 w2 w20 · · · wn wn0 ,
there exists a set J ⊆ {0, . . . , n} of cardinality at most B such that, letting wj00 for
0 ≤ j ≤ n be wj0 if j ∈ J and the empty word otherwise, letting v = w000 w1 w100 · · · wn wn00 ,
we have µ(u) = µ(v) and µ(w00 · · · wn0 ) = µ(w000 · · · wn00 ).
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 v1 , v2 , v3 such that the edges {v1 , v2 }, {v2 , v3 }, and {v1 , v3 }
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 wi
and wi0 . Now, let us construct the complete graph Γ with n vertices v1 , . . . , vn and with
edges colored by triples of elements of H in the following way: the edge between vi and vj
0
00
for i < j is colored with the triple (gi,j , gi,j
, gi,j
), where we define gi,j := µ(wi . . . wj−1 )),
0 :=
0
0
00 :=
0
0
gi,j
µ(wi wi · · · wj−1 wj−1 ), and gi,j
µ(wi · · · wj−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 gl,m = gm,r = gl,r , and
0
0
0
gl,m
= gm,r
= gl,r
. Now, as by definition we have gl,r = gl,m gl,r , this means that we have
2
gl,r = gl,r , and as H is a group we can simplify and deduce that gl,r = e, the neutral element
0
0
of H. We deduce in the same way that gl,r
= e. Hence, we have shown gl,r = gl,r
, which
0
0
means that (*): µ(wl wl · · · wr−1 wr−1 ) = µ(wl · · · wr−1 ). Further, we deduce in the same way
00
that (**) gl,r
= e.
We will now conclude using the induction hypothesis. Let n0 = n − (r − l), and consider
the n0 -tuple w1 , . . . , wl−1 , (wl · · · wr−1 ), wr , · · · , wn of words of A∗ , and the (n0 + 1)-tuple
0
w00 , . . . , wl−1
, wr0 , . . . , wn0 . Using the induction hypothesis for n0 , we deduce the existence of
0
J ⊆ {0, . . . , n0 } of cardinality at most B such that, defining wj000 for all 0 ≤ j ≤ n0 as the
empty word if j ∈
/ J, as wj if j ∈ J 0 and j < l, and as wj+(r−l) if j ∈ J and j ≥ l, letting
0
u0 :=w00 w1 w10 · · · wl−1 wl−1
(wl · · · wr−1 )wr wr0 · · · wn wn0
000
v 0 :=w0000 w1 w100 · · · wl−1 wl−1
(wl · · · wr−1 )wr wr00 · · · wn wn00
0
we have µ(u0 ) = µ(v 0 ), and we have (***) µ(w00 · · · wl−1
wr0 · · · wn0 ) = µ(w0000 · · · wn000 ). Let
us accordingly define J ⊆ {0, . . . , n} by {j | j ∈ J, j < l} t {j + (r − l) | j ∈ J, j ≥ l},
which satisfies the cardinality bound. Let us show that µ(u) = µ(v) and µ(w0 · · · wn ) =
µ(w0000 · · · wn000 ) with v and the wi00 defined from this choice of J. From the equality (*), we
0
know that we can replace (wl · · · wr−1 ) by (wl wl0 · · · wr−1 wr−1
) in u0 without changing its
0
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 wj00 is empty for all j ∈ {l, . . . , r − 1}, so we have
00
wl · · · wr−1 = wl wl00 · · · wr−1 wr−1
); further, from this and our definition of J, we observe that
0
0
v = v , hence µ(v) = µ(v ). We thus deduce that µ(u) = µ(v). Last, we can use (**) to insert
00
in (***) the product wl00 · · · wr−1
, to establish the second required equality. This concludes
the proof.
J

XX:39

XX:40

Constrained Topological Sorting

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 = {a1 , . . . , ak }, let µ : A∗ → H be the
syntactic morphism of K, where H is a finite group generated by the µ(ai ). Consider an
instance I = (S1 , . . . , Sn ) to the CSh-problem, where each Si 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 nk 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 Arare , Afreq , Srare , and (implicitly) Sfreq . We
write Hfreq for the subgroup of H equal to µ(A∗freq ), i.e., the subgroup spanned by Afreq .
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 Srare which can be decomposed as ρ1 · · · ρn , and a sequence
g0 , . . . , gn of elements of Hfreq , such that:
1. g0 µ(λ(ρ1 ))g1 · · · µ(λ(ρn ))gn = g;
2. g0 · · · gn ∈ τ (Comµ (Sfreq ));
3. n < B.
To test this condition (*), we simply nondeterministically guess a sequence S 0 of elements
of Hfreq of size at most B (i.e., a constant) such that the concatenation of its elements is
in τ (Comµ (Sfreq )), add S 0 to Srare , and check whether the resulting CSh instance has a
topological sort using the NL algorithm of Proposition C.2 (because its number of strings
is at most R · k 2 + 1, which is constant): the language to test is µ−1 (g) on the modified
alphabet where the elements of S 0 carry labels in Hfreq and stand for themselves; note that
this clearly yields a group language.
All that remains to show is that condition (*) is equivalent to the existence of a topological
sort of I that achieves g. For the forward direction, assume that condition (*) holds.
Recall that we have defined R := nB . Focus on Sfreq , which has an R-rich antichain
for Afreq , and observe that g0 · · · gn ∈ τ (Comµ (Sfreq ), which is the equivalent rephrasing of
the condition PI(Sfreq ) ∈ PI(µ−1 (g0 · · · gn )), as argued at the beginning of the proof. Using
the antichain lemma (Lemma E.4), we know that there is a topological sort σ = σ0 · · · σn
of Sfreq such that µ(λ(σi )) = gi for each i ∈ {0, . . . , n}. Now, considering the topological
sort ρ1 , . . . , ρn of Srare given by condition (*), it is clear that σ0 ρ1 σ1 · · · ρn σn is a topological
sort of I, built by interleaving Srare and Sfreq ; and furthermore µ(λ(σ0 ρ1 σ1 · · · ρn σn )) =
µ(λ(σ0 ))µ(λ(ρ1 ))µ(λ(σ1 )) · · · µ(λ(ρn ))µ(λ(σn )), which by (*) is equal to g, concluding the
forward direction of the correctness proof.
We now show the backward direction. Assume that there is a topological sort σ 0 of I
achieving g, i.e., µ(σ 0 ) = g. We can decompose it as an interleaving of Srare and Sfreq , which

A. Amarilli and C. Paperman

we write σ0 ρ01 σ1 · · · ρ0n0 σn0 , with ρ01 · · · ρ0n0 being a topological sort of Srare , and σ0 · · · σn0
being a topological sort of Sfreq (in particular, we have µ(λ(σ0 · · · σn0 )) ∈ τ (Comµ (Sfreq )),
which we call condition (#20 )). We now use the insertion lemma (Lemma E.5) to argue
that there exists a set w0 , . . . , wn0 of words of A∗ , with wi = λ(σi ) for at most B values
of i and being the empty word otherwise, such that µ(w0 λ(ρ01 )w1 · · · λ(ρ0n0 )wn0 ) = µ(σ 0 ) = g,
and (#200 ) µ(λ(σ0 · · · σn0 )) = µ(w0 · · · wn ). We now collapse the ρ0i which are contiguous,
calling the result ρ1 , . . . , ρn , where we have (#3) n < B, and write gi the µ-image of the i-th
wi which is non-empty: this image is in Hfreq because the strings in Sfreq are only labeled
with letters in Afreq . This gives us a topological sort ρ1 , . . . , ρn of Srare , and a sequence
g0 , . . . , gn of elements of Hfreq , such that (#1) g0 µ(λ(ρ1 ))g1 · · · µ(λ(ρn ))gn = g. By (#1),
(#20 ) combined with (#200 ), 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 =
K0 a1 K1 · · · am Km , where each ai is a letter of the alphabet (they are not necessarily distinct),
and each Ki is a group language on some subset Ai of the alphabet. We fix as before the
instance I = (S1 , . . . , Sn ) of the CSh-problem. A K-slicing of the instance I is an (m + 1)tuple of instances I0 , . . . , Im , with each Ij being a n-tuple (S1j , . . . , Snj ) of strings, and an
0
m-tuple of instances I10 , . . . , Im
, with each Ij0 being a n-tuple ((S 0 )j1 , . . . , (S 0 )jn ) as before,
with the stipulation that, for each 1 ≤ j ≤ m, all (S 0 )ji are empty except one which is a
singleton whose only element is labeled aj ; and that, for each 1 ≤ i ≤ n, the concatenation
m
Si0 (S 0 )1i Sii · · · (S 0 )m
i Si is equal to Si . In other words, a slicing is a partition of each string of
I in a way that respects the ai .
Intuitively, we would like to guess a slicing, check the Ii0 in the obvious way, and apply the
previous result to the Ij for odd j, corresponding to the group languages Kj . Unfortunately,
while guessing the even Ij 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 nk , and let R := nk . Given a slicing
0
I0 . . . Im and I10 . . . Im
, a rare–frequent partition of the slicing consists of one partition Ajrare ,
j
Afreq for all 1 ≤ j ≤ m, and one global partition of the strings S1 , . . . , Sn into rare strings
Srare and frequent strings Sfreq (again, the frequent strings are not explicitly represented).
We require that (i) for every string S of Sfreq , considering its slices S 0 , . . . , S m , for each
1 ≤ j ≤ m, the slice S j contains only letters of Ajfreq ; that (ii) for every 1 ≤ j ≤ m, the S j
for S in Sfreq , when seen as a subinstance of I over the alphabet Ajfreq , contains an R-rich
antichain; and that (iii) for every 1 ≤ j ≤ m, the one non-empty string of Ij0 is in Srare .
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.
0
, there exists a rare–frequent partition
I Lemma E.10. For any slicing I0 , . . . , Im , I10 , . . . , Im
such that |Srare | ≤ m · R · k 2 .

Proof. We apply Lemma E.7 to each Ij for 1 ≤ j ≤ m to obtain one rare–frequent partition
j
j
for it, written Ajrare t Ajfreq = Aj and Srare
t Sfreq
= Ij , except that we take m × (R + 2)

XX:41

XX:42

Constrained Topological Sorting

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
j
Srare to be the union of the strings S of I such that S j is in Srare
for some 0 ≤ j ≤ m,
0
plus the strings that are non-empty in some Ij . We take Sfreq 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 Ij ,
and m for the slices of the form Ij0 . Hence, we can deduce an R-rich antichain by looking at
any preexisting (m × (R + 2))-rich antichain.
J
While we cannot guess the slices, let us guess partitions Aj = Ajrare t Ajfreq for 0 ≤ j ≤ m
and the set Srare of (globally) rare strings of size at most R · k 2 . Let us further guess the
slices Sj0 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 Srare , 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
g0 , . . . , gn in condition (*) in the previous proof. Formally, we guess a sequence g0j , . . . , gnj j for
j
all 0 ≤ j ≤ m, with each gij being an element of Hfreq
, the subgroup of Hj spanned by Ajfreq .
Last, we also guess an element γ0 , . . . , γm of H0 × · · · × Hm to describe the accepting elements
of the Hi 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 Sfreq with an additional string labeled directly with elements of the groups Hi of
the group languages Ki , 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 Ij0 , 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 Ij 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 Sfreq (i.e., not in Srare ), 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 \ Ajfreq , that our choice of slicing does not contain
any occurrence of a in the restriction of the slice Ij to Sfreq .
For each 0 ≤ j ≤ m, for each a ∈ Ajfreq , 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 Ij to
Sfreq , witnessing that it has an R-rich antichain for the alphabet Ajfreq .
For each 0 ≤ j ≤ m, letting w be the word containing all letters of the restriction of
slice Sj to Sfreq with the correct number of occurrences, that g0j · · · gnj j ∈ τj (Comµj (w)),
intuitively checking that we have the right commutative image.

A. Amarilli and C. Paperman

Second, we check the following condition (**), inspired from condition (*) in the previous
j
proof: for all 0 ≤ j ≤ m, there exist a topological sort ρj0 · · · ρjnj of the slice Srare
of Srare
0
whose concatenation, interleaved with the singleton elements of the Ij , is a topological sort
of Srare , and g0j λ(ρj0 ) · · · gnj j −1 λ(ρjnj −1 )g j nj = γ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 Srare (at most Rk 2 of them),
partitions Ajfreq t Ajrare , and sequences g0j , . . . , gnj j , 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
j
of a set Srare of rare strings (whose slices are written Srare
), and frequent strings Sfreq (with
j
j
0
the same convention for slices), partitions Afreq t Arare , a slicing I0 , . . . , Im and I10 , . . . , Im
,a
j
j
j
topological sort of Sfreq constituting of topological sorts ρ0 · · · ρnj of each Srare for 0 ≤ j ≤ m
interleaved with the singleton elements of the Ij0 for 1 ≤ j ≤ m, sequences g0j , . . . , gnj j of
elements of Hj for 0 ≤ j ≤ m, and an element γ0 , . . . , γm of H0 × · · · × Hm , such that:
For all 0 ≤ j ≤ m, the element γj is accepting in Hj .
For all 0 ≤ j ≤ m, for all S ∈ Sfreq , the slice S j contains only letters from Ajfreq , and
contains an R-rich antichain on the sub-alphabet Ajfreq .
For all 0 ≤ j ≤ m, for all S ∈ Srare , the slice S j contains only letters from Aj .
j
For all 0 ≤ j ≤ m, letting Sfreq
be the slice of Sfreq defined in the expected way, we have
j
j
j
g0 · · · gnj ∈ τj (Comµj (Sfreq )).
(#) For all 0 ≤ j ≤ m, we have g0j λ(ρj0 ) · · · gnj j −1 λ(ρjnj −1 )gnj j = γj
We claim that we can deduce from this the existence of a witnessing topological sort.
j
To do this, as before, we will use Lemma E.4 in the Sfreq
for all 0 ≤ j ≤ m. From our
j
definition of R, as nj < B, as Sfreq contains an nk -rich antichain (seen as an instance on the
j
sub-alphabet Ajfreq ), as g1j · · · gnj j ∈ τj (Comµj (Sfreq
)), there is a topological sort σ1j . . . σnj j
j
of Sfreq
such that µj (λ(σij )) = gij for each 0 ≤ j ≤ m and 1 ≤ i ≤ nj . This allows us to
deduce our witnessing topological sort of I, consisting of a topological sort of each slice Ij
of I achieving γj , interleaved with the trivial topological sorts of the Ij0 that achieve the
required aj : the topological sort of Ij is formed of the guessed topological sort ρj0 · · · ρjnj of
j
j
Srare
interleaved with the topological sort σ1j , . . . , σnj j of Sfreq
, each vij achieving gij , so that
the topological sort of Ij 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 Ij for 0 ≤ j ≤ m has a topological sort achieving an element γj which
is accepting for Hj . We now use Lemma E.10 to argue that there exists a rare–frequent
partition consisting of a partition Srare t Sfreq of the strings, and Ajrare t Ajfreq of the alphabets
Aj , such that |Srare | ≤ m · R · k 2 . In each slice, the witnessing topological sort must consist
j
j
of a topological sort of the Srare
interleaved with topological sorts of the Sfreq
. As in the
previous proof, we now use Lemma E.5 to argue that we can assume that there are at
most nj such insertions, without changing the µj -image of the result or the µj -image of the
inserted elements. Now, we define the g1 , . . . , gnj j as the µj -images of these insertions. We

XX:43

XX:44

Constrained Topological Sorting

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\Aj ) and of a
rare–frequent partition (for Aj \Ajrare ); the second condition is by definition of a rare–frequent
partition; the third condition is by definition of g1 , . . . , gnj j being achieved as a topological
j
sort of Srare
. We next explain why the second phase works, by explaining why condition (**)
j
is satisfied. This can be seen by considering when the insertions of the Sfreq
are performed
j
in the Srare : 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].
I Proposition 6.3. Let K = (a+ b+ a+ b+ )∗ . Then CSh[K] is in NL.
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 00 be such an antichain, and C 0 be a subset of C 00 containing
exactly three occurrences of each letter; it is still an antichain. We now define C as a subset
of C 0 containing exactly two occurrences of each letter, and ensuring that there is an a-labeled
element va which is the first element of a string and is not in a string of C, and likewise
there is a b-labeled element vb 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 0 to construct C.
Now, consider a topological sort σ1 of I formed by concatenating va , a topological sort σ−
of the ancestors of elements of C and of the elements incomparable to C except va and vb ,
a topological sort σ10 of C achieving the word aabb, a topological sort σ+ of the successors
of C, and vb . The word w1 achieved by σ1 starts with a and ends with b, so it must be
of the form (a+ b+ )∗ . Let n1 be the number of repetitions of a+ b+ in w1 . Now, consider
the topological sort σ2 obtained by concatenating va , σ− , σ20 , σ+ , and vb , where σ20 is a
topological sort of C achieving the word abab. Again, the word w2 achieved by σ2 must
be of the form (a+ b+ )∗ : let n2 be the number of repetitions of a+ b+ in w2 . We claim that
n2 = n1 + 1. Indeed, consider the subfactor a+ b+ that contains σ10 in σ1 . In σ2 , the other
subfactors are unchanged, and this subfactor is split into two subfactors, one ending at the
first b of σ20 , the other one starting at the second a of σ20 . So indeed n2 = n1 + 1. Hence, one
of n1 , n2 is even, and the corresponding σi witnesses that I is a positive instance to CSh[K].

A. Amarilli and C. Paperman

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 0 , which means that
the other strings S1 , . . . , Sm only contain elements labeled with the other symbol β 6= α of A.
Now, it is easy to see that we obtain exactly the same topological sorts by merging together
P
the S1 , . . . , Sm to one string S 00 of elements labeled β whose length is i |Si |. Hence, we
can reduce the problem in NL to the instance {S, S 0 , S 00 }. 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.
J
References for the Appendix
ABDS17 Antoine Amarilli, M. Lamine Ba, Daniel Deutch, and Pierre Senellart. Possible and certain
Alm94
Dil50
Eil74
Ful55
GGP08
GJ75
Imm88
Pap18
PW97
Str94
Sze88
TT01
TT02
TT05
WH84

answers for queries over order-incomplete data. In Proc. TIME, 2017.
J. Almeida. Finite Semigroups and Universal Algebra. Series in algebra. World Scientific,
1994.
Robert P. Dilworth. A decomposition theorem for partially ordered sets. Annals of Mathematics, 1950.
Samuel Eilenberg. Automata, languages, and machines. Vol. A. Academic Press, 1974.
Pure and Applied Mathematics, Vol. 58.
D. R. Fulkerson. Note on Dilworth’s decomposition theorem for partially ordered sets. In
Proc. Amer. Math. Soc, 1955.
Antonio Cano Gómez, Giovanna Guaiana, and Jean-Eric Pin. When does partial commutative closure preserve regularity? In Proc. ICALP, 2008.
Michael R. Garey and David S. Johnson. Complexity results for multiprocessor scheduling
under resource constraints. SIAM J. Comput, 1975.
Neil Immerman. Nondeterministic space is closed under complementation. SIAM J. Comput, 17(5), 1988.
Charles Paperman. Semigroup online, 2018. https://www.paperman.name/semigroup/.
Jean-Éric Pin and Pascal Weil. Polynominal closure and unambiguous product. TCS, 30(4),
1997.
Howard Straubing. Finite automata, formal logic, and circuit complexity. Birkhauser
Verlag, 1994.
Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata.
Acta Informatica, 26(3), 1988.
Pascal Tesson and Denis Thérien. The computing power of programs over finite monoids.
J. Autom. Lang. Comb., 7(2), 2001.
Pascal Tesson and Denis Thérien. Diamonds are forever: the variety DA. Semigroups,
algorithms, automata and languages, 1, 2002.
Pascal Tesson and Denis Thérien. Complete classifications for the communication complexity of regular languages. TCS, 38(2), 2005.
Manfred K. Warmuth and David Haussler. On the complexity of iterated shuffle. JCSS,
28(3), 1984.

XX:45

