Ca’ Foscari University of Venice, Italy and http://www.gssi.it/people/post-
doc/post-doc-computer-science/item/4577-becker-
rubenrubensimon.becker@unive.ithttps://orcid.org/0000-0002-3495-3753
University of Helsinki, Finland and
https://me.ariel.computer/manuel.caceresreyes@helsinki.fihttps://orcid.org/0000-0003-0235-6951This
work was partially funded by the Academy of Finland (grants No.
352822,328877). Ca’ Foscari University of Venice,
Italydavide.cenzato@unive.ithttps://orcid.org/0000-0002-0098-3620 Ca’ Foscari
University of Venice,
Italysunghwan.kim@unive.ithttps://orcid.org/0000-0002-1117-5020Funded by the
European Union (ERC, REGINDEX, 101039208). Ca’ Foscari University of Venice,
Italybojana.kodric@unive.ithttps://orcid.org/0000-0001-7242-0096 CeBiB —
Centre for Biotechnology and Bioengineering and Department of Computer
Science, University of Chile,
Chilefolivares@uchile.clhttps://orcid.org/0000-0001-7881-9794Funded by Ph.D
Scholarship 21210579, ANID, Chile. Ca’ Foscari University of Venice,
Italynicola.prezza@unive.ithttps://orcid.org/0000-0003-3553-4953Funded by the
European Union (ERC, REGINDEX, 101039208). Views and opinions expressed are
however those of the author(s) only and do not necessarily reflect those of
the European Union or the European Research Council. Neither the European
Union nor the granting authority can be held responsible for them. Ruben
Becker, Manuel Cáceres, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric,
Francisco Olivares, and Nicola Prezza [500]Theory of computation Sorting and
searching [500]Theory of computation Graph algorithms analysis [500]Theory of
computation Pattern matching

###### Acknowledgements.

cproblem[1]  #1 0

#  Sorting Finite Automata via Partition Refinement

Ruben Becker  Manuel Cáceres  Davide Cenzato  Sung-Hwan Kim  Bojana Kodric
Francisco Olivares  Nicola Prezza

###### Abstract

Wheeler nondeterministic finite automata (WNFAs) were introduced in (Gagie et
al., TCS 2017) as a powerful generalization of prefix sorting from strings to
labeled graphs. WNFAs admit optimal solutions to classic hard problems on
labeled graphs and languages such as compression and regular expression
matching. The problem of deciding whether a given NFA is Wheeler is known to
be NP-complete (Gibney and Thankachan, ESA 2019). Recently, however, Alanko et
al. (Information and Computation 2021) showed how to side-step this complexity
by switching to _preorders_ : letting $Q$ be the set of states and $\delta$
the set of transitions, they provided a $O(|\delta|\cdot|Q|^{2})$-time
algorithm computing a totally-ordered _partition_ (i.e. equivalence relation)
of the WNFA’s states such that (1) equivalent states recognize the same
regular language, and (2) the order of (the classes of) non-equivalent states
is consistent with any Wheeler order, when one exists. As a result, the output
is a preorder of the states as useful for pattern matching as standard Wheeler
orders.

Further extensions of this line of work (Cotumaccio et al., SODA 2021 and DCC
2022) generalized these concepts to arbitrary NFAs by introducing _co-lex
partial preorders_ : in general, any NFA admits a partial preorder of its
states reflecting the co-lexicographic order of their accepted strings; the
smaller the width of such preorder is, the faster regular expression matching
queries can be performed. To date, the fastest algorithm for computing the
smallest-width partial preorder on NFAs runs in $O(|\delta|^{2}+|Q|^{5/2})$
time (Cotumaccio, DCC 2022), while on DFAs the same task can be accomplished
in $O(\min(|Q|^{2}\log|Q|,|\delta|\cdot|Q|))$ time (Kim et al., CPM 2023).

In this paper, we provide much more efficient solutions to the co-lex order
computation problem. Our results are achieved by extending a classic algorithm
for the relational coarsest partition refinement problem of Paige and Tarjan
to work with _ordered_ partitions. More specifically, we provide a
$O(|\delta|\log|Q|)$-time algorithm computing a co-lex total preorder when the
input is a Wheeler NFA, and an algorithm with the same time complexity
computing the smallest-width co-lex partial order of any DFA. In addition, we
present implementations of our algorithms and show that they are very
efficient also in practice.

###### keywords:

Wheeler automata, prefix sorting, pattern matching, graph compression,
sorting, partition refinement

###### category:

##  1 Introduction

The classical _pattern matching_ problem between two strings $S$ (the text)
and $P$ (the pattern) over alphabet $\Sigma$ asks to find the substrings of
$S$ matching $P$. Although many algorithms solving the _on-line_ version of
the problem exist, in many scenarios it is possible to pre-process $S$ _off-
line_ into an _index_ to speed up subsequent pattern matching queries. As a
matter of fact, a very successful line of research dating back to the
invention of suffix trees [25] and culminating with the discovery of
compressed data structures [21] showed that it is possible to represent $S$ in
compact space while speeding up matching queries.

The _indexed pattern matching_ problem can be generalized to collections of
strings: in this case the pattern must be found as a substring in a string
collection $\mathcal{S}$. A natural approach to solve this problem is to
concatenate all strings in $\mathcal{S}$ into one string $S$ and re-use the
well-optimized techniques for classical pattern matching. Even though there
are many successful examples of indexes following this strategy [13, 15, 20],
this approach suffers from high space consumption during index construction
(the input is very large), and does not scale to a more general (and
interesting) scenario: the case where $\mathcal{S}$ contains an _infinite_
number of strings. A solution, addressing both issues, is to represent a
(potentially infinite) collection of strings using a finite-state automaton
with set of states $Q$ and transition function $\delta$. In this new scenario,
the goal of pattern matching is to locate paths in the automaton (seen as a
labeled graph) spelling the query pattern $P$. In bioinformatics, for example,
genomic collections are represented using pangenome graphs: labeled graphs
encoding nucleotide variations within the collection [6, 24]. Matching a DNA
sequence over a pangenome graph allows one to discover the genetic variation
in a population [23].

Unfortunately, both the off-line and on-line pattern matching problems are
hard to solve on labeled graphs: Equi et al. [11, 12] showed that, conditioned
on OVH [26], it is not possible to design a polynomial-time algorithm to index
a labeled graph such that pattern matching queries can be answered in
$O(|P|+|\delta|^{\alpha}|P|^{\beta})$ time, for any constants $\alpha<1$ or
$\beta<1$.

A successful paradigm to cope with this hardness is to study sub-classes of
graphs where the problem is easier. Along these lines, Gagie et al. [14]
introduced the class of Wheeler automata: labeled graphs admitting a total
order of their states (a _Wheeler order_) which respects the underlying
alphabet’s order and it is propagated through pairs of equally-labeled edges.
Wheeler orders generalize prefix sorting (the machinery standing at the core
of the most successful string indexes) to labeled graphs and as a consequence,
an index over a Wheeler automaton supports pattern matching queries in near-
optimal $O(|P|\log|\Sigma|)$ time.

Wheeler automata, however, have two important limitations. First, the classes
of Wheeler automata and Wheeler languages (accepted by such automata) are
quite restricted. For example, Wheeler automata cannot contain proper cycles
labeled with a unary string, and moreover, Wheeler languages are star-free
[2]. Second, several natural problems related to Wheeler graphs are
computationally hard. For example, the simple fact of deciding if an automaton
is Wheeler is NP-complete, even when the automaton is acyclic [16].

Related to the first issue, the work [9] extended state-ordering to arbitrary
automata by using the concept of _co-lex partial order_. By switching from
total to partial orders, the authors showed that (i) every automaton can be
(partially) sorted, and that (ii) the efficiency of pattern matching on the
automaton depends on the _width_ (maximum size of an antichain) of such
partial order. Wheeler automata are the particular case in which there exists
a total co-lex order (i.e., of width one), thus enabling near-optimal time
pattern matching queries.

A way to circumvent the latter limitation (hardness of computing a Wheeler
order) was proposed by Alanko et al. [2] by switching to _total preorders_ :
the authors showed a $O(|\delta|\cdot|Q|^{2})$-time _partition refinement_
algorithm, which outputs a totally-ordered partition of $Q$ such that (1)
states in the same part recognize the same language, and (2) the order of the
partition is consistent with _any_ Wheeler order of $Q$. In other words, this
ordered partition is a preorder of the states as useful for indexing as
Wheeler orders. Recently, a similar solution was proposed by Chao et al. [5]
to speed up the computation of Wheeler orders in practice; after a first
polynomial-time partition refinement step, their tool runs an exponential-time
solver to assign a Wheeler ordering within classes of equivalent states.

These strategies — partial orders and total preorders — were finally merged by
Cotumaccio [7]. As in [9], the efficiency of pattern matching depends on the
width of such a partial preorder. The author described a polynomial-time
algorithm computing a _colex partial preorder_ of smallest width over an
arbitrary nondeterministic finite-state automaton (NFA) in
$O(|\delta|^{2}+|Q|^{5/2})$ time. Later, this running time was improved by Kim
et al. [18] in the particular case of DFAs with two algorithms running in time
$O(|Q|^{2}\log|Q|)$ and $O(|\delta|\cdot|Q|)$, respectively, and one algorithm
running in near-optimal time $O(|\delta|\log|Q|)$ on acyclic DFAs.

#### Our contributions.

We consider two cases of colex orders: (1) total preorders on NFAs, and (2)
partial orders of minimum width on DFAs. We provide algorithms running in time
$O(|\delta|\log|Q|)$ for both cases, improving the state-of-the-art cubic and
quadratic algorithms to near-optimal time.

Our solution to (1) is obtained by extending a classic algorithm for the
relational coarsest partition refinement problem of Paige and Tarjan [22] to
work with _ordered_ partitions. Our algorithm starts from the ordered
partition corresponding to the states’ incoming labels and, similarly to [22],
iteratively refines this partition by enforcing _forward-stability_ : for any
two parts $B$ (the “splitter”) and $D$ (the “split”) the image $\delta_{a}(B)$
of $B$ through the transition function (for any alphabet’s character $a$) must
either contain $D$ or be disjoint with $D$. If this condition is not
satisfied, $D$ is split into three parts: states reached only from $B$, states
reached only from $Q\setminus B$, and states reached from both. In addition to
Paige and Tarjan’s algorithm, we show how to sort these three parts
consistently with the current partition’s order. In fact, we show that our
algorithm finds a total preorder on a class of automata being strictly larger
than the Wheeler automata. We dub this class _quasi-Wheeler_ , thereby
extending the class of automata that can be indexed to support queries in
near-optimal time.

######  Theorem 1.1.

For an NFA $\mathcal{A}=(Q,\delta,s)$, we can compute a total preorder
$\preceq$ in $O(|\delta|\log|Q|)$ time such that $\preceq$ corresponds to a
Wheeler preorder if and only if $\mathcal{A}$ is quasi-Wheeler.

Our solution to (2) relies on a further modification of the partition
refinement algorithm. More specifically, we show that within the same time
complexity, we can prune the automaton’s transition function so that the
resulting graph is a quasi-forest satisfying the following property: every
state $u$ has only one incoming path, whose label (the _infimum_) is co-
lexicographically smallest among (the labels of) all paths ending at $u$ in
the original DFA. Symmetrically, we compute a pruned automaton encoding the
co-lexicographically largest strings (the _suprema_). We obtain our second
result by plugging in the $O(|Q|\log|Q|)$-time algorithms of Kim et al. [18],
which sort the infimum and suprema strings (suffix-doubling)111We develop an
extension of this algorithm with the claimed time complexity. and then compute
a minimum chain partition of the smallest-width co-lex order (interval graph
coloring). Our result assumes that the DFA is input-consistent (all incoming
transitions to a state are labeled with the same letter). This assumption is a
common simplification in automata theory and it is not a limitation of our
approach as every DFA can be easily transformed into an equivalent input-
consistent DFA.

######  Theorem 1.2.

For an input-consistent DFA $\mathcal{A}=(Q,\delta,s)$, we can compute a
minimum chain partition of the smallest-width co-lex order in
$O(|\delta|\log|Q|)$ time.

We have implemented our partition refinement algorithms. We compared the
implementation of our algorithm from Theorem 1.1 with a heuristic
implementation from WGT [5] (their first polynomial time step) which,
similarly to our algorithm, computes an ordered partition being consistent
with any Wheeler order (although not the most refined — unlike the output of
our algorithm). On random Wheeler NFAs generated with a tool from the same
toolbox (WGT), our implementation outperforms the heuristic from WGT by more
than two orders of magnitude. We also experimentally show that our algorithm
from Theorem 1.2 can prune a pangenomic DFA with more than 50 million states
in less than 6 minutes.

##  2 Notation and Preliminaries

For an integer $k\geq 1$, we let $[k]:=\\{1,\ldots,k\\}$. Given a set $U$, a
partition $\mathcal{P}$ of $U$ is a set of pairwise disjoint non-empty sets
$\\{U_{1},\ldots,U_{k}\\}$ whose union is $U$. We call $U_{1},\ldots,U_{k}$
the _parts_ of $\mathcal{P}$. If we, in addition, have a (total) order of the
parts, we say that it is an _ordered partition_ and denote it with $\langle
U_{1},\ldots,U_{k}\rangle$. For two (ordered) partitions $\mathcal{P}$ and
$\mathcal{P}^{\prime}$ of $U$, we say that $\mathcal{P}^{\prime}$ is a
_refinement_ of $\mathcal{P}$ if every part of $\mathcal{P}^{\prime}$ is
contained in a part of $\mathcal{P}$, i.e., for every
$U^{\prime}\in\mathcal{P}^{\prime}$ there is $U\in\mathcal{P}$ with
$U^{\prime}\subseteq U$. As a special case, a partition is a refinement of
itself.

#### Relations and Orders.

A _relation_ $R$ over a set $U$ is a set of ordered pairs of elements from
$U$, i.e., $R\subseteq U\times U$. We sometimes omit $U$ if it is clear from
the context. For two elements $u,v$ from $U$, we usually write $uRv$ for
$(u,v)\in R$.

A _strict partial order_ over a set $U$ is a relation that satisfies
irreflexivity, asymmetry, and transitivity. If, in addition, a strict partial
order satisfies connectedness it is a _strict total order_. A _total preorder_
over a set $U$ is a relation that satisfies transitivity, reflexivity, and
connectedness (i.e., for all two distinct $u,v\in U$, $u$ is in relation with
$v$ or $v$ is in relation with $u$). An _equivalence relation_ over a set $U$
is a relation that satisfies reflexivity, symmetry, and transitivity. For an
equivalence relation $\sim$, we use $[u]_{\sim}$ to denote the equivalence
class of an element $u\in U$ with respect to $\sim$, i.e.,
$[u]_{\sim}:=\\{v\in U:u\sim v\\}$. We denote with $U/_{\sim}$ the partition
of $U$ consisting of all equivalence classes $[u]_{\sim}$ for $u\in U$. In
this paper, we denote strict total orders with the symbols $\prec$ and $<$,
total preorders with the symbols $\preceq$ and $\leq$, and equivalence
relations with the symbols $\sim$ and $\approx$.

A total preorder $\preceq$ over $U$ induces an equivalence relation $\sim$
over $U$: For $u,v\in U$, define $u\sim v$ if and only if $u\preceq v$ and
$v\preceq u$. Throughout the paper, $\sim$ will always refer to the
equivalence induced by $\preceq$ (the order $\preceq$ will always be
unambiguously defined). A total preorder $\preceq$, in addition, yields a
strict total order $\prec$ on the elements of $U/_{\sim}$ as
$[u]_{\sim}\prec[v]_{\sim}$ if and only if $u\preceq v$ and not $v\preceq u$.
Throughout the paper $\prec$ will refer to the strict order induced by
$\preceq$ (always unambiguously defined). A total preorder $\preceq$ over a
set $U$ can thus be represented by a unique ordered partition $\langle
U_{1},\ldots,U_{k}\rangle$, where the parts $U_{i}$ represent the equivalence
classes with respect to $\sim$ and their ordering represents the strict total
order $\prec$.

#### Non-Deterministic Finite Automata (NFAs).

Let $\Sigma$ denote a fixed finite and non-empty _alphabet_ of _letters_. We
assume that there is a strict total order $<$ on the alphabet $\Sigma$.

######  Definition 2.1 (NFA and DFA).

A _non-deterministic finite automaton (NFA)_ over the alphabet $\Sigma$ is an
ordered triple $\mathcal{A}=(Q,\delta,s)$, where $Q$ is the set of _states_ ,
$\delta:Q\times\Sigma\rightarrow 2^{Q}$ is the _transition function_ , and
$s\in Q$ is the _source state_.

A _deterministic finite automaton (DFA)_ over the alphabet $\Sigma$ is an NFA
over $\Sigma$ such that $|\delta(v,a)|\leq 1$ for all $a\in\Sigma$ and $v\in
V$.

We note that the standard definition of NFAs includes also a set of final
states. As we are not concerned with the accepting languages of automata in
this work, we omit the final states from the definition. In what follows we
consider the alphabet $\Sigma$ to be fixed and thus frequently refer to NFAs
without specifying the alphabet. Given an NFA $\mathcal{A}=(Q,\delta,s)$, for
a state $u\in Q$ and a letter $a\in\Sigma$, we use the shortcut
$\delta_{a}(u)$ for $\delta(u,a)$, similarly $\delta^{-1}_{a}(u)=\\{v\ :\
\delta(v,a)=u\\}$. For a set $S\subseteq Q$, we let
$\delta_{a}(S):=\bigcup_{u\in S}\delta_{a}(u)$ and
$\delta^{-1}_{a}(S):=\bigcup_{u\in S}\delta^{-1}_{a}(u)$.

The set of finite strings over $\Sigma$, denoted by $\Sigma^{*}$, is the set
of finite sequences of letters from $\Sigma$. We extend the transition
function from letters to finite strings in the common way, i.e, for
$\alpha\in\Sigma^{*}$ and $v\in Q$, we define $\delta_{\alpha}(v)$ recursively
as follows. If $\alpha=\varepsilon$, we let $\delta_{\alpha}(v)=\\{v\\}$.
Otherwise, if $\alpha=a\alpha^{\prime}$ for some $a\in\Sigma$ and
$\alpha^{\prime}\in\Sigma^{*}$, we let
$\delta_{\alpha}(v)=\bigcup_{w\in\delta_{a}(v)}\delta_{\alpha^{\prime}}(w)$.

######  Definition 2.2 (Strings Reaching a State).

Given an NFA $\mathcal{A}=(Q,\delta,s)$, for a state $v\in Q$, the _set of
strings reaching $v$_ is defined as
$S_{v}=\\{\alpha\in\Sigma^{*}:v\in\delta_{\alpha}(s)\\}$.

Equivalently, $S_{v}$ is the regular language recognized by state $v$. For
simplicity, in this work we assume that NFAs satisfy the following two
properties: (1) The source state has no in-going transitions, i.e.,
$S_{s}=\\{\varepsilon\\}$ and every other state is reachable from the source
state, i.e., $|S_{v}|>1$ for all $v\in Q\setminus\\{s\\}$. (2) The automaton
is _input-consistent_ , i.e., for every state $v\in Q\setminus\\{s\\}$ it
holds that $\delta_{a}^{-1}(v)$ is non-empty for exactly one letter
$a\in\Sigma$. It is easy to see that any automaton can be transformed into an
equivalent one (in the sense of the recognized language) satisfying
assumptions (1) and (2). Condition (1) yields that $|Q|\leq|\delta|+1$.
Condition (2) comes at the cost of increasing the number of states and
transitions by a factor of at most $|\Sigma|$. We also assume that a given NFA
contains at least one transition for every letter. We denote by $\lambda(v)$
the unique label of the incoming transitions of a state $v\in
Q\setminus\\{s\\}$, while $\lambda(s):=\varepsilon$. We also extend this
notation to sets of states, that is for a set of states $S$, we let
$\lambda(S):=\\{\lambda(v):v\in S\\}$ and if $\lambda(S)=\\{a\\}$, we write
$\lambda(S)=a$.

#### Forward-Stable Partitions.

Alanko et al. consider _forward-stable partitions_ [2, Section 4.2].

######  Definition 2.3 (Forward-Stability).

Given an NFA $\mathcal{A}=(Q,\delta,s)$ and two sets of states $S,T\subseteq
Q$, we say that $S$ is _forward-stable_ with respect to $T$, if, for all
$a\in\Sigma$, $S\subseteq\delta_{a}(T)$ or $S\cap\delta_{a}(T)=\emptyset$
holds. A partition $\mathcal{P}$ of $\mathcal{A}$’s states is _forward-stable
for $\mathcal{A}$_, if, for any two parts $S,T\in\mathcal{P}$, it holds that
$S$ is forward-stable with respect to $T$.

A direct consequence of forward-stability is given in the following lemma,
i.e., all states in the same part of a forward-stable partition are reached by
the exact same set of strings.

######  Lemma 2.4.

Let $\mathcal{P}$ be a forward-stable partition for an NFA
$\mathcal{A}=(Q,\delta,s)$ and assume that $u,v\in P$ for some part
$P\in\mathcal{P}$. Then, $S_{u}=S_{v}$.

This property can be proven easily using the definition of forward-stability,
see, e.g., [2, Lemma 4.7]. Furthermore, there is a straightforward
relationship between forward-stability and bisimulation, see, e.g., the work
of Kanellakis and Smolka [17] or Chapter 7.3 of the book by Katoen and Baier
[3]. The _coarsest_ forward-stable partition for an NFA $\mathcal{A}$, i.e.,
the forward-stable partition with fewest parts, is identical to the partition
consisting of the equivalence classes with respect to the bisimilarity
relation (the unique largest bisimulation) on $\mathcal{A}^{-1}$, the
automaton obtained from $\mathcal{A}$ by reversing all its transitions. We
include a proof of this fact in Appendix A. This also directly yields that
there is a unique forward-stable partition. We note that a reverse statement
of Lemma 2.4 may not necessarily hold even for the coarsest forward-stable
partition. More precisely, states in different parts of the coarsest forward-
stable partition may have the same set of strings reaching them, see the left
automaton in Figure 1. In what follows, for an NFA $\mathcal{A}=(Q,\delta,s)$
and an equivalence relation $\sim$ on $Q$, we write $\mathcal{A}/_{\sim}$ for
the quotient NFA (of $\mathcal{A}$ with respect to $\sim$) obtained by
collapsing the equivalence classes into single states, see [2, Definition 8]
for a formal definition.

#### Wheeler NFAs and Quasi-Wheeler NFAs.

Wheeler NFAs [14] are a special class of NFAs that can be stored compactly and
indexed efficiently as they can be endowed with a specific type of strict
total order, the so-called _Wheeler order_.

######  Definition 2.5 (Wheeler NFA and Wheeler order).

Let $\mathcal{A}=(Q,\delta,s)$ be an NFA. We say that $\mathcal{A}$ is a
_Wheeler NFA_ , if there exists a _Wheeler order_ $\prec$ of $Q$. A Wheeler
order $\prec$ of $Q$ is a strict total order on $Q$ such that the source state
precedes all other states, i.e., $s\prec v$ for all $v\in Q\setminus\\{s\\}$,
and, for any pair $v\in\delta_{a}(u)$ and
$v^{\prime}\in\delta_{a^{\prime}}(u^{\prime})$:

  1. (1)

If $a<a^{\prime}$, then $v\prec v^{\prime}$.

  2. (2)

If $a=a^{\prime}$, $u\prec u^{\prime}$, and $v\neq v^{\prime}$, then $v\prec
v^{\prime}$.

Clearly, not every NFA is a Wheeler NFA and, even worse, recognizing if a
given NFA is Wheeler is NP-complete (for alphabet size at least 2) as shown by
Gibney and Thankachan [16]. We now introduce the following problem, called
OrderWheeler: Given an arbitrary NFA $\mathcal{A}=(Q,\delta,s)$ as input, the
task is to compute a strict total order $\prec$ of $Q$ with the property that
$\prec$ is a Wheeler order if $\mathcal{A}$ is Wheeler. As a result of the NP-
completeness of recognizing Wheeler NFAs previously mentioned, also
OrderWheeler is NP-hard. This follows as checking whether a given order is
indeed a Wheeler order can be done in linear time [1, Lemma 3.1]. This
motivates introducing the following relaxed version of Wheeler NFAs.

######  Definition 2.6 (Wheeler preorders and quasi-Wheeler NFAs).

Let $\mathcal{A}=(Q,\delta,s)$ be an NFA. A Wheeler preorder $\preceq$ on $Q$
is a total preorder on $Q$ such that:

  * •

The partition $Q/_{\sim}$, where $\sim$ is the equivalence relation induced by
$\preceq$, is equal to the coarsest forward-stable partition of $\mathcal{A}$.

  * •

The quotient automaton $\mathcal{A}/_{\sim}$ is a Wheeler NFA with the strict
total order $\prec$ induced by $\preceq$ on the equivalence classes with
respect to $\sim$.

We say that $\mathcal{A}$ is a _quasi-Wheeler NFA_ , if there exists a
_Wheeler preorder_ $\preceq$ on $Q$.

See the beginning of this section for the formal definition of $\sim$ and
$\prec$. From the point of view of indexing, quasi-Wheeler NFAs are as useful
as Wheeler NFAs: note that the quotient automaton $\mathcal{A}/_{\sim}$ in the
definition above generates the same language as the original NFA $\mathcal{A}$
due to the properties of the forward-stable partition, see Lemma 2.4. However,
$\mathcal{A}/_{\sim}$ is a Wheeler NFA and can thus be stored compactly and
indexed efficiently. We next note that Corollary 4.11 in the paper by Alanko
et al. [2] directly yields the following lemma.

######  Lemma 2.7.

Let $\mathcal{A}=(Q,\delta,s)$ be a Wheeler NFA, then $\mathcal{A}$ is also a
quasi-Wheeler NFA.

Furthermore, the set of quasi-Wheeler NFAs is strictly larger than the set of
Wheeler NFAs as there exist non-Wheeler NFAs $\mathcal{A}$ for which the
quotient automaton $\mathcal{A}/_{\sim}$ is Wheeler, e.g., the NFA and its
corresponding quotient NFA in the center and on the right of Figure 1.

$s$$1$$2$$3$$a$$a$$a$$a$$a$$a$$s$$1$$2$$3$$4$$b$$b$$b$$b$$b$$a$$a$$s$$1,2$$3$$4$$a$$b$$b$$b$

Figure 1: Left: An NFA for which
$\mathcal{P}=\langle\\{s\\},\\{1\\},\\{2\\},\\{3\\}\rangle$ is the coarsest
forward-stable partition, yet $S_{2}=S_{3}$. Center: A non-Wheeler NFA (the
two states $3$ and $4$ cannot be ordered) that is quasi-Wheeler as witnessed
by the Wheeler preorder $\preceq$ corresponding to the ordered partition
$\langle\\{s\\},\\{1,2\\},\\{3\\},\\{4\\}\rangle$. Right: Quotient automaton
$\mathcal{A}/_{\sim}$, where $\mathcal{A}$ is the automaton in the middle and
$\sim$ is the equivalence relation induced by the Wheeler preorder $\preceq$.
Notice that $\mathcal{A}/_{\sim}$ is Wheeler with the strict total order
$\prec$ induced by $\preceq$ on the equivalence classes with respect to
$\sim$.

An important advantage of quasi-Wheeler NFAs over classical Wheeler NFAs is
that the former can be recognized in polynomial time, which is implicit in the
Forward Algorithm of Alanko et al. [2]. Indeed, the Forward Algorithm receives
a Wheeler NFA as input and, in $O(|\delta||Q|^{2})$ time, outputs a Wheeler
order of the quotient automaton $\mathcal{A}/_{\sim}$, where $\sim$ is the
equivalence relation induced by the returned partition. However, this
algorithm actually solves a slightly more general problem, since their output
partition is guaranteed to correspond to a Wheeler order of
$\mathcal{A}/_{\sim}$ whenever $\mathcal{A}$ is quasi-Wheeler rather than
Wheeler. In other words Alanko et al. gave a polynomial time algorithm for the
following problem that we call PreOrderWheeler: Given an arbitrary NFA
$\mathcal{A}=(Q,\delta,s)$, the task is to compute a total preorder $\preceq$
of $Q$ with the property that $\preceq$ is a Wheeler preorder if $\mathcal{A}$
is quasi-Wheeler. Their polynomial time algorithm for PreOrderWheeler, the
_Forward Algorithm_ , yields a polynomial-time recognition algorithm for
quasi-Wheeler NFAs as follows: Given an arbitrary input NFA $\mathcal{A}$, run
the Forward Algorithm to compute the Wheeler preorder $\preceq$ given by an
ordering of the forward-stable partition. The output partition is guaranteed
to be the coarsest forward-stable partition. Compute the quotient automaton
with respect to this partition and check if it is Wheeler (in polynomial time
by [1, Lemma 3.1]) when endowed with the induced strict total order $\prec$.

##  3 Partition Refinement for Wheeler Preorders of NFAs

In this section we provide an algorithm that solves PreOrderWheeler in
$O(|\delta|\log|Q|)$ time. Recall that the Forward Algorithm of Alanko et al.
[2] has running time $O(|\delta|\cdot|Q|^{2})$. We achieve the nearly-linear
time complexity by using the partition refinement framework of Paige and
Tarjan [22]. It is in fact clear that this framework can be used to compute a
forward-stable partition. Our notion of forward-stability corresponds to
stability with respect to $|\Sigma|$ relations, defined as $E_{a}:=\\{(u,v)\in
Q^{2}:u\in\delta_{a}(v)\\}$ for $a\in\Sigma$, in their terminology [22,
Section 3]. Our main contribution here is to extend the framework so as to
compute an _ordered_ partition (and thus a preorder), while maintaining the
nearly-linear running time.

We proceed with a description of the partition refinement algorithm by Paige
and Tarjan. The algorithm maintains two partitions $\mathcal{P}$ and
$\mathcal{X}$, here $\mathcal{P}$ is an input partition to be refined and
$\mathcal{X}$ is such that (1) $\mathcal{P}$ is a refinement of $\mathcal{X}$
and (2) every part of $\mathcal{P}$ is stable with respect to every part of
$\mathcal{X}$. Initially, $\mathcal{X}$ is the partition with a single part
containing all elements. Until $\mathcal{P}$ becomes stable, i.e., every part
of $\mathcal{P}$ is stable with respect to every part of $\mathcal{P}$, which
is witnessed by the fact that $\mathcal{P}=\mathcal{X}$, the algorithm
iteratively chooses a _compound part_ $S$ from $\mathcal{X}$, i.e., a part
form $\mathcal{X}$ that consists of multiple parts in $\mathcal{P}$. Then a
“splitter” $B$ is chosen as one of the parts in $\mathcal{P}$ contained in $S$
and every part in $\mathcal{P}$ is refined using $B$ by doing a so-called
“three-way split” that we detail in the next section. The idea behind the
three-way split is essentially to make $\mathcal{P}$ stable with respect to
$B$ and $S\setminus B$ at the same time. In fact, the choice of $B$ in the
algorithm of Paige and Tarjan is crucial. It is fundamental to always choose a
block $B$ such that $|B|\leq|S|/2$. This is the essential property that yields
the nearly linear running time using the observation that every element is
contained in at most logarithmically many splitters. This property on the size
of $B$ is achieved in Paige and Tarjan’s implementation by inspecting the
first two elements of the list of all parts from $\mathcal{P}$ contained in
$S$ and then choosing $B$ to be the smaller one (in size).

As it turns out, this choice of $B$ however interferes with maintaining the
order of the parts such as to satisfy the properties of the Wheeler preorder.
We solve this issue by choosing the smaller (in size) among the first and last
block (in the sense of the ordered partition) contained in the first compound
block (rather than the smaller out of the first two blocks, as in Paige and
Tarjan’s algorithm). This choice both guarantees that $|B|\leq|S|/2$ and
enables us to maintain a consistent ordering between the parts resulting from
a split step.

#### Algorithm.

We proceed with a description of our algorithm. A pseudo-code formulation can
be found in Algorithm 1. First, note that an input-consistent NFA has a
natural partition of its states into the $|\Sigma|+1$ parts
$\\{V_{a}\\}_{a\in\Sigma\cup\\{\varepsilon\\}}$, where $V_{a}:=\\{v\in
Q:\lambda(v)=a\\}$ for $a\in\Sigma\cup\\{\varepsilon\\}$. Property (1) of
Wheeler orders already defines the ordering of these parts: any Wheeler
preorder of the NFA’s states has to satisfy that $u$ precedes $v$ if $u$’s in-
coming letter is smaller than $v$’s. Hence, the ordering of the $|\Sigma|+1$
parts has to be $V_{\varepsilon},V_{a_{1}},\ldots V_{a_{k}}$, where we assume
that $\Sigma=\\{a_{1},\ldots,a_{k}\\}$ with $a_{1}<\ldots<a_{k}$. Following
this observation, the ordered partition $\mathcal{P}$ in the algorithm is
initialized to $\mathcal{P}:=\langle V_{\varepsilon},V_{a_{1}},\ldots
V_{a_{k}}\rangle$.

Input : NFA $\mathcal{A}=(Q,\delta,s)$

Output : Ordered Partition $\mathcal{P}$ of $Q$ that corresponds to Wheeler
preorder if and only if $\mathcal{A}$ is quasi-Wheeler

1

// * initialization * //

2 $\mathcal{P}:=\langle Q_{\varepsilon},Q_{a_{1}},...,Q_{a_{k}}\rangle$,
$\mathcal{X}:=\langle Q\rangle$

3

4while  _$\mathcal{X}\neq\mathcal{P}$ _ do

// * get splitter $B$ * //

5 $S:=$ first block in $\mathcal{X}$ consisting of multiple blocks in
$\mathcal{P}$

6 $B:=$ smaller of first and last block from $\mathcal{P}$ contained in $S$

7 // * variable $B$ contains this block even if split *//

// * update $\mathcal{X}$ * //

8 if  _$B$ is first block_ then replace $S$ in $\mathcal{X}$ with
$B,S\setminus B$ else with $S\setminus B,B$

9

// * split blocks in $\mathcal{P}$ using $B$ * //

10 for  _$D\in\mathcal{P}$ _ do

// * split $D$ * //

11

12 $D_{1}:=D\cap\delta_{a}(B)$, $D_{2}:=D\setminus D_{1}$, where
$a=\lambda(D)$

13 $D_{11}:=D_{1}\cap\delta_{a}(S\setminus B)$, $D_{12}:=D_{1}\setminus
D_{11}$

14

// * update $\mathcal{P}$ * //

15 if  _$B$ first block_ then replace $D$ in $\mathcal{P}$ with non-empty sets
from $D_{12},D_{11},D_{2}$

16 else with non-empty sets from $D_{2},D_{11},D_{12}$

17

// * continue for behind newly inserted blocks in $\mathcal{P}$ * //

18

19

return _$\mathcal{P}$_

Algorithm 1 Ordered Partition Refinement

Figure 2: The two cases of our “ordered” three-way split of $D$ into $D_{2}$,
$D_{11}$ and $D_{12}$ using splitter $B$ contained in the compound part $S$.
Here, $D_{11}$ is the part of $D$ that is reached both by $B$ and $S\setminus
B$, $D_{12}$ is the part of $D$ reached by $B$ but not by $S\setminus B$, and
$D_{2}$ is the part of $D$ reached by $S\setminus B$ but not by $B$. The size
of the splitter $B$ is at most half of the size of the compound block $S$
containing $B$. On the left, $B$ is the first part in $S$ (in the ordered
partition), on the right it is the last part. On the left, the order of
$B,S\setminus B$ gets propagated forward, the resulting order within $D$ is
$D_{12},D_{11},D_{2}$. On the right, the order of $S\setminus B,B$ gets
propagated forward, the resulting order within $D$ is $D_{2},D_{11},D_{12}$.
The two shades of blue indicate the pruning of edges explained in Section 4.

As in the original partition refinement framework, the algorithm then keeps
splitting the parts of the partition using so called _splitters_ which are
themselves parts in the partition. By splitting, we mean the operation of
making all parts of the partition forward-stable with respect to the splitter.
As in Paige and Tarjan’s algorithm, to maintain the set of splitters, the
algorithm also maintains another ordered partition $\mathcal{X}$ such that
$\mathcal{P}$ is a refinement of $\mathcal{X}$. Initially $\mathcal{X}$ has a
unique part that is equal to $Q$ and the algorithm will maintain the invariant
that $\mathcal{P}$ is forward-stable with respect to each part from
$\mathcal{X}$. As before, we call the parts of $\mathcal{X}$ that contain more
than a single part from $\mathcal{X}$ _compound parts_. The algorithm then
iteratively takes the first (in the order of the ordered partition) compound
block $S$ from $\mathcal{P}$ and defines the splitter $B$ as the smaller (in
size) of the first and last (in the order of the ordered partition) block in
$\mathcal{P}$ contained in $S$.

Once the splitter $B$ is defined, the algorithm aims to split each part $D$ of
the partition $\mathcal{P}$ (including $B$ itself) using $B$. As we aim at
making the partition forward-stable with respect to $B$ we would want to split
$D$ into $D_{1}:=D\cap\delta_{a}(B)$ and $D_{2}:=D\setminus D_{1}$. To
implement the three-way split, we however want to further refine $D$ by
$S\setminus B$. Recall that $S$ was a part in $\mathcal{X}$ that contained $B$
and that $\mathcal{P}$ is already forward-stable with respect to $S$ by the
invariant. The forward-stability of $D$ with respect to $S$ yields that all
states in $D_{2}$ are reached by $S\setminus B$ and thus $D$ is decomposed
into only three parts $D_{11}:=D_{1}\cap\delta_{a}(S\setminus B)$,
$D_{12}:=D_{1}\setminus D_{11}$, and $D_{2}:=D\setminus D_{1}$ when splitting
both with $B$ and $S\setminus B$. This three-way split can be implemented with
work proportional to the number of edges leaving $B$ (rather than $B$ and
$S\setminus B$). Together with the choice of $B$ being the smaller out of the
first and the last block contained in $S$, this is the main property that
allows to prove the nearly linear running time bound of the algorithm. The
order in which the sets $D_{11}$, $D_{12}$, and $D_{2}$ are put in
$\mathcal{P}$ replacing $D$ depends on whether $B$ was the first or the last
block in $S$ and is chosen so as to satisfy property 2 of Wheeler orders.
Intuitively, the order of $B$ and $S\setminus B$ is propagated forward to
$D_{11}$, $D_{12}$, and $D_{2}$, see Figure 2 for an illustration of this
“ordered” three-way split.

The algorithm keeps splitting the parts in $\mathcal{P}$ in this way until
$\mathcal{X}=\mathcal{P}$, i.e., until there are no compound blocks left.
Stopping at this point is correct by the invariant that the partition
$\mathcal{P}$ is forward-stable with respect to each part from
$\mathcal{X}=\mathcal{P}$, and, thus, forward-stable for $\mathcal{A}$.

#### Analysis.

The following lemma states that the claimed invariant, that every part of
$\mathcal{P}$ is forward-stable with respect to every part of $\mathcal{X}$,
holds. This follows immediately from the same property of the framework by
Paige and Tarjan and we include the proof in the appendix.

######  Lemma 3.1.

At the beginning of every iteration of the while loop in Algorithm 1, it holds
that every part of the ordered partition $\mathcal{P}$ is forward-stable with
respect to every part of $\mathcal{X}$.

We will now prove the core technical result of this section: The ordered
partition refinement algorithm in fact computes a partition that corresponds
to a Wheeler preorder.

######  Lemma 3.2.

Assume that Algorithm 1 is called on a quasi-Wheeler NFA
$\mathcal{A}=(Q,s,\delta)$. Then, at any step of the algorithm, the partition
$\mathcal{P}=\langle Q_{1},\dots,Q_{k}\rangle$ agrees with every Wheeler order
$\prec$ of the quotient automaton
$\mathcal{A}^{\prime}:=\mathcal{A}/_{\mathcal{P}^{\prime}}$, where
$\mathcal{P}^{\prime}$ denotes the coarsest forward-stable partition for
$\mathcal{A}$. That is, if $i<j,u\in P_{i},v\in P_{j}$ then $u\prec v$ for
every Wheeler order $\prec$ of $\mathcal{A}^{\prime}$.

######  Proof 3.3.

The initial partition $\mathcal{P}=\langle
Q_{\varepsilon},Q_{a_{1}},\dots,Q_{a_{k}}\rangle$ agrees with any Wheeler
order $\prec$ of $\mathcal{A}^{\prime}$. We will show by induction over the
number of steps of the while loop that this is the case in any step of the
algorithm. Assume that this is true before some intermediate iteration and let
us denote with $\mathcal{P}$ the ordered partition at that point. Now, let $S$
be the compound block and let $B$ be the splitter chosen in that iteration.
Let us call $\mathcal{P}^{\prime}$ the ordered partition after refining
$\mathcal{P}$ with $B$ and $S\setminus B$, i.e., at the end of that iteration.
We will prove that $\mathcal{P}^{\prime}$ agrees with any Wheeler order
$\prec$. As in the algorithm, for $D\in\mathcal{P}$, assume that
$a=\lambda(D)$ and let $D_{1}=D\cap\delta_{a}(B)$, $D_{2}=D\setminus D_{1}$,
and $D_{11}=D_{1}\cap\delta_{a}(S\setminus B)$ and $D_{12}=D_{1}\setminus
D_{11}$. Now let $u,v\in D$. If $u$ and $v$ are contained in the same set out
of the three sets $D_{12},D_{11},D_{2}$, nothing is to be shown. Hence, assume
that $u$ and $v$ are in two different sets out of the three sets. There are
three cases: (1) $u\in D_{11}$ and $v\in D_{2}$, (2) $u\in D_{12}$ and $v\in
D_{2}$, and (3) $u\in D_{12}$ and $v\in D_{11}$. Notice first that in all
three cases, there exists $x\in B$ with $u\in\delta_{a}(x)$. Now, recall that
$D$ is stable with respect to $S$ due to Lemma 3.1 and thus there exists $y\in
S\setminus B$ with $v\in\delta_{a}(y)$ in all three cases as well. Let us now
first assume that $B$ is the first block in $S$ in line 1. Then, as $B$
precedes all blocks in $S\setminus B$ in $\mathcal{P}$ and $\mathcal{P}$ is
consistent with any Wheeler order of $\mathcal{A}^{\prime}$, we have that
$x\prec y$ for any Wheeler order of $\mathcal{A}^{\prime}$. Then, property 2
of Wheeler orders implies that $u\prec v$ for any Wheeler order of
$\mathcal{A}^{\prime}$. In summary, as the algorithm replaces $D$ by
$D_{12},D_{11},D_{2}$ in this case, we deduce that $\mathcal{P}^{\prime}$
again agrees with each Wheeler order of $\mathcal{A}^{\prime}$. If, instead
$B$ is the last block in $S$ in line 1, then $B$ succeeds all blocks in
$S\setminus B$ in $\mathcal{P}$ and thus we can analogously deduce $v\prec u$
from property 2 of Wheeler orders and as the algorithm replaces $D$ by
$D_{2},D_{11},D_{12}$ in this case, we deduce that $\mathcal{P}^{\prime}$
agrees with every Wheeler order of $\mathcal{A}^{\prime}$ also in this case.

It remains to argue that the ordered partition refinement algorithm in fact
runs in the claimed running time bound of $O(|\delta|\log|Q|)$. This is
formalized in Lemma B.2 in the appendix. The two main ingredients are as
follows: (1) We always choose the smaller out of the first and the last part
contained in $S$ as $B$ and thus $|B|\leq|S|/2$. As a result every state is in
at most logarithmically many splitters. (2) We can implement the algorithm in
such a way that the work done in a refinement step with splitter $B$ is
proportional to the size of $B$ and the number of out-going transitions from
$B$. This can be argued completely analogously as done by Paige and Tarjan.
For the sake of completeness, we describe the main data structure details in
the appendix in Section B.2. In summary, we obtain the following theorem. See
1.1

##  4 Partition Refinement for Width-Optimal Co-lex Orders of DFAs

Cotumaccio and Prezza [9] propose a way of sidestepping the fact that there
may not be a Wheeler order for a given NFA. They show how to index general
NFAs using _partial orders_. For this purpose, they define co-lex orders for
NFAs as follows.

######  Definition 4.1 (Co-lex Order).

Let $\mathcal{A}=(Q,\delta,s)$ be an NFA. A _co-lex order_ for $\mathcal{A}$
is a strict partial order $\prec$ of $Q$ such that the source state precedes
all other states, i.e., $s\prec v$ for all $v\in Q\setminus\\{s\\}$, and, for
any pair $v\in\delta_{a}(u)$ and
$v^{\prime}\in\delta_{a^{\prime}}(u^{\prime})$:

  1. (1)

If $a<a^{\prime}$, then $v\prec v^{\prime}$.

  2. (2)

If $a=a^{\prime}$, $v\prec v^{\prime}$, and $u\neq u^{\prime}$, then $u\prec
u^{\prime}$.

The _width_ of a strict partial order $\prec$ is defined as the size of the
largest antichain, i.e. set of pairwise incomparable states, where two
distinct states $u,v\in Q$ are said to be incomparable if neither $u\prec v$
nor $v\prec u$ holds. Finding a smallest-width co-lex order of $\mathcal{A}$
has been of particular interest for constructing efficient indexes for pattern
matching on automata [9, 7, 8, 18]. We provide more context on co-lex orders
in Appendix C.1. For DFAs, the following order is known to be the smallest-
width co-lex order [9].

######  Definition 4.2.

Let $\mathcal{A}=(Q,\delta,s)$ be a DFA. The relation $\prec_{\mathcal{A}}$
over $Q$ is defined as follows. For $u,v\in Q$, $u\prec_{\mathcal{A}}v$ holds
if and only if $\alpha<\beta$ for all $\alpha\in S_{u}$ and $\beta\in S_{v}$.

In the above definition, the alphabet order $<$ over $\Sigma$ is extended to
the co-lexicographical order on strings. For the purpose of the co-lex order
$\prec_{\mathcal{A}}$, a state $v\in Q$ can thus be represented solely using
upper and lower bounds on $S_{v}$. In particular, for a state $v\in Q$, let
$\inf S_{v}$ and $\sup S_{v}$ be the greatest lower bound (infimum) and the
least upper bound (supremum) of $S_{v}$, respectively, which are possibly
left-infinite strings. We refer the reader to Appendix C.2 for a formal
definition of these concepts.

As shown by Kim et al. [18], the co-lex order $\prec_{\mathcal{A}}$ can be
characterized using the co-lex order of
$\operatorname{IS}_{\mathcal{A}}:=\\{\inf S_{v}:v\in Q\\}\cup\\{\sup
S_{v}:v\in Q\\}$.

######  Lemma 4.3 ([18, Theorem 10]).

Let $\mathcal{A}=(Q,\delta,s)$ be a DFA. Then, for any two distinct states
$u,v\in Q$, $u\prec_{\mathcal{A}}v$ holds if and only if
$\sup{S_{u}}\leq\inf{S_{v}}$.

for the purpose of indexing, we also need a minimum chain partition of
$\prec_{\mathcal{A}}$, i.e., a minimum-size partition of $Q$ such that the
states in each part are totally ordered under $\prec_{\mathcal{A}}$. As shown
by Kim et al. [18], it can be computed in linear time via a greedy algorithm
for the interval graph coloring problem based on the set
$\operatorname{IS}_{\mathcal{A}}$.

In this section, we give an algorithm for co-lex sorting the set
$\operatorname{IS}_{\mathcal{A}}$ that runs in nearly-linear time
$O(|\delta|\log|Q|)$ on any input-consistent DFA. This is a significant
improvement with respect to the best previously-known algorithms that run in
$O(|\delta|\cdot|Q|)$ and $O(|Q|^{2}\log|Q|)$ [18].

#### Outline.

Given an input DFA $\mathcal{A}=(Q,\delta,s)$, we first compute a pruned
automaton $\mathcal{A}^{\inf}=(Q,\delta^{\inf},s)$ that _encodes_ $\\{\inf
S_{v}:v\in Q\\}$ in a sense that walking back starting at a state $v\in Q$ on
the pruned transition $\delta^{\inf}$ yields its infimum string $\inf S_{v}$.
Similarly, we compute a pruned automaton
$\mathcal{A}^{\sup}=(Q,\delta^{\sup},s)$ that encodes the supremum strings. As
we will see, computing these sets takes $O(|\delta|\log|Q|)$ time each. On
these two pruned automata, we adopt an extension of the prefix-doubling
algorithm [19] to compute the co-lex order of
$\operatorname{IS}_{\mathcal{A}}$ in $O(|Q|\log|Q|)$ time in a similar way as
done by Kim et al. [18].

#### Pruning Algorithm.

The algorithm is identical to Algorithm 1 with the only difference that we
insert an additional pruning step, Algorithm 2, before Line 1 of the
algorithm. See Figure 2 for an illustration: If a state in $D$ is reached from
both $B$ and $S\setminus B$, we only keep the edges from the smaller (in the
sense of the ordered partition) of the two. This corresponds to changing
$\delta_{a}$ such that the blue portion of the figure shrinks to the dark blue
one.

// * prune $\mathcal{A}$ * //

if  _$B$ is the first block_ then delete transitions from $S\setminus B$ to
$D_{1}$ else from $B$ to $D_{1}$.

Algorithm 2 Pruning Step for Algorithm 1 inserted before Line 1

We inductively show that Algorithm 2 outputs a pruned automaton encoding the
set of infima $I:=\\{\inf S_{v}:v\in Q\\}$. For an integer $i\geq 1$, let
$\delta^{(i)}$ be the pruned transition at the end of the $i$-th iteration of
the while loop. Let us analogously denote with $\mathcal{X}^{(i)}$ and
$\mathcal{P}^{(i)}$ the state of the ordered partitions $\mathcal{X}$ and
$\mathcal{P}$ in the algorithm at the end of the $i$-th iteration. For
convenience, we also define $\delta^{(0)}=\delta$, $\mathcal{X}^{(0)}=\langle
Q\rangle$, and $\mathcal{P}^{(0)}=\langle
Q_{\varepsilon},Q_{a_{1}},\ldots,Q_{a_{k}}\rangle$. Lemma 3.1 and the
definition of the pruning step yield the following invariant on forward-
stability. At the end of every iteration $i$ of the while loop in Algorithm 1
when run together with the pruning step, it holds that every part of the
ordered partition $\mathcal{P}^{(i)}$ is forward-stable with respect to every
part in $\mathcal{X}^{(i)}$ in the automaton
$\mathcal{A}^{(i)}=(Q,\delta^{(i)},s)$. Intuitively speaking, the pruning step
removes transitions that do not originate from the co-lexicographically
smallest part in the sorted partition. Hence, we obtain the following lemma
(the proof is deferred to Appendix C.3).

######  Lemma 4.4.

Let $v\in Q$ be a state with $a=\lambda(v)$ and let
$A,A^{\prime}\in\mathcal{X}^{(i)}$ for some $i\geq 0$ be such that
$v\in\delta^{(i)}_{a}(A)\cap\delta_{a}(A^{\prime})$. Then either (i)
$A=A^{\prime}$ or (ii) $A$ precedes $A^{\prime}$ in $\mathcal{X}^{(i)}$.

Let $\mathcal{P}^{*}$ and $\delta^{*}$ be the ordered partition and the pruned
transition, respectively, obtained at the end of the algorithm’s execution.
From Lemma 4.4, we can see that for every state $v\in Q\setminus\\{s\\}$,
there exists a unique part $A\in\mathcal{P}^{*}$ such that
$v\in\delta_{\lambda(v)}^{*}(A)$. Combining this with Observation 4, we obtain
that a unique string can be obtained by walking backwards through the pruned
transitions $\delta^{*}$. For $u\in Q$, let $\alpha^{*}_{u}$ be the longest
(or possibly left-infinite) string that can be obtained in this way starting
from $u$. Since every transition comes from a co-lex smallest part, we can
obtain the following lemma; the proof is included in Appendix C.3.

######  Lemma 4.5.

For every $u\in Q$, $\alpha^{*}_{u}=\inf S_{u}$.

Similarly, we can compute the pruned automaton for the set of suprema $\\{\sup
S_{v}:v\in Q\\}$. The only difference is that we start with the partition
$\mathcal{P}^{\prime(0)}=\langle
Q_{a_{k}},\ldots,Q_{a_{1}},Q_{\varepsilon}\rangle$ with the reversed order. It
is simple to see the greatest string can be computed with this setting.

Regarding the time complexity, notice that the partition refinement algorithm
iterates through the same partitions as if it were run on $\mathcal{A}^{\inf}$
in the first place. Additional time is taken for the pruning step for deleting
transitions. This work can be done in $O(1)$ time per transition. Once a
transition is deleted, it will never be considered in the rest of the
execution and hence the additional work amortizes to $O(|\delta|)$.
Consequently, the asymptotic time complexity of the partition refinement
algorithm with pruning remains $O(|\delta|\log|Q|)$.

#### Computing Co-Lex Order of $\operatorname{IS}_{\mathcal{A}}$.

Once the two pruned automata $\mathcal{A}^{\inf}$ and $\mathcal{A}^{\sup}$ are
obtained, we can easily compute the co-lex order of
$\operatorname{IS}_{\mathcal{A}}$ by extending the well-known prefix-doubling
algorithm [19] in $O(|Q|\log|Q|)$ time. Instead of accessing via integer
indexes for the doubling procedure, each state keeps a pointer referring to
another (possibly the same) state that is $2^{k}$ hops away along its backward
walk. The details are described in Appendix C.4. In summary, we conclude this
section with the following theorem. See 1.2

##  5 Experimental results

We implemented our partition refinement algorithms in C++. We compared the
algorithm from Theorem 1.1 to the only (to the best of our knowledge) other
available tool for computing a sorted partition consistent with any Wheeler
order of the input NFA, the renaming heuristic from WGT [5]. For a fair
comparison, we only run the first part of the WGT recognizer and remove the
exponential time search that is used to subsequently compute a Wheeler order
of the states ending up in equivalence classes.222As observed empirically, the
partition computed by WGT is in some cases coarser than the partition computed
by our algorithm and is, thus, not necessarily forward-stable. We used the
Wheeler graph generator included in WGT to generate $7$ random input Wheeler
NFAs with $|Q|\in\\{5^{6}\cdot 2^{i}:i=0,\ldots,6\\}$ and $|\delta|=3|Q|$ (we
cannot generate much denser graphs since for Wheeler graphs
$\delta=O(|\Sigma|\cdot|Q|)$ and here $|\Sigma|=5$). Our experiments were run
on a server with Intel(R) Xeon(R) W-2245 CPU @ 3.90GHz with 8 cores and 128
gigabytes of RAM running Ubuntu 18.04 LTS 64-bit.

Figure 3: CPU time (left) and memory peak (right) for sorting seven Wheeler
NFAs using our partition refinement algorithm and the renaming heuristic
contained in the WGT recognizer software. Datasets generated using WGT
specifying seven different combinations of number of states and edges.

Figure 3 shows the running time and peak memory consumption of both
implementations. As expected, our partition refinement implementation shows a
slight super-linear behavior confirming the $O(|\delta|\cdot\log{|Q|})$ worst-
case running time of the algorithm. On the other hand, WGT shows a quadratic
behavior, which is better than the cubic $O(|\delta|\cdot|Q|^{2})$ bound for
the Forward Algorithm of Alanko et. al [2], but between $\approx 100\times$ to
$\approx 10000\times$ slower than our implementation. In terms of peak memory,
both implementations behave linearly with respect to the automaton’s size with
a $3\times$ advantage in favor of our implementation. On the largest input
instance containing one million states, our implementation computes the
Wheeler preorder in about seven seconds. In a second experiment, we show that
our implementation of the algorithm from Theorem 1.2 can prune a pangenomic
DFA containing over 51 million states and 53 million edges in 355 seconds with
a peak memory of 33.2 Gb.

## References

  * [1] Jarno Alanko, Giovanna D’Agostino, Alberto Policriti, and Nicola Prezza.  Regular languages meet prefix sorting.  In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 911–930. SIAM, 2020.
  * [2] Jarno Alanko, Giovanna D’Agostino, Alberto Policriti, and Nicola Prezza.  Wheeler languages.  Information and Computation, 281:104820, 2021.  URL: https://www.sciencedirect.com/science/article/pii/S0890540121001504, doi:https://doi.org/10.1016/j.ic.2021.104820.
  * [3] Christel Baier and Joost-Pieter Katoen.  Principles of model checking.  MIT Press, 2008.
  * [4] Uwe Baier.  Linear-time Suffix Sorting - A New Approach for Suffix Array Construction.  In Roberto Grossi and Moshe Lewenstein, editors, 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), volume 54 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:12, Dagstuhl, Germany, 2016. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2016/6069, doi:10.4230/LIPIcs.CPM.2016.23.
  * [5] Kuan-Hao Chao, Pei-Wei Chen, Sanjit A Seshia, and Ben Langmead.  WGT: Tools and algorithms for recognizing, visualizing and generating wheeler graphs.  bioRxiv, pages 2022–10, 2022.
  * [6] Computational Pan-Genomics Consortium.  Computational pan-genomics: status, promises and challenges.  Briefings in bioinformatics, 19(1):118–135, 2018.
  * [7] Nicola Cotumaccio.  Graphs can be succinctly indexed for pattern matching in $O(|E|^{2}+|V|^{5/2})$ time.  In Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagristà, and James A. Storer, editors, Data Compression Conference, DCC 2022, Snowbird, UT, USA, March 22-25, 2022, pages 272–281. IEEE, 2022.  doi:10.1109/DCC52660.2022.00035.
  * [8] Nicola Cotumaccio, Giovanna D’Agostino, Alberto Policriti, and Nicola Prezza.  Co-lexicographically ordering automata and regular languages. Part I, 2022.  URL: https://arxiv.org/abs/2208.04931, doi:10.48550/ARXIV.2208.04931.
  * [9] Nicola Cotumaccio and Nicola Prezza.  On indexing and compressing finite automata.  In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 \- 13, 2021, pages 2585–2599. SIAM, 2021.  doi:10.1137/1.9781611976465.153.
  * [10] Robert P. Dilworth.  A Decomposition Theorem for Partially Ordered Sets.  Annals of Mathematics, 51(1):161–166, 1950.  doi:10.2307/1969503.
  * [11] Massimo Equi, Veli Mäkinen, and Alexandru I. Tomescu.  Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless seth fails.  In Tomáš Bureš, Riccardo Dondi, Johann Gamper, Giovanna Guerrini, Tomasz Jurdziński, Claus Pahl, Florian Sikora, and Prudence W.H. Wong, editors, SOFSEM 2021: Theory and Practice of Computer Science, pages 608–622, Cham, 2021. Springer International Publishing.
  * [12] Massimo Equi, Veli Mäkinen, Alexandru I Tomescu, and Roberto Grossi.  On the complexity of string matching for graphs.  ACM Transactions on Algorithms, 19(3):1–25, 2023.
  * [13] Travis Gagie, Paweł Gawrychowski, Juha Kärkkäinen, Yakov Nekrich, and Simon J. Puglisi.  Lz77-based self-indexing with faster pattern matching.  In Alberto Pardo and Alfredo Viola, editors, LATIN 2014: Theoretical Informatics, pages 731–742, Berlin, Heidelberg, 2014. Springer Berlin Heidelberg.
  * [14] Travis Gagie, Giovanni Manzini, and Jouni Sirén.  Wheeler graphs: A framework for BWT-based data structures.  Theoretical computer science, 698:67–78, 2017.
  * [15] Travis Gagie, Gonzalo Navarro, and Nicola Prezza.  Optimal-time text indexing in bwt-runs bounded space.  In Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1459–1477, 2018.  URL: https://epubs.siam.org/doi/abs/10.1137/1.9781611975031.96, arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611975031.96, doi:10.1137/1.9781611975031.96.
  * [16] Daniel Gibney and Sharma V. Thankachan.  On the hardness and inapproximability of recognizing wheeler graphs.  In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany, volume 144 of LIPIcs, pages 51:1–51:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [17] Paris C. Kanellakis and Scott A. Smolka.  CCS expressions, finite state processes, and three problems of equivalence.  Inf. Comput., 86(1):43–68, 1990.
  * [18] Sung-Hwan Kim, Francisco Olivares, and Nicola Prezza.  Faster prefix-sorting algorithms for deterministic finite automata, 2023\.  To appear in the Proceedings of CPM 2023.  arXiv:2304.10962.
  * [19] Udi Manber and Gene Myers.  Suffix Arrays: A New Method for on-Line String Searches.  In Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 319–327, 1990.  doi:10.1137/0222058.
  * [20] Veli Mäkinen, Gonzalo Navarro, Jouni Sirén, and Niko Välimäki.  Storage and retrieval of highly repetitive sequence collections.  Journal of computational biology : a journal of computational molecular cell biology, 17:281–308, 03 2010.  doi:10.1089/cmb.2009.0169.
  * [21] Gonzalo Navarro.  Compact Data Structures – A practical approach.  Cambridge University Press, 2016.  ISBN 978-1-107-15238-0. 536 pages.
  * [22] Robert Paige and Robert Endre Tarjan.  Three partition refinement algorithms.  SIAM J. Comput., 16(6):973–989, 1987.  doi:10.1137/0216062.
  * [23] Jouni Sirén, Jean Monlong, Xian Chang, Adam M Novak, Jordan M Eizenga, Charles Markello, Jonas A Sibbesen, Glenn Hickey, Pi-Chuan Chang, Andrew Carroll, et al.  Pangenomics enables genotyping of known structural variants in 5202 diverse genomes.  Science, 374(6574):abg8871, 2021.
  * [24] Jouni Sirén, Niko Välimäki, and Veli Mäkinen.  Indexing graphs for path queries with applications in genome research.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 11(2):375–388, 2014.  doi:10.1109/TCBB.2013.2297101.
  * [25] Peter Weiner.  Linear pattern matching algorithms.  In Switching and Automata Theory, 1973. SWAT’08. IEEE Conference Record of 14th Annual Symposium on, pages 1–11. IEEE, 1973.
  * [26] Ryan Williams.  A new algorithm for optimal 2-constraint satisfaction and its implications.  Theoretical Computer Science, 348(2-3):357–365, 2005.

##  Appendix A Forward-Stability and Bisimulation

######  Definition A.1 (Bisimulation).

Given an NFA $\mathcal{A}=(Q,\delta,s)$ over a finite alphabet $\Sigma$, a
bisimulation on $\mathcal{A}$ is a relation $B\subseteq Q\times Q$ such that
for all $(u,v)\in B$ and $a\in\Sigma$, it holds that:

  * •

If $u^{\prime}\in\delta_{a}(u)$, then there exists
$v^{\prime}\in\delta_{a}(v)$ such that $(u^{\prime},v^{\prime})\in B$.

  * •

If $v^{\prime}\in\delta_{a}(v)$, then there exists
$u^{\prime}\in\delta_{a}(u)$ such that $(u^{\prime},v^{\prime})\in B$.

Any bisimulation $B$ on $\mathcal{A}$ partitions $V$ into sets $P$ that
correspond to the weakly connected components of the directed graph $(V,B)$.
We denote the resulting partition of $V$ with $\mathcal{P}_{B}$. Note that the
relation $\bar{B}:=\bigcup_{P\in\mathcal{P}_{B}}P^{2}$ is again a bisimulation
that we call the _closure_ of $B$.

######  Definition A.2 (Bisimilarity).

Given an NFA $\mathcal{A}=(Q,\delta,s)$ over a finite alphabet $\Sigma$, the
_bisimilarity_ of $\mathcal{A}$ is the union of all bisimulations on
$\mathcal{A}$.

It is clear that the bisimilarity of $\mathcal{A}$ is again a bisimulation on
$\mathcal{A}$ and it partitions $Q$ into equivalence classes, we write
$\mathcal{P}_{\sim}$ for the _bisimilarity partition_ on $G$ consisting of the
partition with the equivalence classes as its parts.

Given an NFA $\mathcal{A}=(Q,\delta,s)$ over a finite alphabet $\Sigma$, we
define the NFA $\mathcal{A}^{-1}=(Q,\delta^{-1},s)$ as the automaton with the
same state set $Q$ and the transition function $\delta^{-1}$ that is defined
as $\delta^{-1}(u,a):=\delta^{-1}_{a}(u)$ for all $u\in Q$ and $a\in\Sigma$.

######  Lemma A.3.

Given an NFA $\mathcal{A}=(Q,\delta,s)$ over a finite alphabet $\Sigma$ and
any bisimulation $B$ on $\mathcal{A}^{-1}$. Then, the partition
$\mathcal{P}_{B}$ is forward-stable on $\mathcal{A}$.

######  Proof A.4.

Let $S,T$ be two parts of $\mathcal{P}_{B}$. We show that
$S\subseteq\delta_{a}(T)$ or $S\cap\delta_{a}(T)=\emptyset$. Assume for
contradiction that this is not the case, i.e., that
$S\cap\delta_{a}(T)\neq\emptyset$ and $S\setminus\delta_{a}(T)\neq\emptyset$
holds. Hence, there exists $u\in S\cap\delta_{a}(T)$ and $v\in
S\setminus\delta_{a}(T)$. As both $u\in S$ and $v\in S$, it follows that
$(u,v)\in\bar{B}$. Notice however that $u\in S\cap\delta_{a}(T)$ and thus
there exists $u^{\prime}\in\delta_{a}^{-1}(u)\cap T$. Hence by the
bisimulation $\bar{B}$, there exists $v^{\prime}\in\delta_{a}^{-1}(v)$ such
that $(u^{\prime},v^{\prime})\in\bar{B}$. As a consequence also $v^{\prime}\in
T$, a contradiction to $v\notin\delta_{a}(T)$.

######  Lemma A.5.

Given an NFA $\mathcal{A}=(Q,\delta,s)$ over a finite alphabet $\Sigma$, any
forward-stable partition $\mathcal{P}$ on $G$ induces a bisimulation
$B_{\mathcal{P}}:=\\{(u,v)\in Q\times Q:u,v\in S,S\in\mathcal{P}\\}$.

######  Proof A.6.

We just need to check that $B_{\mathcal{P}}$ indeed is a bisimulation. Let
$(u,v)\in B_{\mathcal{P}}$, then by definition $u,v\in S$ for some part
$S\in\mathcal{P}$. Now assume that there exists
$u^{\prime}\in\delta^{-1}_{a}(u)$ for some $a\in\Sigma$. Let $T$ be the part
of $\mathcal{P}$ such that $u^{\prime}\in T$. By forward-stability it follows
that $S\subseteq\delta_{a}(T)$ and thus there exists $v^{\prime}\in T$ such
that $v^{\prime}\in\delta^{-1}_{a}(v)$. By the definition of $B_{\mathcal{P}}$
it furthermore follows that $(u^{\prime},v^{\prime})\in B_{\mathcal{P}}$. The
second condition for $B_{\mathcal{P}}$ being a bisimulation is shown in a
symmetric way.

######  Corollary A.7.

Given an NFA $\mathcal{A}=(Q,\delta,s)$ over a finite alphabet $\Sigma$, the
coarsest forward-stable partition $\mathcal{Q}$ on $\mathcal{A}$ is identical
to the bisimilarity partition $\mathcal{P}_{\sim}$ on $\mathcal{A}^{-1}$.

######  Proof A.8.

Assume for contradiction that $\mathcal{Q}\neq\mathcal{P}_{\sim}$. Recall that
$\mathcal{P}_{\sim}$ is forward-stable due to Lemma A.3 and thus
$|\mathcal{Q}|\leq|\mathcal{P}_{\sim}|$ as $\mathcal{Q}$ is the coarsest
forward-stable partition. Now, $\mathcal{Q}\neq\mathcal{P}_{\sim}$ and
$|\mathcal{Q}|\leq|\mathcal{P}_{\sim}|$ imply that there exist $u,v\in
S\in\mathcal{Q}$ such that $u\in P_{1}$ and $v\in P_{2}$ with
$P_{1},P_{2}\in\mathcal{P}_{\sim}$ and $P_{1}\neq P_{2}$. By Lemma A.5, it
follows that $B_{\mathcal{Q}}$ is a bisimulation and $(u,v)\in
B_{\mathcal{Q}}$. As $\mathcal{P}_{\sim}$ is defined as the union of all
bisimulations this is however a contradiction to $u$ and $v$ being in
different parts in $\mathcal{P}_{\sim}$.

##  Appendix B Deferred Material for Section 3

###  B.1 Deferred Proofs

See 3.1

######  Proof B.1.

Note that the property holds before the first iteration as $\mathcal{X}$
contains $Q$ as its unique part then and every state is assumed to have at
least one in-going transition. Inductively assume that the property also holds
before some intermediate iteration of the while loop. Assume that $S$ is the
block from $\mathcal{X}$ chosen in that iteration. The only modification made
to $\mathcal{X}$ is the replacement of $S$ with $B,S\setminus B$ or
$S\setminus B,B$ in line 1. As we have to show that every part of
$\mathcal{P}$ is stable with respect to every part of $\mathcal{X}$ at the end
of the iteration. For the blocks $B$ and $S\setminus B$, this is clear by the
refinement step of the algorithm. For the other blocks in $\mathcal{X}$ this
follows from the induction hypothesis and the fact that every subset of a
forward-stable set is again forward-stable.

######  Lemma B.2.

The following two hold:

  1. (1)

A refinement step with splitter $B$ takes $O(|B|+\sum_{a\in\Sigma}\sum_{v\in
B}|\delta_{a}(v)|)$ time.

  2. (2)

Every $v\in Q$ is in at most $\log|Q|+1$ different splitters $B$ used for the
refinement step.

Hence, the ordered partition refinement algorithm can be implemented in
$O(|\delta|\cdot\log|Q|)$.

######  Proof B.3.

Part (1) can be achieved by an efficient implementation that stores the
partitions $\mathcal{P}$ and $\mathcal{X}$ in a specific data structure (based
on double-linked lists) that is identical to the one described by Paige and
Tarjan. We include more details in the following subsection. The data
structure guarantees that every refinement step takes $O(1)$ per state
contained in the splitter $B$ and $O(1)$ per transition leaving $B$, i.e., the
refinement by splitter $B$ takes $O(|B|+\sum_{a\in\Sigma}\sum_{v\in
B}|\delta_{a}(v)|)$. For part (2) notice that the splitter sets, say,
$B_{1},\ldots,B_{\ell}$ in which a fixed state $v$ is contained satisfy
$|B_{i}|\geq|B_{i+1}|/2$ for each $i\in[\ell-1]$. As $|B_{1}|\leq|Q|$, it
follows that $v$ is in at most $\ell\leq\log|Q|+1$. Let us now call
$\mathcal{B}$ the set of all splitters used by the algorithm. The total time
needed for all refinement steps can thus be bounded by

$\displaystyle\sum_{B\in\mathcal{B}}$ $\displaystyle O\Big{(}|B|+\sum_{v\in
B}\sum_{a\in\Sigma}|\delta_{a}(v)|\Big{)}=\sum_{v\in
Q}\sum_{B\in\mathcal{B}:v\in B}O(1)+O\Big{(}\sum_{v\in
Q}\sum_{B\in\mathcal{B}:v\in B}\sum_{a\in\Sigma}|\delta_{a}(v)|\Big{)}$
$\displaystyle=O(|Q|\log|Q|)+O\Big{(}\log|Q|\cdot\sum_{v\in
Q}\sum_{a\in\Sigma}|\delta_{a}(v)|\Big{)}=O(|\delta|\cdot\log|Q|).$

###  B.2 Data Structure Details

The nearly linear time implementation can be achieved in the same way as was
described already by Paige and Tarjan [22]. We briefly repeat the most
important parts of their implementation. Each element $u\in Q$ is represented
by a record. Each pair $u,v\in Q$ such that $v\in\delta_{a}(u)$ is represented
by a record, which we call an _edge_ (labeled $a$). Each part in partition
$\mathcal{P}$ and in partition $\mathcal{X}$ is represented by a record. A
part $S\in\mathcal{X}$ is called _simple_ if it contains only a single part of
$\mathcal{P}$ and _compound_ otherwise. Each edge $u,v\in Q$ s.t.
$v\in\delta_{a}(u)$ points to element $u$. Each element $v$ points to a list
of the edges $u,v$ s.t. $v\in\delta_{a}(u)$, which allows scanning
$\delta_{a}^{-1}(\\{y\\})$ in time proportional to its size. Each part of
$\mathcal{P}$ has an associated integer equal to its size, and points to a
doubly linked list of the elements in it (which allows for constant deletion
time). Each element points to the part in $\mathcal{P}$ that contains it. Each
part in $\mathcal{X}$ points to a doubly linked list of the parts of
$\mathcal{P}$ in it. Each part of $\mathcal{P}$ points to the part of
$\mathcal{X}$ that contains it. Additionally, $\mathcal{C}$ is a set of
compound parts of $\mathcal{X}$, which is initialized to $Q$ and maintained
accordingly.

For the three-way splitting, for every part $S\in\mathcal{X}$ and every
element $x\in\delta_{a}(S)$, we maintain a record containing
$\texttt{count}_{a}(x,S)=|S\cap\delta_{a}^{-1}(x)|$, and $x$ points to
$\texttt{count}_{a}(x,S)$. Each edge $y,x$ labeled $a$ (i.e.,
$x\in\delta_{a}(y)$) such that $y\in S$ points to $\texttt{count}_{a}(x,S)$.
Initially, $x$ points to $\texttt{count}_{a}(x,Q)=|\delta_{a}^{-1}(x)|$ and
each edge $y,x$ labeled $a$ also points to $\texttt{count}_{a}(x,Q)$.

The space needed for all the data structures is $O(|\delta|)$, the total
number of transitions. The initialization time is also $O(|\delta|)$. The
algorithm stops when $\mathcal{C}=\emptyset$ or equivalently
$\mathcal{P}=\mathcal{X}$. In what follows, we specify the refinement step in
more detail.

#### Implementation of Three-Way Split.

Copy the elements of $B$ into a temporary set $B^{\prime}$. Then, for each
$a\in\Sigma$:

  1. 1.

(compute $\delta_{a}(B)$) Compute $\delta_{a}(B)$ by scanning the edges $y,x$
labeled $a$ for every $y\in B$, and adding each newly found element to
$\delta_{a}(B)$. To avoid duplicates, mark encountered elements and link them
together for later unmarking. During the scan, create and update
$\texttt{count}_{a}(x,B)=|\\{y\in B:x\in\delta_{a}(y)\\}|$, and let $x$ point
to this record.

  2. 2.

(refine $\mathcal{P}$ by $B$ w.r.t. $\delta_{a}$) Split each block
$D\in\mathcal{P}$ that contains some element of $\delta_{a}(B)$ into $D_{1}$
and $D_{2}$. Do so by scanning the elements of $\delta_{a}(B)$ one by one. For
$x\in\delta_{a}(B)$, determine the block $D$ that contains it, create an
associated block $D^{\prime}$ (if it does not already exist) and move $x$ to
$D^{\prime}$. During the scan, construct and maintain a list of split blocks.
After the scan, process the list: mark $D^{\prime}$ as no longer associated
with $D$, delete $D$ if it is empty; if $D$ is not empty and the block of
$\mathcal{X}$ containing $D$ and $D^{\prime}$ has been made compound by the
split, add this block to $\mathcal{C}$.

  3. 3.

(compute $\delta_{a}(B)\setminus\delta_{a}(S\setminus B)$) Scan the edges
$y,x$ labeled $a$ where $y\in B^{\prime}$. To process one such edge, determine
$\texttt{count}_{a}(x,B)$ (to which $x$ points) and $\texttt{count}_{a}(x,S)$
(to which $y,x$ points). If these integers are equal, add $x$ to
$\delta_{a}(B)\setminus\delta_{a}(S\setminus B)$ (if not added already).

  4. 4.

(refine $\mathcal{P}$ by $S\setminus B$ w.r.t. $\delta_{a}$) Proceed as in
(b), but by scanning $\delta_{a}(B)\setminus\delta_{a}(S\setminus B)$.

  5. 5.

(update counts) Scan the edges $y,x$ labeled $a$ where $y\in B^{\prime}$.
Process them one by one, by decreasing $\texttt{count}_{a}(x,S)$ (to which
$y,x$ points) by one. If the count becomes zero, delete the record. Make $y,x$
point to $\texttt{count}_{a}(x,B)$ (to which $x$ points).

Discard $B^{\prime}$.

##  Appendix C Deferred Material for Section 4

###  C.1 Motivation for computing the smallest-width partial order

For an NFA $\mathcal{A}=(Q,\delta,s)$ and a co-lex order $\prec$ for
$\mathcal{A}$, the width $p$ of $\prec$ is defined as the size of the largest
antichain, i.e., set of pairwise _incomparable_ states, where we say that two
states $u,v\in Q$ are incomparable if neither $u\prec v$ nor $v\prec u$ holds.
According to Dilworth’s theorem [10], the width of the co-lex order $\prec$ is
equal to the cardinality of the smallest _$\prec$ -chain decomposition_ of
$Q$. Here, a partition $\\{Q_{i}\\}_{i\in[k]}$ of $Q$ is a $\prec$-chain
decomposition of $Q$, if $Q_{i}$ is a $\prec$-chain for every $i\in[k]$, where
a subset $S\subseteq Q$ is a $\prec$-chain if $\prec$ is a strict total order
on $S$. Clearly, the width of a Wheeler order is 1 as no two states are
incomparable.

Cotumaccio and Prezza [9] call an NFA $\mathcal{A}$ _$p$ -sortable_ if there
exists a co-lex order for $\mathcal{A}$ that has width $p$. They then show
that this parameter $p$ determines the complexity of a series of problems
related to storing and indexing the automaton $\mathcal{A}$. As an example,
they show how to store a $p$-sortable NFA using
$\lceil\log|\Sigma|\rceil+\lceil\log p\rceil+2$ bits per transition by
extending the Burrows-Wheeler transform [9, Theorem 4.1] from strings to NFAs.
The construction of this data structure however assumes to have the co-lex
order $\prec$ and a corresponding $\prec$-chain decomposition of size $p$ as
input. Unfortunately, it is NP-hard to determine if a given NFA is
$p$-sortable for a given $p$. This follows from the NP-completeness of
recognizing Wheeler NFAs, i.e., $1$-sortable NFAs. As a consequence, it is
unrealistic to assume that one can compute a co-lex order $\prec$ and a
corresponding $\prec$-chain decomposition for a given NFA. For DFAs however,
Cotumaccio and Prezza showed that the co-lex order of minimum width is unique
and can be computed in $O(|\delta|^{2}+|Q|^{5/2})$ time. Kim et al. [18]
improved this running time by describing two algorithms running in
$O(|\delta|\cdot|Q|)$ and $O(|Q|^{2}\cdot\log|Q|)$ time on arbitrary DFAs, and
an algorithm running in $O(|\delta|\cdot\log|Q|)$ time on acyclic DFAs. All
the mentioned algorithms, together with the co-lex order $\prec$ of minimum
width $p$, also compute a $\prec$-chain decomposition of size $p$.

###  C.2 Infimum and Supremum strings

To define infimum and supremum strings, we first have to introduce left-
infinite strings that we denote with $\Sigma^{\omega}$. A _left-infinite
string_ over the alphabet $\Sigma$ is a sequence of letters from $\Sigma$ of
infinite countable length that can be constructed by appending letters to the
left of the empty string $\varepsilon$. For a string $\alpha\in\Sigma^{*}$,
the notation $\alpha^{\omega}$ is used to denote the string consisting of an
infinite number of copies of the string $\alpha$. We denote with
$\Sigma^{\bullet}:=\Sigma^{*}\cup\Sigma^{\omega}$ the set of all finite and
left-infinite strings.

######  Definition C.1 (Infimum and Supremum).

For a possibly infinite set of finite strings $S\subseteq\Sigma^{*}$ over an
alphabet $\Sigma$, we define

$\displaystyle\inf S$ $\displaystyle:=\gamma\in\Sigma^{\bullet}\text{ s.t.\
}\gamma\geq\beta\text{ for all }\beta\in\Sigma^{\bullet}\text{ with
}\beta\leq\alpha\text{ for all }\alpha\in S,\text{ and }$ $\displaystyle\sup
S$ $\displaystyle:=\gamma\in\Sigma^{\bullet}\text{ s.t.\
}\gamma\leq\beta\text{ for all }\beta\in\Sigma^{\bullet}\text{ with
}\beta\geq\alpha\text{ for all }\alpha\in S.$

Notice that the infimum and supremum of a string set $S_{v}$ for some $v\in Q$
possibly have infinite length, see Figure 4 for a simple example. Intuitively
speaking, one can encode $\inf S_{v}$ (and $\sup S_{v}$ analogously) using the
NFA: The string is obtained by walking backwards from $v\in Q$ by prepending
the label of the in-going transition. When there are more than one in-going
transitions, we take an _appropriate_ branch to yield the smallest string,
which can be determined only after sorting the states by their infimum
strings. When this walk forms a loop then a string with infinite length is
obtained.

$s$$1$$2$$b$$a$$a$

Figure 4: An example DFA with a node ($v=2$) whose infimum string $\inf
S_{v}=a^{\omega}$ is of infinite length.

###  C.3 Deferred Proofs

See 4.4

######  Proof C.2.

We prove the statement by induction over $i$. The base case, i.e., $i=0$,
corresponds to the beginning of the first iteration, then $Q$ is the only
element in $\mathcal{X}$ and thus $Q=A=A^{\prime}$. Let us now assume that the
claim holds for $i\geq 0$, i.e.,
$v\in\delta^{(i)}_{a}(P)\cap\delta_{a}(P^{\prime})$ for some
$P,P^{\prime}\in\mathcal{X}^{(i)}$ implies $P=P^{\prime}$ or $P<P^{\prime}$.
We now prove the statement for $i+1$, more precisely, we show that, if
$A>A^{\prime}$ for two parts from $\mathcal{X}^{(i+1)}$, then
$v\notin\delta^{(i+1)}_{a}(A)\cap\delta_{a}(A^{\prime})$ (which is the
contraposition of the claim to be shown). Now let $A$ and $A^{\prime}$ be two
parts from $\mathcal{X}^{(i+1)}$ with $A>A^{\prime}$ and let
$S\in\mathcal{X}^{(i)}$ be the part chosen in line 1 in iteration $i+1$ of the
algorithm. There are two cases. (1) Assume that at least one of $A$ and
$A^{\prime}$ is not contained in $S$. Then, there are two parts $P$ and
$P^{\prime}$ in $\mathcal{X}^{(i)}$ such that $A\subseteq P$ and
$A^{\prime}\subseteq P^{\prime}$ and $P>P^{\prime}$. By the induction
hypothesis, it follows that
$v\notin\delta^{(i)}_{a}(P)\cap\delta_{a}(P^{\prime})$. This yields
$v\notin\delta^{(i+1)}_{a}(A)\cap\delta_{a}(A^{\prime})$, as
$\delta^{(i+1)}_{a}(P)\subseteq\delta^{(i)}_{a}(P)$,
$\delta^{(i+1)}_{a}(A)\subseteq\delta^{(i+1)}_{a}(P)$, as well as
$\delta_{a}(A^{\prime})\subseteq\delta_{a}(P^{\prime})$. (2) Now assume that
both $A$ and $A^{\prime}$ are contained in $S$. Then one of $A$ and
$A^{\prime}$ must be $B$ and the other one $S\setminus B$. Following
Observation 4, all parts of $\mathcal{P}^{(i)}$ are forward-stable with
respect to $S$ and hence $v\in\delta^{(i)}_{a}(A)$ implies
$v\in\delta^{(i)}_{a}(A^{\prime})$. As a consequence of the pruning step, the
transitions from $A$ to $v$ are then deleted in iteration $i+1$ and hence
$v\notin\delta^{(i+1)}_{a}(A)$ and consequently
$v\notin\delta^{(i+1)}_{a}(A)\cap\delta_{a}(A^{\prime})$.

See 4.5

######  Proof C.3.

In addition to $\delta^{(i)}$, $\mathcal{X}^{(i)}$, and $\mathcal{P}^{(i)}$,
let $\prec^{(i)}$ be the strict partial order induced by ordered partition
$\mathcal{P}^{(i)}$; i.e., for $u,v\in Q$, $u\prec^{(i)}v$ if and only if
$u\in A$ and $v\in A^{\prime}$ for two parts $A$ and $A^{\prime}$ in
$\mathcal{P}^{(i)}$ such that $A$ precedes $A^{\prime}$. For convenience, we
also define $\prec^{(0)}=\\{(u,v)\in Q^{2}:\lambda(u)<\lambda(v)\\}$. First,
we claim that $\prec^{(i)}$ is a co-lex order of $\mathcal{A}^{(i)}$.

######  Claim 1.

The strict partial order $\prec^{(i)}$ is a co-lex order for the automaton
$\mathcal{A}^{(i)}=(Q,\delta^{(i)},s)$.

We will show by induction over $i$ that $\prec^{(i)}$ is a co-lex order for
$\mathcal{A}^{(i)}$. The order $\prec^{(0)}$ corresponding to the partition
$\mathcal{P}^{(0)}=\langle Q_{\varepsilon},Q_{a_{1}},\dots,Q_{a_{k}}\rangle$
clearly is a co-lex order for $\mathcal{A}^{(0)}$ as Axiom (1) in Definition
4.1 is satisfied and the premise of Axiom (2) never holds. Assume now that
$\prec^{(i)}$ is a co-lex order for some intermediate iteration $i$. We will
now prove that the order $\prec^{(i+1)}$ corresponding to
$\mathcal{P}^{(i+1)}$ is a co-lex order. In order to show that $\prec^{(i+1)}$
is a co-lex order, we have to show that Axiom (2) is maintained. More
precisely, for every pair of states $u,v$ with $\lambda(u)=\lambda(v)=a$ for
which $u\prec^{(i+1)}v$, we have to show that $x\prec^{(i+1)}y$ for all
distinct predecessors $x$ and $y$ of $u$ and $v$, respectively. Hence, let
$u,v\in D$ for $D\in\mathcal{P}^{(i)}$, as otherwise the statement follows by
the induction hypothesis. As in the algorithm, let
$D_{1}=D\cap\delta^{(i+1)}_{a}(B)$, $D_{2}=D\setminus D_{1}$, and
$D_{11}=D_{1}\cap\delta^{(i+1)}_{a}(S\setminus B^{\prime}))$ and
$D_{12}=D_{1}\setminus D_{11}$, where $S$ is the compound block from
$\mathcal{X}^{(i)}$ and $B$ be is the splitter chosen in iteration $i+1$.
Notice that due to the pruning step, $D_{11}=\emptyset$. If $u$ and $v$ are
contained in the same out of the two sets $D_{12}$ and $D_{2}$, nothing is to
be shown. Hence, assume that $u$ and $v$ are in different sets, w.l.o.g., say
$u\in D_{12}$ and $v\in D_{2}$. Now let $x$ and $y$ be two distinct
predecessors of $u$ and $v$ respectively.

According to Lemma 4.4, all predecessors of $u$ and $v$, and hence also $x$
and $y$, are in a unique part $A$ and $A^{\prime}$ of $\mathcal{X}^{(i+1)}$.
As $u\in D_{12}$ and $v\in D_{2}$, it follows that $x\in B$ and $y\in
S\setminus B$. Let us now first assume that $B$ is the first block in $S$ in
line 1, i.e., the decided order of $u$ and $v$ is $u\prec^{(i+1)}v$ as
$D_{12}$ precedes $D_{2}$ in $\mathcal{P}^{(i+1)}$. As $B$ precedes all blocks
in $S\setminus B$ in $\mathcal{P}^{(i)}$, we have that $x\prec^{(i)}y$ and
thus also $x\prec^{(i+1)}y$. If, instead $B$ is the last block in $S$ in line
1, i.e., the decided order of $u$ and $v$ is $v\prec^{(i+1)}u$ as $D_{2}$
precedes $D_{12}$ in $\mathcal{P}^{(i+1)}$. As $B$ succeeds all blocks in
$S\setminus B$ in $\mathcal{P}^{(i)}$, we have that $y\prec^{(i)}x$ and thus
also $y\prec^{(i+1)}x$. In summary, property 2 of co-lex orders holds in both
cases and thus $\prec^{(i+1)}$ is a co-lex order for $\mathcal{A}^{(i+1)}$.

We can now prove Lemma 4.5 using the fact that $\prec^{(i)}$ is a co-lex order
of $\mathcal{A}^{(i)}$. First, we show that $\alpha^{*}_{u}$ is a lower bound
on all strings in $S_{u}$, i.e., for every $\alpha\in S_{u}$, it holds that
$\alpha^{*}_{u}\leq\alpha$. Assume for contradiction that there is a string
$\alpha\in S_{u}$ such that $\alpha<\alpha^{*}_{u}$. Let $1\leq i\leq|\alpha|$
be the smallest integer such that, for some $v_{1},v_{2}\in Q$,
$\alpha[1..i-1]\in S_{v_{2}}$, $v_{1}\in\delta_{\alpha[i]}(v_{2})$, and
$u\in\delta^{*}_{\alpha^{\prime}}(v_{1})$ where
$\alpha^{\prime}=\alpha[i+1..|\alpha|]$. Intuitively, $v_{1}$ is the farthest
state (from the back) on the path spelling $\alpha$ that can reach $u$ in the
pruned automaton $\mathcal{A}^{*}$. Note that such states $v_{1}$ and $v_{2}$
must exist as otherwise $\alpha=\alpha^{*}_{u}$. Clearly, $v_{1}\neq s$ as it
has an in-going transition. Now by Lemma 4.4, there exists a state $v_{3}\in
Q$ with $v_{1}\in\delta^{*}_{\alpha[i]}(v_{3})$. Notice that by the minimality
of $i$, it holds that $v_{1}\notin\delta^{*}_{\alpha[i]}(v_{2})$ and thus
$v_{2}\neq v_{3}$ and, furthermore, by Lemma 4.4, it holds that
$v_{3}\prec^{*}v_{2}$. Let $j$ be the integer such that $\alpha[j..|\alpha|]$
is the longest common suffix of $\alpha$ and $\alpha_{u}^{*}$. Note that $j<i$
must hold. Let $v_{2}^{\prime}\in Q$ be a state such that $\alpha[1..j-1]\in
S_{v_{2}^{\prime}}$ and $v_{2}\in\delta_{\alpha[j..i-1]}(v_{2}^{\prime})$ and
let $v_{3}^{\prime}\in Q$ be a state such that
$v_{3}\in\delta^{*}_{\alpha[j..i-1]}(v_{3}^{\prime})$. Since
$\alpha<\alpha^{*}_{u}$ and $\alpha[j..|\alpha|]$ is their longest common
suffix, we either have $v_{2}^{\prime}=s$ and thus
$v_{2}^{\prime}\prec^{*}v_{3}^{\prime}$ or
$\lambda(v_{2}^{\prime})<\lambda(v_{3}^{\prime})$. In the second case, it also
follows that $v_{2}^{\prime}\prec^{*}v_{3}^{\prime}$ by Axiom (1) in
Definition 4.1. On the other side, we can deduce
$v_{3}^{\prime}\prec^{*}v_{2}^{\prime}$ from $v_{3}\prec^{*}v_{2}$ using
Property 2 of Definition 4.1, a contradiction. See Figure 5.

Figure 5: Proof of that $\alpha^{*}_{u}$ is a lower bound. Thick transitions
indicate $\delta^{*}$. If we assume that there exists $\alpha\in S_{u}$ such
that $\alpha<\alpha^{*}_{u}$, we obtain (from the co-lex property of
$\prec^{*}$) the contradiction that both
$v_{2}^{\prime}\prec^{*}v_{3}^{\prime}$ and
$v_{3}^{\prime}\prec^{*}v_{2}^{\prime}$ hold.

Next, we show that $\alpha^{*}_{u}$ is the greatest lower bound, i.e., for
every lower bound $\alpha$ of $S_{u}$, it holds that
$\alpha\leq\alpha^{*}_{u}$. Assume for contradiction that there exists a lower
bound $\alpha$ of $S_{u}$ such that $\alpha>\alpha^{*}_{u}$. If
$\alpha^{*}_{u}$ is a proper suffix of $\alpha$, then $\alpha^{*}_{u}$ must be
a finite string from $S_{u}$. Thus, $\alpha$ is not a lower bound of $S_{u}$,
a contradiction. Now let us consider the case that $\alpha^{*}_{u}$ is not a
proper suffix of $\alpha$. Let $\alpha_{1}\in\Sigma^{*}$ be the longest common
suffix of $\alpha$ and $\alpha^{*}_{u}$ and let
$\alpha_{2},\alpha_{3}\in\Sigma^{\bullet}$ be the strings such that
$\alpha=\alpha_{2}\cdot\alpha_{1}$ and
$\alpha^{*}_{u}=\alpha_{3}\cdot\alpha_{1}$. Let $a$ and $b$ be the rightmost
character of $\alpha_{2}$ and $\alpha_{3}$, respectively. Since
$\alpha>\alpha^{*}_{u}$, it must hold $a>b$. However there must exist $v\in Q$
such that $u\in\delta_{b\cdot\alpha_{1}}(v)$ because $\alpha_{u}^{*}$ is
suffixed by ${b\cdot\alpha_{1}}$. And since we assume that every state is
reachable from the source state $s$, there exists a string
$\beta\in\Sigma^{*}$ such that $v\in\delta_{\beta}(s)$; consequently,
$\beta\cdot b\cdot\alpha_{1}\in S_{u}$. However, because
$\alpha=\alpha_{2}\cdot a\cdot\alpha_{1}>\beta\cdot b\cdot\alpha_{1}$,
$\alpha$ is no longer a lower bound of $S_{u}$, a contradiction.

###  C.4 Suffix doubling algorithm on pruned automata

Suppose we have computed the pruned automata
$\mathcal{A}^{\inf}=(Q^{\inf},\delta^{\inf},s^{\inf})$ for infima, and
$\mathcal{A}^{\sup}=(Q^{\sup},\delta^{\sup},s^{\sup})$ for suprema, according
to the algorithm described in Section 4.

Note that, for every $u\in Q^{\inf}$, $\alpha^{*}_{u}$ is the infimum string
of its associated state on the original input automaton. Similarly, for every
$u\in Q^{\sup}$, $\alpha^{*}_{u}$ corresponds to the supremum string. For
convenience, we denote by $\hat{\mathcal{A}}=(\hat{Q},\hat{\delta},\hat{s})$
the graph obtained by making two copies of the input DFA $\mathcal{A}$, then
computing the pruned automaton $\mathcal{A}^{\inf}$ on one of them and
$\mathcal{A}^{\sup}$ on the other one.

At every iteration $k\geq 0$, we sort the states $\hat{Q}$ according to the
length-$2^{k}$ suffixes of their associated strings ($a^{*}_{u}$’s). For the
first iteration $k=0$, states are sorted by their incoming label, and each
state $u\in\hat{Q}$ has a pointer
$\varphi(u)\in\hat{\delta}^{-1}_{\lambda(u)}(u)$ to any of its predecessor
with respect to the pruned transitions; for the source states, we define
$\varphi(s^{\inf})=s^{\inf}$ and $\varphi(s^{\sup})=s^{\sup}$. For next
iterations $k\geq 1$, we use the relative rank of the length-$2^{k-1}$
suffixes in order to sort the states by the length-$2^{k}$ suffixes of their
associated strings. This can be simply done using the fact that the
length-$2^{k}$ suffix of $a^{*}_{u}$ is the concatenation of the
length-$2^{k-1}$ suffixes of $a^{*}_{\varphi(u)}$ and $a^{*}_{u}$. Once we
know the relative rank of the length-$2^{k-1}$ suffixes of the states, we can
compute the rank for the next iteration using 2-pass radix sort in linear
time. Then for each state $u\in\hat{Q}$, we update its pointer with
$\varphi(\varphi(u))$ for further extensions of the suffixes in the next
iterations. Regarding the number of iterations we need to repeat, we can use
the following lemma.

######  Lemma C.4 ([18]).

The co-lex order of the infimum and supremum strings of a DFA
$\mathcal{A}=(Q,\delta,s)$ is the same as the co-lex order of their
length-$(2\cdot|Q|)$ suffixes.

Consequently, after $O(\log|Q|)$ iterations, we obtain the co-lex order of
$\\{\inf S_{u}:u\in Q\\}\cup\\{\sup S_{u}:u\in Q\\}$ associated with the input
DFA’s states. According to [18, Theorem 10] it characterizes the smallest-
width co-lex order $\prec_{\mathcal{A}}$ of the input DFA $\mathcal{A}$. Then
plugging the algorithm of [18, Sec. 3.3], we can obtain a minimum chain
partition of $\prec_{\mathcal{A}}$.

For the time complexity, we can compute the pruned automata each for the
infimum strings and supremum strings in $O(|\delta|\log|Q|)$ time as shown in
Section 4. Then the suffix doubling algorithm described in this section takes
$O(|Q|\log|Q|)$ time; because $O(\log|Q|)$ iterations are required, and each
iteration requires a 2-pass radix sort and updating pointers, each of which
takes $O(|Q|)$ time. Notice that after sorting these strings, we can compute a
minimum chain partition of $\prec_{\mathcal{A}}$ in linear time [18, Section
3.3] by solving an interval graph colouring problem.

######  Remark C.5.

One may wonder if our result contradicts the one in [18, Section 4]. In
particular, (i) a similar algorithm runs in $O(|Q|^{2}\log|Q|)$ time, and (ii)
the merged graph described here is no longer a deterministic and connected
automaton, i.e. there are two source states, and some states are not reachable
from a source state. The difference is that in our case the pruned automata
are already computed. In [18], each state should keep track of $O(|Q|)$
pointers (instead of only one as in our case) because there are possibly many
strings (implicitly) represented by backward walks in intermediate steps that
share the same suffixes with the infimum and supremum strings. On the other
hand, in our case, it is guaranteed that, for each state, the state referred
by its pointer is exactly on a walk representing the desired infimum (or
supremum) string. As a consequence, we can obtain $O(|Q|\log|Q|)$ time.
Regarding the determinism, the only problem caused with the suffix doubling
algorithm in [18] with an NFA is the procedure for updating the pointers. In
particular, the union of the updated pointers may take additional time in case
of NFAs. As mentioned above, it is also not the case for our algorithm because
it is sufficient to keep only one pointer on the (already) pruned automata.

##  Appendix D Special Case of String as Input

Our partition refinement algorithm (Algorithm 1) can be used to co-
lexicographically sort the prefixes of a string $S$ as follows333We can
compute the popular suffix array by co-lexicographically sorting the prefixes
of the reverse of $S$.

. We encode $S$ as a path DFA spelling $S$ and run Algorithm 1 in time
$O(|\delta|\log{|Q|})=O(|S|\log{|S|})$. The algorithm will output an ordered
partition of $Q$, where each part is a singleton set, and thus the order will
correspond to the co-lexicographic order of the prefixes of $S$. This approach
resembles the algorithm of Baier [4], which uses partition refinement on the
suffixes of $S$ to obtain the suffix array. However, Baier’s algorithm further
uses the structural properties of the DFA path (the string $S$) to devise a
particular strategy of refinement achieving a linear $O(|S|)$ running time: it
starts with the partition induced by the incoming labels (as in Algorithm 1),
but then it proceeds to refine this partition until the point where the
suffixes of each part share a well-defined prefixes (called context in the
original paper), and finally it uses this property of the current partition to
efficiently obtain the final partition (the suffix array). A further
difference to our approach is that Baier’s method is based on lexicographic
order, and thus the choice of the splitter and the split block differs from
ours.