DAIS, Ca’ Foscari University of Venice,
Italysunghwan.kim@unive.ithttps://orcid.org/0000-0002-1117-5020Funded by the
European Union (ERC, REGINDEX, 101039208). CeBiB — Centre for Biotechnology
and Bioengineering
Department of Computer Science, University of Chile,
Chilefolivares@uchile.clhttps://orcid.org/0000-0001-7881-9794Funded by Ph.D
Scholarship 21210579, ANID, Chile. DAIS, 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. Sung-Hwan
Kim, Francisco Olivares, Nicola Prezza [500]Theory of computation Pattern
matching [500]Theory of computation Formal languages and automata theory
Laurent Bulteau and Zsuzsanna Lipták 2 34th Annual Symposium on Combinatorial
Pattern Matching (CPM 2023) CPM 2023 CPM 2023 June 26–28, 2023 Marne-la-
Vallée, France 259 24

# Faster Prefix-Sorting Algorithms for Deterministic Finite Automata

Sung-Hwan Kim  Francisco Olivares  Nicola Prezza

###### Abstract

Sorting is a fundamental algorithmic pre-processing technique which often
allows to represent data more compactly and, at the same time, speeds up
search queries on it. In this paper, we focus on the well-studied problem of
sorting and indexing string sets. Since the introduction of suffix trees in
1973, dozens of suffix sorting algorithms have been described in the
literature. In 2017, these techniques were extended to sets of strings
described by means of finite automata: the theory of Wheeler graphs [Gagie et
al., TCS’17] introduced automata whose states can be _totally_ -sorted
according to the co-lexicographic (co-lex in the following) order of the
prefixes of words accepted by the automaton. More recently, in [Cotumaccio,
Prezza, SODA’21] it was shown how to extend these ideas to arbitrary automata
by means of _partial_ co-lex orders. This work showed that a co-lex order of
minimum width (thus optimizing search query times) on deterministic finite
automata (DFAs) can be computed in $O(m^{2}+n^{5/2})$ time, $m$ being the
number of transitions and $n$ the number of states of the input DFA.

In this paper, we exhibit new combinatorial properties of the minimum-width
co-lex order of DFAs and exploit them to design faster prefix sorting
algorithms. In particular, we describe two algorithms sorting arbitrary DFAs
in $O(mn)$ and $O(n^{2}\log n)$ time, respectively, and an algorithm sorting
acyclic DFAs in $O(m\log n)$ time. Within these running times, all algorithms
compute also a smallest chain partition of the partial order (required to
index the DFA). We present an experiment result to show that an optimized
implementation of the $O(n^{2}\log n)$-time algorithm exhibits a nearly-linear
behaviour on large deterministic pan-genomic graphs and is thus also of
practical interest.

###### keywords:

String Matching, Deterministic Finite Automata, Graph Indexing, Co-
lexicographical Sorting

###### category:

##  1 Introduction

In this paper, we study the problem of indexing string sets for _pattern
matching_ queries: pre-process a set $\mathcal{L}\subseteq\Sigma^{*}$ of
strings from a finite alphabet $\Sigma$ so that later we can efficiently
answer queries of the form “is a given query pattern $P\in\Sigma^{*}$
substring of some string in $\mathcal{L}$?”.

Clearly, an algorithmic solution to this problem requires the set
$\mathcal{L}$ to be representable in _finite_ space (even though $\mathcal{L}$
itself could contain an _infinite_ number of strings); in this paper, we focus
on string sets described by finite state automata, that is, on regular
languages. Our results build on a successful line of previous research based
on the following idea: after sorting all prefixes $Pref(\mathcal{L})$ of the
strings in $\mathcal{L}$ in colexicograpic (co-lex for brevity)
order111Historically, the lexicographic order of suffixes was used first;
however, with finite state automata the symmetric co-lex order of
$Pref(\mathcal{L})$ turns out to be more natural., pattern matching queries
translate to finding the strings in $Pref(\mathcal{L})$ that are suffixed by
pattern string $P$. Being $Pref(\mathcal{L})$ co-lex sorted, those strings
form a range in co-lex order; notice that, if the sorted $Pref(\mathcal{L})$
is explicitly stored, such a range can be easily found by binary search.
Recall, however, that (due to limited available working space) we work with a
particular representation of $\mathcal{L}$: a finite state automaton
$\mathcal{A}$. This requires re-formulating the pattern matching problem on
$\mathcal{A}$. It is easy to see that pattern matching queries on
$\mathcal{L}$ translate to finding paths of $\mathcal{A}$ whose labels, when
concatenated, form $P$. When using $\mathcal{A}$ to index $\mathcal{L}$, the
main question becomes therefore “how does the total co-lex order on
$Pref(\mathcal{L})$ map onto the states of $\mathcal{A}$?”. In particular
cases, such a mapping yields a total order among $\mathcal{A}$’s states. This
happens, for example, when $\mathcal{A}$ is a path (i.e. a string;
corresponding data structures include the suffix tree [22], the suffix array
[17, 12], and the FM-index [10]), a finite set of disjoint paths (eBWT [18]),
or a labeled arborescence (XBWT [9]). A total order on the states of
$\mathcal{A}$ is obtained even in particular cases where $\mathcal{A}$ may
accept an infinite language: this is the case, for example, of de Bruijn
graphs (BOSS [2]) and Wheeler graphs [21] (the latter generalize all the above
classes of totally-sortable labeled graphs).

More recently, in [6, 5] it was shown that in the general case (arbitrary
NFAs) the total co-lex order on $Pref(\mathcal{L})$ maps very naturally onto a
family of _partial co-lex orders_ among the states of $\mathcal{A}$. Such a
family contains only one order for any given DFA, while NFAs may admit
multiple admissible co-lex orders. Letting $p$ be the _width_ of a smallest-
width partial order $<_{\mathcal{A}}$, it was shown that pattern matching
queries on $\mathcal{L}$ can be solved in time $\tilde{O}(p^{2})$ per query
character222The notation $\tilde{O}$ hides factors polylogarithmic in the size
of $\mathcal{A}$.. Note that this generalizes the total order case $p=1$,
where indeed queries take $\tilde{O}(1)$ time using the aforementioned
solutions (e.g. indexes on strings and labeled trees). Building the index of
[6, 5] requires the computation of a smallest _chain partition_ for the co-lex
order $<_{\mathcal{A}}$, i.e. a minimum-size partition $C_{1},\dots,C_{p}$ of
$\mathcal{A}$’s states such that $(C_{i},<_{\mathcal{A}})$ is a total order
for each $i=1,\dots,p$ (note that the index does not require the order
$<_{\mathcal{A}}$ itself, just a chain partition). Letting $n$ and $m$ be the
number of states and transitions of $\mathcal{A}$, respectively, [6] showed
how to build such a chain partition in $O(n^{5/2}+m^{2})$ time in the case
where $\mathcal{A}$ is a deterministic finite automaton (DFA). The work [5]
presented a solution running in $\tilde{O}(m^{2})$ time w.h.p. In the general
nondeterministic (NFA) case, the problem is known to be NP-complete333Hardness
follows from hardness of the $p=1$ case [11], while membership in NP follows
from the fact that the properties defining a co-lex order can be checked in
polynomial time, given a candidate order., even though polynomial algorithms
do exist for co-lex _pre-orders_ [4] (which still allow indexing and whose
width is never larger than that of co-lex orders).

###  1.1 Our results

In this work, we focus on the problem of computing the smallest-width partial
co-lex order $<_{\mathcal{A}}$ when the input is a DFA. On DFAs,
$<_{\mathcal{A}}$ has a very intuitive definition: letting $u,v$ be states of
$\mathcal{A}$, we have $u<_{\mathcal{A}}v$ if and only if $\alpha<\beta$ for
every $\alpha\in I_{u}$ and $\beta\in I_{v}$, where $<$ denotes the co-lex
order among strings and $I_{u}$ denotes the set of strings (in fact, a regular
language) labeling all paths from the source of $\mathcal{A}$ to $u$. We first
observe that $<_{\mathcal{A}}$ is completely specified by pairs $(\inf
I_{u},\sup I_{u})$ over the co-lex sorted $Pref(\mathcal{L})$: in fact, we
prove that $u<_{\mathcal{A}}v$ holds if and only if $\sup I_{u}\leq\inf
I_{v}$. This allows finding a smallest chain decomposition of
$<_{\mathcal{A}}$ in $O(n)$ time through a solution of the _interval
partitioning problem_ , given that the co-lex ranks of strings $\inf I_{u}$
and $\sup I_{u}$ are known for each state $u$. Observing that these strings
can be easily encoded with two pruned versions of the DFA $\mathcal{A}$, this
leaves the problem of computing and sorting them — ideally, in $\tilde{O}(m)$
time. We give three different solutions for this problem, which could be of
independent interest. The first two solutions work on arbitrary DFAs and run
in time $O(mn)$ and $O(n^{2}\log n)$, respectively. The latter of these two
solutions is based on _suffix doubling_ , the technique at the core of the
first suffix array construction algorithm [17], and is close to optimal on
dense graphs. We show that an optimized implementation of this algorithm
exhibits a sub-quadratic behaviour on large deterministic pan-genomic graphs
(in fact, we experimentally observe a linearithmic running time). The third
solution works on acyclic DFAs, runs in $O(m\log n)$ time, and generalizes a
well-known algorithm for building the Burrows-Wheeler transform in an online
fashion; in our case, we process the automaton’s states in any topological
order and, for each processed state $u$, compute $\inf I_{u}$ and $\sup I_{u}$
using the results computed on the already-processed states.

##  2 Preliminaries

Notation $[i,j]$, where $i,j\in\mathbb{N}$, denotes the integer set
$\\{i,i+1,\dots,j\\}$ (if $i>j$, then $[i,j]=\emptyset$). Let $\Sigma$ be a
finite alphabet. A _finite string_ $\alpha\in\Sigma^{*}$ (or _string of finite
length_) is a finite concatenation of characters from $\Sigma$. The notation
$|\alpha|$ indicates the length of the string $\alpha$. The symbol $\epsilon$
denotes the empty string. The notation $\alpha[i]$ denotes the $i$-th
character from the beginning of $\alpha$; indices start from 1, so $\alpha[1]$
is the first character of $\alpha$. Letting $\alpha,\beta\in\Sigma^{*}$,
$\alpha\cdot\beta$ (or simply $\alpha\beta$) denotes the concatenation of
strings. The notation $\alpha[i..j]$ denotes $\alpha[i]\cdot\alpha[i+1]\cdot\
\dots\ \cdot\alpha[j]$; if $i>j$, then $\alpha[i..j]$ is the empty string
$\epsilon$. The notation $\alpha\sqsubseteq\beta$, where
$\alpha,\beta\in\Sigma^{*}$, indicates that $\alpha$ is a prefix of $\beta$,
i.e. $\alpha=\beta[1..i]$ for some $i\leq|\beta|$. An _$\omega$ -string_
$\beta\in\Sigma^{\omega}$ (or _infinite string_ / _string of infinite length_)
is an infinite numerable concatenation of characters from $\Sigma$. In this
paper, we work with _left-infinite_ $\omega$-strings, meaning that
$\beta\in\Sigma^{\omega}$ is constructed from the empty string $\epsilon$ by
prepending an infinite number of characters to it. In particular, the
operation of appending a character $a\in\Sigma$ at the end of a
$\omega$-string $\alpha\in\Sigma^{\omega}$ is well-defined and yields the
$\omega$-string $\alpha a$. The notation $\alpha^{\omega}$, where
$\alpha\in\Sigma^{*}$, denotes the concatenation of an infinite (numerable)
number of copies of string $\alpha$.

######  Definition 2.1.

A Deterministic Finite-State Automaton (DFA) is a quintuple
$\mathcal{A}=(Q,\Sigma,\delta,s,F)$ where $Q$ is the finite set of states,
$\Sigma$ is a finite alphabet, $\delta:Q\times\Sigma\rightarrow Q$ is the
transition function, $s\in Q$ is the initial state, and $F\subseteq Q$ is the
set of final states.

As is customary, we extend the transition function to words
$\alpha\in\Sigma^{*}$ as follows: for $a\in\Sigma$, $\alpha\in\Sigma^{*}$, and
$q\in Q$: $\delta(q,a\cdot\alpha)=\delta(\delta(q,a),\alpha)$ and
$\delta(q,\epsilon)=q$. By $\delta^{-1}(u)$, we denote the set of states from
which there exists a transition to $u$: i.e. $\delta^{-1}(u)=\\{v\in
Q:(\exists a\in\Sigma)(\delta(v,a)=u)\\}$.

In the rest of the paper, $n=|Q|$ denotes the number of states and
$m=|\delta|=|\\{(u,v,a)\in Q\times Q\times\Sigma:\delta(u,a)=v\\}|$ the number
of transitions of the DFA under consideration.

Following [1], we use the following notation for the set of words reaching a
given state:

######  Definition 2.2.

Let $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ be a DFA. If $q\in Q$, let $I_{q}$ be
the set of words _reaching_ $q$ from the initial state:

$I_{q}=\\{\alpha\in\Sigma^{*}:q=\delta(s,\alpha)\\};$

$I_{q}$ is also called _the regular language recognized by $q$_.

The _language $\mathcal{L}(\mathcal{A})$ recognized by $\mathcal{A}$_ is
defined as $\mathcal{L}(\mathcal{A})=\cup_{q\in F}I_{q}$.

The co-lexicographic (or co-lex) order of two strings
$\alpha,\beta\in\Sigma^{*}\cup\Sigma^{\omega}$ is defined as follows. (i)
$\epsilon<\alpha$ for every $\alpha\in\Sigma^{+}\cup\Sigma^{\omega}$, and (ii)
if $\alpha=\alpha^{\prime}a$ and $\beta=\beta^{\prime}b$ (with $a,b\in\Sigma$
and $\alpha^{\prime},\beta^{\prime}\in\Sigma^{*}\cup\Sigma^{\omega}$),
$\alpha<\beta$ holds if and only if
$(a<b)\vee(a=b\wedge\alpha^{\prime}<\beta^{\prime})$. In this paper, the
symbols $<$ and $\leq$ will be used to denote the total order between the
alphabet’s characters, the co-lexicographic order between
strings/$\omega$-strings, and the co-lex partial order among the states of an
automaton (Definition 2.3). The meaning of symbols $<$ and $\leq$ will always
be clear from the context. In all cases, the symbol $\leq$ has the following
meaning: $x\leq y$ if and only if $x<y$ or $x=y$ (i.e. $x<y$ or $x$ and $y$
are the same state, the same character, or the same string, depending on the
context).

Let $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ be a DFA. We assume that $s$ has no
incoming edges; any automaton can always be transformed into an equivalent
automaton with this property. We also assume that every state is reachable
from the source: for every $v\in Q$, there exists $\alpha\in\Sigma^{*}$ such
that $\delta(s,\alpha)=v$. Moreover, we assume _input consistency_ : for every
$u,v,v^{\prime}\in Q$ and $c,c^{\prime}\in\Sigma$, if
$\delta(v,c)=\delta(v^{\prime},c^{\prime})=u$, then $c=c^{\prime}$. We denote
with $\lambda(v)$ such a uniquely-defined character and take $\lambda(s)=\\#$
for the source $s$, where $\\#\notin\Sigma$ is such that $\\#<c$ for every
$c\in\Sigma$. Note that input consistency is equivalent to working with state-
labeled automata. Also this assumption is not too restrictive, since any
automaton can be converted into an equivalent input-consistent automaton by
just multiplying its size by a factor of $|\Sigma|$.

The following concepts can be defined more in general for NFAs (see [6]), but
for the purposes of this article it will be sufficient to introduce them just
on DFAs:

######  Definition 2.3.

Let $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ be a DFA. A _co-lex order_ on
$\mathcal{A}$ is a partial order $\leq$ on $Q$ that satisfies the following
two axioms:

  1. 1.

(Axiom 1) For every $u,v\in Q$, if $u<v$, then $\lambda(u)\leq\lambda(v)$;

  2. 2.

(Axiom 2) For every $a\in\Sigma$ and $u,v,u^{\prime},v^{\prime}\in Q$, if
$u=\delta(u^{\prime},a)$, $v=\delta(v^{\prime},a)$ and $u<v$, then
$u^{\prime}\leq v^{\prime}$.

The _width_ of a partial order is the size of its largest antichain or,
equivalently by Dilworth’s theorem [7], the size of a smallest chain partition
of the order.

######  Definition 2.4.

The _co-lex width_ of a DFA $\mathcal{A}$ is the minimum width of a co-lex
order on $\mathcal{A}$:

$\text{width}(\mathcal{A})=\min\\{\text{width}(\leq):\ \leq\text{is a co-lex
order on $\mathcal{A}$}\\}$

On DFAs, the following co-lex order is of particular interest:

######  Definition 2.5.

Let $\mathcal{A}$ be a DFA. The relation $<_{\mathcal{A}}$ over $Q$ is defined
by:

$u<_{\mathcal{A}}v\text{ if and only if }(\forall\alpha\in
I_{u})(\forall\beta\in I_{v})\leavevmode\nobreak\ (\alpha<\beta).$

In fact, by [5, Lem. 1] the following holds:

######  Lemma 2.6.

If $\mathcal{A}$ is a DFA, then $<_{\mathcal{A}}$ is a co-lex order on
$\mathcal{A}$ and $\text{width}(<_{\mathcal{A}})=\text{width}(\mathcal{A})$.
The order $<_{\mathcal{A}}$ is called the _maximum_ co-lex order on
$\mathcal{A}$.

Computing the smallest-width co-lex order is of interest because, as shown in
[5, 6], there exists a linear-space index over any DFA $\mathcal{A}$ answering
_subpath queries_ (find all the states of $\mathcal{A}$ reached by a path
labeled with a given query string $P$) in time proportional to
$\text{width}(\mathcal{A})^{2}$ time per query character. In fact, the index
is even compressed and uses
$\log(\text{width}(\mathcal{A}))+\log|\Sigma|+O(1)$ bits per transition of
$\mathcal{A}$. Building such an index requires computing a smallest-size chain
partition of $<_{\mathcal{A}}$. State-of-the art algorithms for this problem
run in time $O(m^{2}+n^{5/2})$ [6] and $\tilde{O}(m^{2})$ w.h.p. [5]. The goal
of our paper is to improve these bounds by exploiting a new characterization
for $<_{\mathcal{A}}$, introduced in the next section.

##  3 A new characterization of the maximum co-lex order of a DFA

In this section, we give a new interval-based characterization of the maximum
co-lex order $<_{\mathcal{A}}$ of a DFA. We show that this yields an
$O(n)$-space representation for $<_{\mathcal{A}}$ (observe that, in general, a
partial order requires $O(n^{2})$ space to be represented) and that, given
this representation, one can compute a smallest chain partition of
$<_{\mathcal{A}}$ in linear $O(n)$ time.

###  3.1 Infimum and supremum strings

Let $u$ be a state of a DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$. For the set
$I_{u}$ of strings recognized by $u\in Q$, consider a (possibly infinite)
string $\beta$ such that $\beta$ is a lower bound of $I_{u}$; i.e.
$\beta\leq\alpha$ for every $\alpha\in I_{u}$. Consider the co-lex largest
string $\gamma$ among such lower bounds of $I_{u}$. We call such a string the
infimum string of $u$, and denote it by $\inf I_{u}$. Similarly, we define the
supremum string $\sup I_{u}$ of $u$ as the least upper bound of $I_{u}$; see
Figure 1 for an example.

######  Definition 3.1 (Infimum and supremum strings).

Let $u\in Q$ be a state of a DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$. The
infimum string $\inf I_{u}$ and the supremum string $\sup I_{u}$ are defined
as:

$\displaystyle\inf I_{u}$
$\displaystyle=\gamma\in\Sigma^{*}\cup\Sigma^{\omega}\mbox{ s.t.
}(\forall\beta\in\Sigma^{*}\cup\Sigma^{\omega}\mbox{ s.t. }(\forall\alpha\in
I_{u}\leavevmode\nobreak\ \beta\leq\alpha)\leavevmode\nobreak\
\beta\leq\gamma)$ $\displaystyle\sup I_{u}$
$\displaystyle=\gamma\in\Sigma^{*}\cup\Sigma^{\omega}\mbox{ s.t.
}(\forall\beta\in\Sigma^{*}\cup\Sigma^{\omega}\mbox{ s.t. }(\forall\alpha\in
I_{u}\leavevmode\nobreak\ \alpha\leq\beta)\leavevmode\nobreak\
\gamma\leq\beta)$

(a)

$i$ | $\inf I_{v_{i}}$ | $\sup I_{v_{i}}$ | $i$ | $\inf I_{v_{i}}$ | $\sup I_{v_{i}}$
---|---|---|---|---|---
1 | $\epsilon$ | $\epsilon$ | 6 | b | ab
2 | a | a | 7 | bb | abb
3 | aa | abbaa | 8 | aaa | abba
4 | aab | bω | 9 | aaab | abbab
5 | aaba | bωa | 10 | aabaa | abbaba
(b)

Figure 1: Example DFA with its infimum/supremum strings.

As a warm up, we make several observations on $I_{u}$, infimum, and supremum
strings. Let $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ be a DFA. For any $u\in Q$,
the following hold:

  1. 1.

For every $\alpha\in I_{u}$, $\alpha$ is finite.

  2. 2.

For any $v(\neq u)\in Q$, $I_{u}\cap I_{v}$ is the empty set.

  3. 3.

For any finite suffix $\alpha\in\Sigma^{*}$ of $\inf I_{u}$ (or $\sup I_{u}$),
there exists $\beta\in\Sigma^{*}$ such that $\beta\alpha\in I_{u}$.

  4. 4.

$\inf I_{u}\in I_{u}$ if and only if $\inf I_{u}$ is a finite string; similar
for $\sup I_{u}$.

  5. 5.

$I_{u}$ is a singleton if and only if $\inf I_{u}=\sup I_{u}$. In such a case,
$I_{u}=\\{\inf I_{u}(=\sup I_{u})\\}$ and $\inf I_{u}=\sup I_{u}\in I_{u}$ is
a finite string.

  6. 6.

For $v(\neq u)\in Q$, if $\inf I_{u}=\inf I_{v}$ or $\inf I_{u}=\sup I_{v}$
then $\inf I_{u}$ has infinite length; similar for $\sup I_{u}$.

######  Proof 3.2.

  1. 1.

By definition of $I_{u}$.

  2. 2.

By definition of DFA, for any string $\alpha$, there exists only one state $u$
such that $\delta(s,\alpha)=u$.

  3. 3.

Let $\alpha$ be any finite suffix of $\inf I_{u}$; the $\sup I_{u}$ case is
analogous. We claim that there must exist $v\in Q$ such that
$\delta(v,\alpha)=u$. This will prove our main claim, since for any string
$\beta\in I_{v}$,
$\delta(s,\beta\cdot\alpha)=\delta(\delta(s,\beta),\alpha))=\delta(v,\alpha)=u$
by definition, so $\beta\cdot\alpha\in I_{u}$.

To prove the claim, assume by contradiction that there is no such $v\in Q$.
Let $\alpha^{\prime}\in\Sigma^{*}$ be the longest suffix of $\alpha$ such that
there exists $v^{\prime}\in Q$ such that
$\delta(v^{\prime},\alpha^{\prime})=u$. Let
$\alpha^{\prime\prime}\in\Sigma^{*}\cup\Sigma^{\omega}$ and $a\in\Sigma$ be a
string and a symbol such that $\inf I_{u}=\alpha^{\prime\prime}\cdot
a\cdot\alpha^{\prime}$. Let $b\in\Sigma$ be the smallest alphabet symbol that
is greater than $a$. Note that such $b$ must exist; if not, every $v^{\prime}$
must have an incoming transition labeled by a symbol
$a^{\prime}(\in\Sigma)\leq a$; since $a^{\prime}\neq a$ (otherwise
$\alpha^{\prime}$ would be longer), there exists a string in $I_{u}$ suffixed
by $a^{\prime}\alpha^{\prime}$ which is co-lex smaller than $\inf I_{u}$,
which causes a contradiction. Then, for every such $v^{\prime}$ and every
$v^{\prime\prime}\in Q$ and $c\in\Sigma$ such that
$\delta(v^{\prime\prime},c)=v^{\prime}$, we have $a<b\leq c$. Note that $\inf
I_{u}<b\cdot\alpha^{\prime}\leq\gamma$ for every $\gamma\in I_{u}$, so $\inf
I_{u}$ is not the greatest lower bound of $I_{u}$. This is a contradiction
with the definition of $\inf I_{u}$.

  4. 4.

$(\Rightarrow)$ By definition of $I_{u}$.

$(\Leftarrow)$ Let $\inf I_{u}$ be finite. Let us assume, by contradiction,
that $\inf I_{u}\notin I_{u}$. Let $\alpha=a\cdot\inf I_{u}$ where
$a\in\Sigma$ is the smallest symbol of the alphabet. We claim that $(\inf
I_{u}<)\alpha\leq\beta$ for every $\beta\in I_{u}$, which contradicts the
definition of $\inf I_{u}$. Consider a $\beta\in I_{u}$. Let $k$ be the length
of the longest common suffix of $\beta$ and $\inf I_{u}$. If $k<|\inf I_{u}|$,
then obviously $\alpha<\beta$ because prepending a symbol to $\inf I_{u}$ does
not affect the relative co-lex order of $\inf I_{u}$ and $\beta$. If $k=|\inf
I_{u}|$, then $\inf I_{u}$ is a suffix of $\beta$ and $|\inf
I_{u}|+1\leq|\beta|$ because $\inf I_{u}\notin I_{u}$. Therefore after
prepending the smallest symbol $a$ to $\inf I_{u}$, we still have $a\cdot\inf
I_{u}\leq\beta$.

To prove the other case for $\sup I_{u}$, let $\sup I_{u}$ be finite and let
us assume for a contradiction that $\sup I_{u}\notin I_{u}$. From (3), there
exists $\beta\in\Sigma^{*}$ such that $\beta\alpha\in I_{u}$ where
$\alpha=\sup I_{u}$; note that a string is a suffix of itself. Because
$\delta(s,\alpha)\neq u$, it holds $\beta\neq\epsilon$. However, then we have
$\sup I_{u}=\alpha<\beta\alpha\in I_{u}$, which contradicts with the
definition of $\sup I_{u}$ being an upper bound of $I_{u}$.

  5. 5.

$(\Rightarrow)$ if $I_{u}=\\{\alpha\\}$, then clearly $\inf I_{u}=\alpha$ and
$\sup I_{u}=\alpha$, so $\inf I_{u}=\sup I_{u}$. $(\Leftarrow)$ If $\inf
I_{u}=\sup I_{u}$, then they are the same _finite_ string. To see this, assume
by contradiction that $\inf I_{u}=\sup I_{u}$ have infinite length. Then, for
every $\alpha\in I_{u}$, $\inf I_{u}<\alpha<\sup I_{u}$. Since $\inf
I_{u}=\sup I_{u}$, no such $\alpha$ can exist thus $I_{u}=\emptyset$. This is
a contradiction, because it must hold $I_{u}\neq\emptyset$ by the assumption
that there always exists $\alpha\in\Sigma^{*}$ such that $\delta(s,\alpha)=u$
(and, for the source $s$, $I_{s}=\\{\epsilon\\}$). Since $\inf I_{u}(=\sup
I_{u})$ is a finite string, $\inf I_{u}\in I_{u}$ by (4). In addition, $\inf
I_{u}$ is the unique string in $I_{u}$ because for every $\alpha\in I_{u}$,
$\inf I_{u}\leq\alpha\leq\sup I_{u}$ and $\inf I_{u}=\sup I_{u}$, therefore
$\inf I_{u}=\alpha=\sup I_{u}$.

  6. 6.

Immediate from Observations (2) and (4).

To conclude the section, we prove a lemma showing that infimum and supremum
strings can always be expressed as a (possibly, infinite) concatenation of a
constant number of distinct strings whose length does not exceed the number of
states. This lemma will be useful later to bound the sorting depth of our
algorithms computing $<_{\mathcal{A}}$.

######  Lemma 3.3.

For a DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ and a state $u\in Q$, let
$\gamma\in\\{\inf I_{u},\sup I_{u}\\}$ be either the infimum or the supremum
string of $I_{u}$. Then,

  1. 1.

If $\gamma$ is finite, then $|\gamma|<|Q|$.

  2. 2.

If $\gamma$ has infinite length, then $\gamma=\beta^{\omega}\alpha$ for some
$\alpha,\beta\in\Sigma^{*}$ such that $|\alpha|+|\beta|<|Q|$.

######  Proof 3.4.

Suppose $|\gamma|\geq|Q|$. Let $\gamma=\gamma^{\prime}\gamma^{\prime\prime}$,
where $\gamma^{\prime\prime}$ is the length-$|Q|$ suffix of $\gamma$. Consider
a sequence of states $v_{1},v_{2},\cdots,v_{|Q|+1}$ such that $v_{|Q|+1}=u$
and $\delta(v_{k},\gamma^{\prime\prime}[k])=v_{k+1}$ for $1\leq k\leq|Q|$.
Note that $v_{i}\neq s$ for every $2\leq i\leq|Q|+1$ because the start state
$s$ does not have an incoming transition. Then, there are at most $|Q|-1$
distinct states among the $|Q|$ states $v_{2},\cdots,v_{|Q|+1}$ so by the
pigeonhole principle there must be $2\leq i<j\leq|Q|+1$ such that
$v_{i}=v_{j}$. Let
$\beta^{\prime}=\gamma^{\prime}\gamma^{\prime\prime}[1..i-1]$,
$\beta=\gamma^{\prime\prime}[i..j-1]$, and
$\alpha=\gamma^{\prime\prime}[j..|Q|]$. Note that $\beta\alpha$ is a proper
suffix of $\gamma^{\prime\prime}$ (_proper_ because $i\geq 2$), therefore
$|\alpha|+|\beta|=|\beta\alpha|<|\gamma^{\prime\prime}|=|Q|$. Note also that
(by definition of $\beta^{\prime},\beta$, and $\alpha$)
$\gamma=\beta^{\prime}\beta\alpha$.

Let us assume $\gamma=\inf I_{u}$; the other case $\gamma=\sup I_{u}$ is
analogous. Note that
$\gamma=\beta^{\prime}\beta\alpha\leq\beta^{\prime}\beta^{k}\alpha$ for every
$k\geq 0$. To see this, observe that if $\gamma$ is a finite string, then
$\gamma=\beta^{\prime}\beta\alpha\in I_{u}$ by Observation 1.4. Since
$\delta(s,\beta^{\prime})=v_{i}$, $\delta(v_{i},\beta)=v_{j}=v_{i}$, and
$\delta(v_{j}(=v_{i}),\alpha)=v_{|Q|+1}=u$, we have
$\beta^{\prime}\beta^{k}\alpha\in I_{u}$ for every $k\geq 0$. By definition of
$\inf I_{u}$, $\gamma=\inf I_{u}\leq\beta^{\prime}\beta^{k}\alpha$ for every
$k\geq 0$. On the other hand, if $\gamma$ has infinite length, assume for a
contradiction that there exists $k^{\prime}\geq 0$ such that
$\beta^{\prime}\beta^{k}\alpha<\beta^{\prime}\beta\alpha=\gamma$. Consider the
length-$(l+1)$ suffix $\beta^{\prime\prime}\alpha$ of
$\beta^{\prime}\beta^{k}\alpha$ where $l$ is the length of the longest common
suffix between $\beta^{\prime}\beta^{k}\alpha$ and $\gamma$; clearly, such a
$l$ is finite and $l\geq|\alpha|$ since $\alpha$ suffixes both strings. Then
by Observation 1.3, there exists $\beta^{\prime\prime\prime}\in\Sigma^{*}$
such that $\beta^{\prime\prime\prime}\beta^{\prime\prime}\alpha\in I_{u}$.
However we have
$\beta^{\prime\prime\prime}\beta^{\prime\prime}\alpha<\beta^{\prime}\beta\alpha=\gamma=\inf
I_{u}$, which contradicts the definition of $\inf I_{u}$.

By plugging $k=0$ into the inequality
$\beta^{\prime}\beta\alpha\leq\beta^{\prime}\beta^{k}\alpha$ above, we obtain
$\beta^{\prime}\beta\alpha\leq\beta^{\prime}\alpha$. Equivalently (by removing
the common suffix $\alpha$) it holds $\beta^{\prime}\beta\leq\beta^{\prime}$;
but then, we can plug again a common suffix $\beta^{k}\alpha$ for any $k\geq
0$ and obtain that
$\beta^{\prime}\beta^{k+1}\alpha\leq\beta^{\prime}\beta^{k}\alpha$ for any
$k\geq 0$. In particular, this implies that
$\beta^{\prime}\beta^{k}\alpha\leq\beta^{\prime}\beta\alpha=\gamma$ for any
$k\geq 1$.

Since in the previous two paragraphs we proved that
$\gamma\leq\beta^{\prime}\beta^{k}\alpha$ and
$\beta^{\prime}\beta^{k}\alpha\leq\gamma$ for any $k\geq 1$, we conclude that
$\gamma=\beta^{\prime}\beta^{k}\alpha$ for any $k\geq 1$, i.e. $\gamma$ must
be an $\omega$-string of the form $\gamma=\beta^{\omega}\alpha$. This proves
claim (2). Claim (1) also follows since the assumption that $\gamma$ is finite
and $|\gamma|\geq|Q|$ leads to $\gamma=\beta^{\omega}\alpha$ (a contradiction
to the finiteness of $\gamma$), hence its negation (i.e. claim 1) must hold.

###  3.2 $O(n)$-space representation of $<_{\mathcal{A}}$

Let $\mathcal{K}(\mathcal{A})=\\{\inf I_{u}:u\in Q\\}\cup\\{\sup I_{u}:u\in
Q\\}\subseteq\Sigma^{*}\cup\Sigma^{\omega}$ be the set of all infimum and
supremum strings of $\mathcal{A}$. Let $rank(\alpha)$, for
$\alpha\in\mathcal{K}(\mathcal{A})$, denote the position of $\alpha$ in the
total order $(\mathcal{K}(\mathcal{A}),<)$ (e.g. $rank(\alpha)=1$ for the co-
lex smallest string $\alpha\in\mathcal{K}(\mathcal{A})$, and so on).

Our new representation of $<_{\mathcal{A}}$ is the set of $n$ integer pairs
$\\{(rank(\inf{I_{u}}),rank(\sup{I_{u}}))\ :\ u\in
Q\\}\subseteq[1,2n]\times[1,2n]$ (note that $|\mathcal{K}(\mathcal{A})|\leq
2n$). With the next theorem, we show that this set is indeed sufficient to
reconstruct $<_{\mathcal{A}}$.

######  Theorem 3.5.

Let $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ be a DFA. Then, for any $u,v(\neq
u)\in Q$, $u<_{\mathcal{A}}v$ if and only if $\sup{I_{u}}\leq\inf{I_{v}}$.

######  Proof 3.6.

$(\Rightarrow)$ To prove $u<_{\mathcal{A}}v\Rightarrow\sup I_{u}\leq\inf
I_{v}$ for all $u,v\in Q$, assume by contradiction that there exist $u,v\in Q$
such that $u<_{\mathcal{A}}v$ and $\inf I_{v}<\sup I_{u}$. We claim that, in
this case, there must exist $\alpha\in I_{u}$, $\beta\in I_{v}$ such that
$\beta<\alpha$. By Definition 2.5, this contradicts $u<_{\mathcal{A}}v$.
First, note that there must exist $\alpha\in I_{u}$ such that $\inf
I_{v}<\alpha$, otherwise it would be $\sup I_{u}\leq\inf I_{v}$. We divide the
proof by contradiction in the two cases (i) $\inf I_{v}$ is a finite string
and (ii) $\inf I_{v}$ has infinite length.

(i) If $\inf I_{v}$ is finite, then $\inf I_{v}\in I_{v}$ by Observation 1.4.
Choosing $\beta=\inf I_{v}$, we have $\beta=\inf I_{v}(\in I_{v})<\alpha$.
This contradicts $u<_{\mathcal{A}}v$.

(ii) If $\inf I_{v}$ has infinite length, then by Lemma 3.3 we can write it as
$\inf I_{v}=\gamma_{2}^{\omega}\gamma_{1}$ for some strings
$\gamma_{1},\gamma_{2}\in\Sigma^{*}$. Note that, for every $k\geq 0$, there
exists a string $\gamma_{3}\in\Sigma^{*}$ such that
$\gamma_{3}\gamma_{2}^{k}\gamma_{1}\in I_{v}$ (by Observation 1.3 because
$\gamma_{2}^{k}\gamma_{1}$ is a suffix of $\inf I_{u}$). Choose any integer
$k^{\prime}$ such that $|\gamma_{2}^{k^{\prime}}\gamma_{1}|>|\alpha|$ (such an
integer exists since $\alpha$ is finite). Since $\inf
I_{v}=\gamma_{2}^{\omega}\gamma_{1}<\alpha$, we also have
$\gamma_{3}\gamma_{2}^{k^{\prime}}\gamma_{1}(=\beta\in I_{v})<\alpha$. Again,
this contradicts $u<_{\mathcal{A}}v$.

$(\Leftarrow)$ Let $\sup{I_{u}}\leq\inf{I_{v}}$, and choose any $\alpha\in
I_{u}$ and $\beta\in I_{v}$. We need to prove that
$\alpha<_{\mathcal{A}}\beta$. By definition of $\sup{I_{u}}$ and
$\inf{I_{v}}$, we have $\alpha\leq\sup I_{u}\leq\inf I_{v}\leq\beta$. If $\sup
I_{u}<\inf I_{v}$, then $\alpha<\beta$. If, on the other hand, $\sup
I_{u}=\inf I_{v}$ then both $\sup I_{u}$ and $\inf I_{v}$ must be infinite
strings by Observation 1.6. Since $\alpha$ and $\beta$ are both finite, it
must be the case that $\alpha\neq\sup I_{u}$ and $\beta\neq\inf I_{v}$,
therefore $\alpha<\sup I_{u}=\inf I_{v}<\beta$. Since this holds for any
$\alpha\in I_{u}$ and $\beta\in I_{v}$, by definition of $<_{\mathcal{A}}$ it
holds $\alpha<_{\mathcal{A}}\beta$.

Equivalently, Theorem 3.5 shows that $<_{\mathcal{A}}$ can be interpreted as a
set of intervals on the co-lex sorted $Pref(\mathcal{L}(\mathcal{A}))$. This
characterization of $<_{\mathcal{A}}$ will allow us to compute this order
faster than the state-of-the-art by (i) co-lex sorting the infimum and
supremum strings (Section 4), and (ii) computing a smallest chain partition
for $<_{\mathcal{A}}$ in linear time (Section 3.3).

###  3.3 Linear-time chain partitioning algorithm

In general, a partial order over $n$ elements requires $O(n^{2})$ space to be
represented. Moreover, the fastest general-purpose algorithms for computing
the smallest chain partition of a partial order run either in worst-case time
$O(n^{5/2})$ (see, for example, [6, Lem. 6.1]) or in $\tilde{O}(n^{2})$ time
w.h.p. [15]. In this section we show that given the $O(n)$-space
representation $S=\\{(rank(\inf{I_{u}}),rank(\sup{I_{u}})):u\in Q\\}$ of
$<_{\mathcal{A}}$, from which the order can be represented using intervals, we
can compute a smallest chain partition of this order in optimal $O(n)$ time.
It is known that the optimal solution of a smallest chain partition of
interval orders can be computed with a greedy method (see [13, Sec. 6.8]).
Moreover, given the sorted intervals, one can compute it in linear time [3];
for completeness here we give the details.

Based on Theorem 3.5, we now show a simple linear-time reduction from the
smallest chain partition problem (where the input order is represented as
described in Section 3.2) to the following problem:

######  Definition 3.7 (Interval partitioning problem, cf. [14, Sec. 4.1]).

Let $\\{[s_{1},f_{1}],\dots,[s_{n},f_{n}]\\}$ be a set of $n$ activities that
must be served (each) by a device. One device can handle at most one activity
at the same time. $[s_{i},f_{i}]$ is an interval, where $s_{i}$ and $f_{i}$
are the starting and finishing time of activity $i$, respectively. Determine
the minimum number of devices to serve all the activities.

Let $S=\\{a_{1}=(s_{1},f_{1}),\dots,a_{n}=(s_{n},f_{n})\\}$ be an instance of
the smallest chain partition problem for $<_{\mathcal{A}}$ (that is, a
particular instance of $<_{\mathcal{A}}$). Our reduction from this instance to
an instance of the interval partitioning problem works as follows:

  1. 1.

For each pair $a_{i}=(s_{i},f_{i})$, with $i\in[1..n]$, let
$s_{i}^{\prime}=2s_{i}+1$ and $f_{i}^{\prime}=2f_{i}$.

  2. 2.

Return the set of intervals
$S^{\prime\prime}=\\{a^{\prime\prime}_{i}\\}_{i=1}^{n}$, where
$a_{i}^{\prime\prime}=[s_{i}^{\prime\prime}=\min{(s_{i}^{\prime},f_{i}^{\prime}),f_{i}^{\prime\prime}=\max{(s_{i}^{\prime},f_{i}^{\prime})}}]$

The following Lemma shows that our reduction is correct:

######  Lemma 3.8.

Let $(s_{i},f_{i}),(s_{j},f_{j})$ be two input pairs, with $s_{i}\leq s_{j}$
without loss of generality. Let moreover
$[s^{\prime\prime}_{i},f^{\prime\prime}_{i}],[s^{\prime\prime}_{j},f^{\prime\prime}_{j}]$
be the intervals into which the two pairs get transformed by the above
reduction. Then, $f_{i}\leq s_{j}$ if and only if
$f_{i}^{\prime\prime}<s_{j}^{\prime\prime}$ (i.e.
$[s^{\prime\prime}_{i},f^{\prime\prime}_{i}]$ and
$[s^{\prime\prime}_{j},f^{\prime\prime}_{j}]$ do not overlap).

######  Proof 3.9.

We divide the proof into two cases: (Case 1) at least one of $s_{i}=f_{i}$ or
$s_{j}=f_{j}$ holds, and (Case 2) both $s_{i}<f_{i}$ and $s_{j}<f_{j}$ hold.

(Case 1) First, we show that $f_{i}\neq s_{j}$. Assume that $s_{i}=f_{i}$ (the
other case $s_{j}=f_{j}$ is analogous). Let $u$ be the state associated with
the pair $(s_{i},f_{i})$, and $v$ be the state associated with the pair
$(s_{j},f_{j})$. By Observation 1.5, $s_{i}=f_{i}$ implies that $\inf
I_{u}=\sup I_{u}$ is a finite string, and $\inf I_{u}=\sup I_{u}\in I_{u}$. If
$\inf I_{v}$ is an infinite string, then clearly $\sup I_{u}\neq\inf I_{v}$
(being $\sup I_{u}$ a finite string), i.e. $f_{i}\neq s_{j}$. If, on the other
hand, $\inf I_{v}$ is a finite string, then by Observation 1.4 we have $\inf
I_{v}\in I_{v}$; since by Observation 1.2, we have $I_{u}\cap
I_{v}=\emptyset$, also in this case we derive that $\sup I_{u}\neq\inf I_{v}$,
i.e. $f_{i}\neq s_{j}$.

Knowing $f_{i}\neq s_{j}$, we obtain that $f_{i}\leq s_{j}\Leftrightarrow
f_{i}<s_{j}\Leftrightarrow f_{i}+1\leq s_{j}$. Note that, since
$s_{j}^{\prime\prime}=2s_{j}+1>2s_{j}$ (if $s_{j}\neq f_{j}$) or
$s_{j}^{\prime\prime}=2f_{j}=2s_{j}$ (if $s_{j}=f_{j}$), we have $2s_{j}\leq
s_{j}^{\prime\prime}$. Similarly, $f_{i}^{\prime\prime}\leq 2f_{i}+1$. Hence
$2s_{i}\leq s_{i}^{\prime\prime}<f_{i}^{\prime\prime}\leq 2f_{i}+1$ (note that
$s_{i}^{\prime\prime}<f_{i}^{\prime\prime}$ always holds for any interval in
our reduction). Therefore, we have $f_{i}\leq s_{j}\Rightarrow f_{i}+1\leq
s_{j}\Rightarrow f_{i}^{\prime\prime}\leq 2f_{i}+1<2(f_{i}+1)\leq 2s_{j}\leq
s_{j}^{\prime\prime}$. For the other direction, note that $2f_{i}\leq
f_{i}^{\prime\prime}$ and $s_{j}^{\prime\prime}\leq 2s_{j}+1$. Then, using
these inequalities we obtain:
$f_{i}^{\prime\prime}<s_{j}^{\prime\prime}\Rightarrow 2f_{i}\leq
f_{i}^{\prime\prime}<s_{j}^{\prime\prime}\leq 2s_{j}+1\Rightarrow
2f_{i}<2s_{j}+1\Rightarrow f_{i}\leq s_{j}$.

(Case 2) In this case, we have $f_{i}\leq s_{j}\Rightarrow
f_{i}^{\prime\prime}=2f_{i}<2s_{j}+1=s^{\prime\prime}_{j}\Rightarrow
f_{i}^{\prime\prime}<s^{\prime\prime}_{j}$. For the other direction, note that
$f_{i}^{\prime\prime}<s^{\prime\prime}_{j}\Rightarrow
2f_{i}=f_{i}^{\prime\prime}<s^{\prime\prime}_{j}=2s_{j}+1\Rightarrow f_{i}\leq
s_{j}$.

By Lemma 3.8, we can now solve smallest chain partition problem for the
particular order $<_{\mathcal{A}}$ by reducing it to an instance of the
interval partitioning problem. Moreover, it is easy to see that the reduction
works in linear time so the linearity of our strategy relies on the cost of
the algorithm we use to solve the latter problem. We can use a greedy method
(cf. [3, 8]) to optimally solve the interval partitioning problem (namely,
using the smallest possible number of devices). The algorithm processes the
intervals in non-decreasing order of starting times, breaking ties
arbitrarily. For each interval, we choose any idle device among the available
ones. We can keep track of the list of the available devices if the starting
and finishing times of the intervals are already sorted. If all devices are
busy, we add a new device.

The above-sketched algorithm spends amortized constant time on every activity,
plus the time required to sort the input set of intervals. As said earlier,
the elements of our input pairs (i.e. before the reduction) are integer values
in the range $[1,2n]$. After the reduction, this range gets expanded to
$[2,4n+1]$. This allows us to radix-sort the intervals in $O(n)$ time. As a
result, in our scenario we can solve the interval partition problem in $O(n)$
time and, in particular, find the smallest chain partition of
$<_{\mathcal{A}}$ given its ranked-pair representation in linear time.

##  4 Co-lex sorting infimum/supremum strings

In this section, we present three algorithms to compute and sort the set
containing all infimum and supremum strings of a DFA. The first two algorithms
sort the strings in such a way that for every iteration the strings are co-lex
sorted with respect to a longer suffix; we present one simple solution that
increases the suffix length by 1 at each iteration, and one that doubles the
suffix length at each iteration. The third algorithm is a generalization of
online BWT construction and is based on the online algorithm for sorting
Wheeler DFA presented in [1, Sec. 3.2]. This algorithm works only on acyclic
DFAs but has a lower time complexity than the former two solutions.

For ease of explanation, we consider only infimum strings since the supremum
string case is analogous. Indeed, one can easily compute and sort both infimum
and supremum strings at the same time by creating two copies of the input DFA
and then running our algorithms on the union of the two DFAs, extracting the
infimum strings on one DFA and the supremum strings on the other DFA while at
the same time sorting the union of these two string sets.

###  4.1 Simple $O(mn)$-time algorithm

Let us establish some notations before describing the algorithm. For a
(possibly infinite) string $\alpha$ and an integer $k\geq 0$, we denote by
$suf_{k}(\alpha)$ the length-$k$ suffix of $\alpha$. When $|\alpha|<k$, we pad
$suf_{k}(\alpha)$ by prepending $k-|\alpha|$ copies of a special symbol
$\\#\notin\Sigma$, with $\\#<c$ for all $c\in\Sigma$; in this way, we
guarantee that $suf_{k}(\alpha)$ is always a string of length $k$ and we do
not affect the co-lex order of such suffixes (which remains the same before
and after the padding).

For state $u\in Q$ and integer $k\geq 0$, we denote by
$rank_{k}(u)\in\mathbb{N}$ the intermediate rank at iteration $k$ of $u$ in
the total order we are computing; this integer indicates the co-lex rank of
$suf_{k}(\inf I_{u})$ among $\\{suf_{k}(\inf I_{v}):v\in Q\\}$. More formally,
for $u\in Q$ and $k\geq 0$,

$\begin{array}[]{l}rank_{0}(u)=1\\\ rank_{k}(u)=|\\{suf_{k}(\inf I_{v}):v\in
Q\leavevmode\nobreak\ \land\leavevmode\nobreak\ suf_{k}(\inf I_{v})\leq
suf_{k}(\inf I_{u})\\}|\ \ \mathrm{for}\ k>0\end{array}$

Observe that two states are assigned the same rank if their corresponding
length-$k$ suffixes are equal. The algorithm works by _pruning_ transitions of
the input automaton, i.e. by removing, for every state $u$, transitions coming
from a state with a non-minimum rank among the predecessors of $u$. We denote
by $\delta_{k}$ the (pruned) transition function at iteration $k$.

The algorithm works as follows. At iteration $k\geq 0$, we perform the
following operations:

  1. 1.

Compute $rank_{k+1}$. Sort the states $\\{u\in Q\\}$ by their label
$\lambda(u)$ with ties broken by $rank_{k}(v)$ for any
$v\in\delta_{k}^{-1}(u)$ (the step below will guarantee that all predecessors
$v$ of $u$ have the same $rank_{k}(v)$).

  2. 2.

Compute $\delta_{k+1}$. For each $u\in Q$, keep only the transitions from the
min-rank predecessors: for $v\in\delta_{k}^{-1}(u)$,
$v\in\delta_{k+1}^{-1}(u)$ iff
$rank_{k+1}(v)=\min\\{rank_{k+1}(u^{\prime}):u^{\prime}\in\delta_{k}^{-1}(u)\\}$.

As far as the running time of each iteration is concerned, computing
$rank_{k+1}$ can be done in $O(n)$ time by 2-pass radix sorting (that is, by
incoming label and breaking ties by any predecessor’s rank $rank_{k}$).
Computing $\delta_{k+1}$ takes $O(|\delta_{k}|)=O(|\delta|)=O(m)$ time. Hence,
each iteration takes $O(m)$ time.

Since $\forall k\geq 0$, $\forall u\in Q$, and $\forall
v\in\delta_{k}^{-1}(u)$ we have $suf_{k+1}(\inf I_{u})=suf_{k}(\inf
I_{v})\cdot\lambda(u)$, it is easy to see that the following invariant always
holds at the beginning of iteration $k$: the infimum strings are sorted with
respect to the co-lex order of their length-$k$ suffixes. This invariant shows
that the number of iterations we have to perform is exactly the length of the
suffixes that need to be sorted to obtain the correct co-lex order of the
infimum strings. We are left to find an upper bound to this length; observe
that this is not a trivial problem, since infimum strings may have infinite
length.

Consider any two infimum strings $\alpha,\beta\in\\{\inf I_{u}:u\in Q\\}$. The
upper bound above can be computed by upper-bounding the length of the longest
common suffix between $\alpha$ and $\beta$. If any of the two strings is
finite, then by Lemma 3.3 their longest common suffix does not exceed length
$n$. If both strings are infinite, then by Lemma 3.3 we can write them as
$\alpha=\alpha_{2}^{\omega}\alpha_{1}$ and $\beta=\beta_{2}^{\omega}\beta_{1}$
and we can use the following:

######  Lemma 4.1 (cf. [18]).

For two infinite strings $\alpha=\alpha_{2}^{\omega}\alpha_{1}$ and
$\beta=\beta_{2}^{\omega}\beta_{1}$, where $\alpha_{1},\beta_{1}\in\Sigma^{*}$
and $\alpha_{2},\beta_{2}\in\Sigma^{+}$, let $\alpha^{\prime}$ and
$\beta^{\prime}$ be their suffixes of length
$k=|\alpha_{2}|+|\beta_{2}|+\max\\{|\alpha_{1}|,|\beta_{1}|\\}$. Then,
$\alpha^{\prime}<\beta^{\prime}$ if and only if $\alpha<\beta$.

######  Proof 4.2.

Without loss of generality, let us assume $|\alpha_{1}|\leq|\beta_{1}|$.
Moreover, note that without loss of generality we can also assume that
$|\alpha_{2}|+|\alpha_{1}|>|\beta_{1}|$; if this does not hold, then re-write
$\alpha_{1}\leftarrow\alpha_{2}^{k}\alpha_{1}$ for the only integer $k>0$ such
that $|\alpha_{1}|\leq|\beta_{1}|<|\alpha_{2}|+|\alpha_{1}|$ holds; after the
transformation, $\alpha$ can still be written as
$\alpha=\alpha_{2}^{\omega}\alpha_{1}$.

If $\alpha_{1}$ is not a suffix of $\beta_{1}$, then clearly the longest
common suffix between $\alpha$ and $\beta$ is at most $|\alpha_{1}|$, so the
claim holds. Let us assume therefore that $\alpha_{1}$ is a suffix of
$\beta_{1}$, i.e. $\beta_{1}=\beta_{1}^{\prime}\alpha_{1}$ for some
$\beta_{1}^{\prime}\in\Sigma^{*}$. Since by assumption
$|\alpha_{2}|+|\alpha_{1}|>|\beta_{1}|$, note that
$|\alpha_{2}|>|\beta_{1}^{\prime}|$. Similarly as above, if
$\beta_{1}^{\prime}$ does not suffix $\alpha_{2}$ (i.e.
$\beta_{1}=\beta_{1}^{\prime}\alpha_{1}$ does not suffix
$\alpha=\alpha_{2}^{\omega}\alpha_{1}$) then the longest common suffix between
$\alpha$ and $\beta$ is at most $|\beta_{1}|$ and the claim holds, so let us
assume that $\beta_{1}^{\prime}$ is a suffix of $\alpha_{2}$, i.e.
$\alpha_{2}=\alpha_{2}^{\prime}\beta_{1}^{\prime}$ for some
$\alpha_{2}^{\prime}\in\Sigma^{*}$. Since
$\alpha_{2}^{\omega}=(\alpha_{2}^{\prime}\beta_{1}^{\prime})^{\omega}=(\beta_{1}^{\prime}\alpha_{2}^{\prime})^{\omega}\beta_{1}^{\prime}$,
we conclude that comparing co-lexicographically
$\alpha=(\beta_{1}^{\prime}\alpha_{2}^{\prime})^{\omega}\beta_{1}^{\prime}\alpha_{1}$
and $\beta=\beta_{2}^{\omega}\beta_{1}^{\prime}\alpha_{1}$ reduces to
comparing $(\beta_{1}^{\prime}\alpha_{2}^{\prime})^{\omega}$ and
$\beta_{2}^{\omega}$. According to [18, Proposition 5], given any
$\gamma_{1},\gamma_{2}\in\Sigma^{+}$ it is sufficient to compare the
length-$k^{\prime}$ suffixes of $\gamma_{1}^{\omega}$ and
$\gamma_{2}^{\omega}$ to determine their co-lex order, where
$k^{\prime}=|\gamma_{1}|+|\gamma_{2}|-gcd(|\gamma_{1}|,|\gamma_{2}|)$. Our
claim easily follows since
$|\beta_{1}^{\prime}\alpha_{2}^{\prime}|=|\alpha_{2}^{\prime}\beta_{1}^{\prime}|=|\alpha_{2}|$.

######  Corollary 4.3.

The co-lex order of the infimum and supremum strings of a DFA is the same as
the co-lex order of their length-$(2n)$ suffixes.

######  Proof 4.4.

By Lemma 3.3, we can represent two infimum/supremum strings $\alpha,\beta$ as
$\alpha=\alpha_{2}^{\omega}\alpha_{1}$ and
$\beta=\beta_{2}^{\omega}\beta_{1}$. By the same lemma, each of
$|\alpha_{1}|$, $|\alpha_{2}|$, $|\beta_{1}|$ and $|\beta_{2}|$, as well as
$|\alpha_{1}|+|\alpha_{2}|$ and $|\beta_{1}|+|\beta_{2}|$, are bounded by $n$.
From Lemma 4.1, it is sufficient to compare the suffixes of length at most
$|\alpha_{2}|+|\beta_{2}|+\max\\{|\alpha_{1}|,|\beta_{1}|\\}=\max\\{(|\alpha_{1}|+|\alpha_{2}|)+|\beta_{2}|,|\alpha_{2}|+(|\beta_{1}|+|\beta_{2}|)\\})$
of $\alpha$ and $\beta$ in order to discover their co-lex order. Therefore,
$2n$ is a sufficient suffix length for sorting all the infimum strings
correctly.

Putting everything together, we conclude:

######  Lemma 4.5.

The infimum and supremum strings of an input-consistent DFA
$\mathcal{A}=(Q,\Sigma,\delta,s,F)$ can be computed and sorted in $O(mn)$
time, where $n=|Q|$ is the number of states and $m=|\delta|$ is the number of
transitions.

Equivalently, the above lemma shows that the representation of
$<_{\mathcal{A}}$ of Section 3.2 can be computed in $O(mn)$ time. Plugging the
linear-time chain partition algorithm of Section 3.3, we obtain:

######  Theorem 4.6.

Given an input-consistent DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$, we can
compute a minimum-size chain partition of $<_{\mathcal{A}}$ in $O(mn)$ time,
where $n=|Q|$ is the number of states and $m=|\delta|$ is the number of
transitions.

###  4.2 $O(n^{2}\log n)$-time suffix doubling algorithm

Instead of increasing the length of the sorted suffixes only by 1 at every
iteration, we can double it via a generalization of the prefix doubling
algorithm [17], the first suffix array construction algorithm that appeared in
the literature. Again, for simplicity we describe the algorithm just for
infimum strings; it is easy to modify it so that it computes and sorts the
union of all infimum and supremum strings.

Algorithm 1 describes our sorting procedure, which we explain in detail in the
rest of the section. At every iteration $k\geq 0$, Algorithm 1 keeps the
infimum strings sorted by their length-$2^{k}$ suffixes. Suppose we already
sorted the infimum strings with respect to their length-$2^{k}$ suffixes. To
enable the doubling procedure, we need to show how to compute the
length-$2^{k+1}$ suffix of each $\inf I_{u}$ given as input the length-$2^{k}$
suffixes of each $\inf I_{u}$, for all $u\in Q$. Given that the infimum
strings are sorted by their length-$2^{k}$ suffixes, for each $u\in Q$ we can
achieve this goal by finding a state $v\in Q$ such that

$suf_{2^{k+1}}(\inf I_{u})=suf_{2^{k}}(\inf I_{v})\cdot suf_{2^{k}}(\inf
I_{u}).$

We call such $v$ an _extender of $u$ (at distance $2^{k}$)_. More formally,
the set $P_{k}(u)$ of all extenders of $u$ at distance $2^{k}$ is defined as:

$\begin{array}[]{l}P_{0}(u)=\\{v\in\delta^{-1}(u):(\forall
v^{\prime}\in\delta^{-1}(u))(\lambda(v)\leq\lambda(v^{\prime}))\\}\\\
P_{k}(u)=\\{v\in Q:\delta(v,suf_{2^{k}}(\inf I_{u}))=u\ \wedge\
suf_{2^{k}}(\inf I_{v})\sqsubseteq suf_{2^{k+1}}(\inf I_{u})\\}\ \ for\
k>0\end{array}$

For $u\in Q$, let $rank_{2^{k}}(u)$ be the co-lex rank of $suf_{2^{k}}(\inf
I_{u})$, as defined in the previous section. Observe that, by definition, for
every $u\in Q$ and $v_{1},v_{2}\in P_{k}(u)$,
$rank_{2^{k}}(v_{1})=rank_{2^{k}}(v_{2})$.

Input: An input-consistent DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$

Output: $rank_{2^{k}}(u)$ for each $u\in Q$, with $2n\leq 2^{k}<4n$.

1 $k\leftarrow 0$;

2 for  _$u\in Q$_ do

3 $rank_{2^{k}}(u)\leftarrow\lambda(u)$;

4 $P_{k}(u)\leftarrow\\{v\in\delta^{-1}(u)\ :\ \big{(}\forall
v^{\prime}\in\delta^{-1}(u)\big{)}\big{(}\lambda(v)\leq\lambda(v^{\prime})\big{)}\\}$;

5

6while  _$2^{k} <2n$_ do

7 for  _$u\in Q$_ do

8 $a_{u}\leftarrow rank_{2^{k}}(u)$;

9 if  _$P_{k}(u)=\emptyset$_ then

10 $b_{u}\leftarrow-\infty$;

11

12 else

13 Pick any $v\in P_{k}(u)$;

14 $b_{u}\leftarrow rank_{2^{k}}(v)$;

15

16

17 Compute $rank_{2^{k+1}}(\cdot)$ by radix-sorting pairs $(a_{u},b_{u})$;

18 for  _$u\in Q$_ do

19 $\hat{P}_{k+1}(u)\leftarrow\bigcup_{v\in P_{k}(u)}P_{k}(v)$;

20 $P_{k+1}(u)\leftarrow\\{v\in\hat{P}_{k+1}(u):\big{(}\forall
v^{\prime}\in\hat{P}_{k+1}(u)\big{)}\big{(}rank_{2^{k+1}}(v)\leq
rank_{2^{k+1}}(v^{\prime})\big{)}\\}$;

21

22 $k\leftarrow k+1$;

23

return _$rank_{2^{k}}(\cdot)$_

Algorithm 1 Suffix doubling algorithm for sorting the infimum strings of a DFA

We implement a suffix doubling step as follows. Assume $P_{k}(u)$ and
$rank_{2^{k}}(u)$ have been computed for all $u\in Q$. We associate with $u$
the pair $(a_{u},b_{u})$ where $a_{u}=rank_{2^{k}}(u)$ and $b_{u}$ is chosen
as follows. If $P_{k}(u)\neq\emptyset$, $b_{u}=rank_{2^{k}}(v)$ with any $v\in
P_{k}(u)$; otherwise, $b_{u}=-\infty$ is chosen444In this case, there are no
more characters to be prepended to $\inf I_{u}$ (i.e. $|\inf I_{u}|<2^{k}$).
Since we radix-sort pairs $(a_{u},b_{u})$, this choice is consistent with the
fact that $suf_{2^{k}}(\inf I_{u})$ is left-padded with copies of symbol $\\#$
in order to reach length $2^{k}$, with $\\#<c$ for all $c\in\Sigma$ (see
definition of $suf_{2^{k}}$ in the previous section).. Finally, we compute
$rank_{2^{k+1}}(\cdot)$ by radix-sorting pairs $(a_{u},b_{u})$ in $O(n)$ time.

After computing $rank_{2^{k+1}}(\cdot)$, we need to compute $P_{k+1}(\cdot)$
for the next doubling step. For a state $u\in Q$, let
$\hat{P}_{k+1}(u)=\bigcup_{u^{\prime}\in P_{k}(u)}P_{k}(u^{\prime})$ be the
union of the extender sets of $u$’s extenders at distance $2^{k}$. Then, we
claim that we can compute $P_{k+1}(u)$ by removing all non-minimum-rank states
(i.e. non-minimum $rank_{2^{k+1}}(\cdot)$) from $\hat{P}_{k+1}(u)$. The
correctness of this procedure follows from the fact that $P_{k+1}(u)$ can also
be defined as the largest subset of $\hat{P}_{k+1}(u)$ such that, for every
$v\in P_{k+1}(u)$ and $\hat{v}\in\hat{P}_{k+1}(u)$, $rank_{2^{k+1}}(v)\leq
rank_{2^{k+1}}(\hat{v})$. To see this, first observe that
$P_{k+1}(u)\subseteq\hat{P}_{k+1}(u)$ because (i) $v\in\hat{P}_{k+1}(u)$ if
and only if $\delta(v,suf_{2^{k+1}}(\inf I_{u}))=u$, and (ii) $v\in
P_{k+1}(u)\Rightarrow\delta(v,suf_{2^{k+1}}(\inf I_{u}))=u$. Also, by the
definition of $P_{k+1}$, $suf_{2^{k+1}}(\inf I_{v})$ for $v\in P_{k+1}(u)$
must not be greater than $suf_{2^{k+1}}(\inf I_{\hat{v}})$ for any
$\hat{v}\in\hat{P}_{k+1}(u)$, which is equivalent to $rank_{2^{k+1}}(v)\leq
rank_{2^{k+1}}(\hat{v})$; otherwise, $suf_{2^{k+1}}(\inf I_{\hat{v}})\cdot
suf_{2^{k+1}}(\inf I_{u})<suf_{2^{k+1}}(\inf I_{v})\cdot suf_{2^{k+1}}(\inf
I_{u})=suf_{2^{k+2}}(\inf I_{u})$, which contradicts the definition of $\inf
I_{u}$.

Since $rank_{2^{k+1}}(v)$ has already been computed for all $v\in Q$ and can
thus be evaluated in constant time, from the above characterization of
$P_{k+1}(u)$ we obtain that the time required to compute this set is
proportional to the time we spend to compute the union
$\hat{P}_{k+1}(u)=\bigcup_{u^{\prime}\in P_{k}(u)}P_{k}(u^{\prime})$. Observe
that, if there were repeated states among the sets $P_{k}(u^{\prime})$, for
$u^{\prime}\in P_{k}(u)$, then computing such a union could take time
$O(n^{2})$ (for every $u\in Q$), leading to a cubic algorithm. Luckily, with
the next lemma we show that this is not the case: being the input automaton
deterministic, those sets are pairwise disjoint and their union can thus be
computed by just concatenating them.

######  Lemma 4.7.

Let $u\in Q$ be a state of a DFA, and let $v_{1},v_{2}(\neq v_{1})\in
P_{k}(u)$ be extenders of $u$ at distance $2^{k}$. Then $P_{k}(v_{1})\cap
P_{k}(v_{2})=\emptyset$.

######  Proof 4.8.

Let $v_{1},v_{2}(\neq v_{1})\in P_{k}(u)$ be extenders of the same state $u\in
Q$ at distance $2^{k}$. Let $\alpha_{1}=suf_{2^{k}}(\inf I_{v_{1}})$ and
$\alpha_{2}=suf_{2^{k}}(\inf I_{v_{2}})$. Assume, for a contradiction, that
there exists $v^{\prime}\in P_{k}(v_{1})\cap P_{k}(v_{2})$. By definition of
$P_{k}$, since $v^{\prime}\in P_{k}(v_{1})$, it holds
$\delta(v^{\prime},\alpha_{1})=v_{1}$. Similarly, it also holds
$\delta(v^{\prime},\alpha_{2})=v_{2}$. Since $v_{1},v_{2}\in P_{k}(u)$ are
extenders of the same state $u\in Q$ at distance $2^{k}$, both $\alpha_{1}$
and $\alpha_{2}$ are equal to the length-$2^{k}$ prefix of $suf_{2^{k+1}}(\inf
I_{u})$, therefore $\alpha_{1}=\alpha_{2}$. Consequently, we have
$v_{1}=\delta(v^{\prime},\alpha_{1})=\delta(v^{\prime},\alpha_{2})=v_{2}$,
i.e. reading a string $\alpha_{1}=\alpha_{2}$ from a state $v^{\prime}$ we
reach two distinct states $v_{1}\neq v_{2}$. This is a contradiction with the
fact that the automaton is deterministic, so the claim $P_{k}(v_{1})\cap
P_{k}(v_{2})=\emptyset$ must be true.

From Lemma 4.7, we can compute $\hat{P}_{k+1}(u)$ in time proportional to its
cardinality $|\hat{P}_{k+1}(u)|\leq n$. Since finding the minimum-rank states
can be done in linear $O(|\hat{P}_{k+1}(u)|)$ time as well, the computation of
$P_{k+1}(u)$ takes time $O(n)$ for each $u\in Q$. We conclude that each
iteration of the suffix doubling algorithm takes $O(n^{2})$ time.

It is worth noting that, since we keep track of each set $P_{k}(u)$, the
running time of an iteration is lower-bounded by the total number of extenders
therein. In the worst case, however, the total number of extenders at a single
iteration could be truly quadratic even on acyclic DFAs: see Figure 2; in this
example, there are $n=4\sigma+2$ states and
$\sigma^{2}+2\sigma+1=\Theta(n^{2})$ extenders at distance $2^{k}$ for $k=1$.

Figure 2: The DFA that has a quadratic number of extenders: the
$\sigma=\Theta(n)$ states in the rightmost column (indicated with A) have
$\sigma=\Theta(n)$ extenders each (indicated with B) at distance $2^{k}$,
where $k=1$.

Putting all together, we have the following result for the suffix doubling
algorithm described in this section.

######  Lemma 4.9.

The infimum and supremum strings of an input-consistent DFA
$\mathcal{A}=(Q,\Sigma,\delta,s,F)$ can be computed and sorted in $O(n^{2}\log
n)$ time, where $n=|Q|$ is the number of states.

Equivalently, the above lemma shows that the representation of
$<_{\mathcal{A}}$ of Section 3.2 can be computed in $O(n^{2}\log n)$ time.
Plugging the linear-time chain partition algorithm of Section 3.3, we obtain:

######  Theorem 4.10.

Given an input-consistent DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$, we can
compute a minimum-size chain partition of $<_{\mathcal{A}}$ in $O(n^{2}\log
n)$ time, where $n=|Q|$ is the number of states.

The suffix doubling algorithm in practice Although every iteration of the
suffix doubling algorithm needs to keep track of $O(n^{2})$ extenders per
iteration in the worst case, we conjecture that it is not likely to have a
quadratic number of extenders on realistic datasets. To demonstrate this, we
conducted a brief experiment using a pan-genomic graph, which is considered to
be one of the most important real-world applications of our problem. We
downloaded the Chromosome 22 sequence of the GRCh38 human reference genome and
its variation data from 1000 Genome project [16]. This variation dataset
contains a set of substitutions, insertions and deletions appearing on the
reference human genome sequence collected from 2,548 samples. Using this
dataset, we constructed a pan-genomic graph using VG [20], then converted it
into a DFA using the classical powerset construction algorithm [19]. We ran an
implementation of our suffix doubling algorithm to sort the infimum and
supremum strings and measured the number of extenders at each iteration. The
largest $\hat{P}_{k}(u)$ and $P_{k}(u)$ (extenders at distance $2^{k}$
before/after filtering non-minimum-rank states) during the procedure had
cardinality 60 and 37, respectively, which might be considered not negligible
but quite small when compared to the DFA’s size ($n$=51,904,782,
$m=$53,049,316). In addition, the sum $\sum_{u\in Q}|\hat{P}_{k}(u)|$ of the
number of extender candidates (the union of extenders before filtering non-
minimum-rank states) at any fixed distance $2^{k}$ was at most two times the
number of edges, suggesting that in practice our algorithm exhibits a
linearithmic complexity on pan-genomic graphs. C++ source code is avaliable
at: https://github.com/regindex/DFA-suffix-doubling.

###  4.3 $O(m\log n)$-time algorithm for acyclic DFAs

If the input DFA is acyclic, then we can sort the infimum strings more
efficiently using the algorithm described in [1, Sec. 3.2]. This algorithm
processes the states of any acyclic _Wheeler DFA_ $\mathcal{A}$ (that is,
$width(\mathcal{A})=1$) and their incoming edges in any topological order
$u_{1},\dots,u_{n}$ while updating $<_{\mathcal{A}}$ in an online fashion;
more precisely, as soon as step $1\leq i\leq n$ has finished, the algorithm
has computed the total order $<_{\mathcal{A}}$ of the set
$\\{u_{1},\dots,u_{i}\\}$. The basic idea is to process the states in any
topological order while maintaining a dynamic data structure that stores the
relative co-lex order of the states according to any representative of $I_{u}$
(in fact, [1] proves that on Wheeler DFAs, any string in $I_{u}$ can be chosen
as a representative of the whole $I_{u}$ to sort the automaton’s states). This
is possible because, when $u_{i}\in Q$ is being processed, the structure is
able to check if $rank(v)\leq rank(u_{j})$ for any $v\in\delta^{-1}(u_{i})$
and $j<i$, where $rank(v)$ denotes the position of $v$ in the total order
$<_{\mathcal{A}}$ of the already-processed states $u_{1},\dots,u_{i-1}$ (and,
by definition of topological order, $rank(v)$ and $rank(u_{j})$ have already
been computed in the previous steps). This information is sufficient to
compute $rank(u_{i})$ among the sorted $u_{1},\dots,u_{i}$.

In our case (arbitrary acyclic DFAs), we use the above data structure as
follows: after topologically sorting $\mathcal{A}$ (in linear time) we process
states in this order. When processing state $u_{i}$, assume that states
$u_{1},\dots,u_{i-1}$ have already been co-lex sorted according to their
strings $\inf I_{u_{1}},\dots,\inf I_{u_{i-1}}$ using the data structure of
[1, Section 3.2]. By scanning the predecessors of $u_{i}$, we find the min-
rank state $v^{*}=\arg\min_{v\in\delta^{-1}(u_{i})}rank(v)$ among them. At
this point, we insert state $u_{i}$, as well as transition (labeled edge)
$(v^{*},u_{i},\lambda(u_{i}))$, in the data structure. Note that, since only
$(v^{*},u_{i},\lambda(u_{i}))$ is inserted, the data structure of [1, Section
3.2] maintains a spanning tree of $\mathcal{A}$ rooted at the start state $s$.
By construction, it is easy to see that the unique path connecting $s$ to
$u_{i}$ in this spanning tree is labeled with string $\inf I_{u_{i}}$: the
spanning tree encodes the infimum strings. As a result, our sorting problem is
equivalent to sorting this spanning tree. It is known that a labeled tree is a
special case of Wheeler graphs (see [21]), so the computed co-lex node order
of this spanning tree is precisely the co-lex order of all infimum strings.

Since it is immediate to extend the idea to the union of all infimum and
supremum strings, taking into account the cost of each update of the data
structure [1, Sec. 3.2], we obtain:

######  Lemma 4.11.

The infimum and supremum strings of an input-consistent acyclic DFA
$\mathcal{A}=(Q,\Sigma,\delta,s,F)$ can be computed and sorted in $O(m\log n)$
time where $n=|Q|$ is the number of states and $m=|\delta|$ is the number of
transitions.

######  Proof 4.12.

First of all, the data structure [1, Sec. 3.2] supports the following two
operations in $O(\log n)$ time555In fact, the running time per operation is
$O(\log m^{\prime})$, where $m^{\prime}$ is the number of edges. However, in
our case, the number of transitions inserted into the data structure is only
$m^{\prime}=n-1$ since we insert one transition per state (except $s$).
Therefore, in our case, the time taken per operation is $O(\log n)$.: (i)
computing the relative rank of a state among those that are already processed,
and (ii) inserting a new edge (a state is inserted into the structure after
all its incoming edges have been inserted). As a result, finding
$v^{*}=\arg\min_{v\in\delta^{-1}(u_{i})}rank(v)$ takes time
$O(|\delta^{-1}(u_{i})|\cdot\log n)$. After $v^{*}$ has been found, inserting
the labeled edge $(v^{*},u_{i},\lambda(u_{i}))$, as well as state $u_{i}$,
into the structure takes time $O(\log n)$. Overall, after all states have been
processed the cost of the above operations amounts to $O(m\log n)$ time. Since
a topological order of $\mathcal{A}$ can be computed in $O(m)$ time, the total
running time is $O(m\log n)$.

Equivalently, the above lemma shows that the representation of
$<_{\mathcal{A}}$ of Section 3.2 can be computed in $O(m\log n)$ time when
$\mathcal{A}$ is acyclic. Plugging the linear-time chain partition algorithm
of Section 3.3, we obtain:

######  Theorem 4.13.

Given an input-consistent acyclic DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$, we
can compute a minimum-size chain partition of $<_{\mathcal{A}}$ in $O(m\log
n)$ time, where $n=|Q|$ is the number of states and $m=|\delta|$ is the number
of transitions.

## References

  * [1] Jarno Alanko, Giovanna D’Agostino, Alberto Policriti, and Nicola Prezza.  Regular languages meet prefix sorting.  In Proceedings of 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 911–930, 2020.  doi:10.1137/1.9781611975994.55.
  * [2] Alexander Bowe, Taku Onodera, Kunihiko Sadakane, and Tetsuo Shibuya.  Succinct de Bruijn Graphs.  In Proceedings of the 12th International Workshop on Algorithms in Bioinformatics (WABI), pages 225–235, 2012.  doi:10.1007/978-3-642-33122-0_18.
  * [3] Martin C. Carlisle and Errol L. Lloyd.  On the $k$-coloring of intervals.  Discrete Applied Mathematics, 59:225–235, 1995.  doi:10.1016/0166-218X(95)80003-M.
  * [4] Nicola Cotumaccio.  Graphs can be succinctly indexed for pattern matching in $O(|E|^{2}+|V|^{5/2})$ time.  In 2022 Data Compression Conference (DCC), pages 272–281, 2022\.  doi:10.1109/DCC52660.2022.00035.
  * [5] 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.
  * [6] Nicola Cotumaccio and Nicola Prezza.  On Indexing and Compressing Finite Automata.  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2585–2599, 2021.  doi:10.1137/1.9781611976465.153.
  * [7] Robert P. Dilworth.  A Decomposition Theorem for Partially Ordered Sets.  Annals of Mathematics, 51(1):161–166, 1950.  doi:10.2307/1969503.
  * [8] Ulrich Faigle and Willem M. Nawijn.  Note on Scheduling Intervals on-line.  Discrete Applied Mathematics, 58(1):13–17, 1995.  doi:10.1016/0166-218X(95)00112-5.
  * [9] Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, and S. Muthukrishnan.  Structuring labeled trees for optimal succinctness, and beyond.  In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 184–196, 2005.  doi:10.1109/SFCS.2005.69.
  * [10] Paolo Ferragina and Giovanni Manzini.  Opportunistic data structures with applications.  In Proceedings of the 41st Annual Symposium on Foundations of Computer Science (FOCS), pages 390–398, 2000.  doi:10.1109/SFCS.2000.892127.
  * [11] Daniel Gibney and Sharma V. Thankachan.  On the Hardness and Inapproximability of Recognizing Wheeler Graphs.  In Proceedings of the 27th Annual European Symposium on Algorithms (ESA), pages 51:1–51:16, 2019.  doi:10.4230/LIPIcs.ESA.2019.51.
  * [12] Gaston H. Gonnet, Ricardo A. Baeza-Yates, and Tim Snider.  New Indices for Text: Pat Trees and Pat Arrays.  In Information Retrieval: Data Structures & Algorithms, pages 66–82. Prentice Hall, 1992.
  * [13] Mitchel T. Keller and Wiliam T. Trotter.  Applied Combinatorics.  CreateSpace Independent Publishing Platform, 2017.  URL: https://www.appliedcombinatorics.org/book/app-comb.html.
  * [14] Jon Kleinberg and Éva Tardos.  Algorithm Design.  Pearson/Addison-Wesley, 2006.
  * [15] Shimon Kogan and Merav Parter.  Beating Matrix Multiplication for $n^{1/3}$-Directed Shortcuts.  In Prooceedings of 49th International Colloquium on Automata, Languages, and Programming (ICALP), pages 82:1–82:20, 2022.  doi:10.4230/LIPIcs.ICALP.2022.82.
  * [16] Ernesto Lowy-Gallego, Susan Fairley, Xiangqun Zheng-Bradley, Magali Ruffier, Laura Clarke, Paul Flicek, and The 1000 Genomes Project Consortium.  Variant calling on the GRCh38 assembly with the data from phase three of the 1000 Genomes Project.  Wellcome Open Research, 4(50), 2020.  doi:10.12688/wellcomeopenres.15126.2.
  * [17] 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.
  * [18] Sabrina Mantaci, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino.  An extension of the Burrows–Wheeler transform.  Theoretical Computer Science, 387(3):298–312, 2007.  doi:10.1016/j.tcs.2007.07.014.
  * [19] M. O. Rabin and D. Scott.  Finite Automata and Their Decision Problems.  IBM Journal on Research and Development, 3(2):114–125, 1959.  doi:10.1147/rd.32.0114.
  * [20] Jouni Sirén, Erik Garrison, Adam M. Novak, Benedict Paten, and Richard Durbin.  Haplotype-aware graph indexes.  Bioinformatics, 36(2):400–407, 2019.  doi:10.1093/bioinformatics/btz575.
  * [21] Giovanni Manzini Travis Gagie and Jouni Sirén.  Wheeler graphs: A framework for BWT-based data structures.  Theoretical Computer Science, 698:67–78, 2017.  doi:10.1016/j.tcs.2017.06.016.
  * [22] Peter Weiner.  Linear pattern matching algorithms.  In Proceedings of the 14th Annual Symposium on Switching and Automata Theory, pages 1–11, 1973.  doi:10.1109/SWAT.1973.13.


A common scenario with a Lagrangian linear in $\dot{\phi}$ is the light-cone
coordinate version of a theory. Such scenario is frequent throughout the given
text, therefore, few words should be given. Transformation into light-cone
coordinates does not introduce anything new, so calling such a Lagrangian
singular may seem odd and if the standard coordinates allow Hamiltonian
formulation, it is not expected that a simple coordinate transformation might
lead to the loss of the Hamiltonian formulation.

The analysis restricts here to a two-dimensional case. Nonetheless, treatment
of higher dimensional cases is of no difference. In the case of light-cone
scalar field theory, the kinetic term turns out to be

$\mathcal{L}_{(kin)}=\partial_{+}\phi(x^{+},x^{-})\partial_{-}\phi(x^{+},x^{-})\,.$
(254)

The “time” variable can be chosen at will, since there is no mathematical
difference between $x^{+}$ and $x^{-}$ coordinates as the metric does not
assign a special signature to one. This can be seen in Appendix C. The time
variable is chosen to be $x^{+}$, then the solution is identical to solving
the problem for

$\begin{split}L[\phi,\dot{\phi}](t)=&\int\differential{x}\dot{\phi}(x,t)\partial_{x}\phi(x,t)\,,\\\
F[\phi](x,t)=&\int\differential{y}\partial_{y}\phi(y,t)\delta(y-x)=-\int\differential{y}\phi(y,t)\partial_{y}\delta(y-x)\,,\\\
\Xi(x,y)=&-\partial_{x}\delta(y-x)+\partial_{y}\delta(y-x)=2\delta^{\prime}(y-x)\,.\end{split}$
(255)

Inverting $\Xi(x,y)$ gives

$\Xi^{-1}(x,y)=-\frac{1}{4}\operatorname{sgn}(x-y)\,,$ (256)

where $\operatorname{sgn}(x)$ is the sign function

$\operatorname{sgn}(x)=\begin{cases}1&x>0\,,\\\ 0&x=0\,,\\\
-1&x<0\,.\end{cases}$ (257)

Thus, Poisson brackets in the light-cone coordinates are

$\poissonbracket{\phi(x^{+},x^{-})}{\phi(x^{+},y^{-})}=-\frac{1}{4}\operatorname{sgn}(x^{-}-y^{-})\,.$
(258)

In the same manner Poisson brackets for fixed $x^{-}$ are derived to be

$\poissonbracket{\phi(x^{+},x^{-})}{\phi(y^{+},x^{-})}=-\frac{1}{4}\operatorname{sgn}(x^{+}-y^{+})\,.$
(259)

Both Poisson brackets, for equal $x^{+}$ and for equal $x^{-}$, have to be
defined because for some theories there might be a split of fields into subset
of fields constant under the change of $x^{+}$ and subset of fields constant
under the change of $x^{-}$. In such case both Poisson brackets are needed to
get the full description.

##  Appendix C Euclide vs Minkowski in two dimensions

The conformal Killing equation (50)

$\partial_{\mu}f_{\nu}+\partial_{\nu}f_{\mu}=g_{\mu\nu}\partial_{\rho}f^{\rho}\,,$

holds for both signatures of the metric, the Euclidean, customarily used in
conformal field theory222222It is so, for its intrinsic connection with
complex plane, allowing to use the results of complex analysis. and the
Minkowski. They are equivalent, but the details of this equivalence are hidden
in the complexification of the coordinates and subsequent Wick rotation, which
is discussed later here. In this paper we consider both signatures, thus the
following table is most useful.

Table 1: Notations for Minkowski and Euclidean spacetimes |  Minkowski | Euclidean
---|---|---
$\mu$ |  $t,x$ | $0,1$
$x^{\mu}$ |  $(t,x)$ | $(x^{0},x^{1})$
$g_{\mu\nu}$ |  $\eta_{\mu\nu}=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$ | $\delta_{\mu\nu}=\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$
$\varepsilon^{\mu\nu}$ |  $\varepsilon^{tx}=+1$ | $\varepsilon^{01}=+1$
Killing eq. |  $\partial_{x}f^{x}=\partial_{t}f^{t}$ | $\partial_{0}f^{1}=-\partial_{1}f^{0}$
$\partial_{x}f^{t}=\partial_{t}f^{x}$ | $\partial_{0}f^{0}=\partial_{1}f^{1}$
$\partial_{\nu}\partial^{\nu}f_{\mu}=0$ |  $\Box_{\text{M}}f_{\mu}=(\partial^{2}_{t}-\partial^{2}_{x})f_{\mu}=0$ | $\Box_{\text{E}}f_{\mu}=(\partial_{0}^{2}+\partial_{1}^{2})f_{\mu}=0$

Of course, the main difference between the two signatures is in the way the
time coordinate is dealt with. While for Minkowski, one can naturally discern
time, for the Euclidean both coordinates are equal on all footings. As a
consequence, the conformal Killing equation turns into the wave equation in
Minkowski spacetime, while it is the Cauchy-Riemann conditions for a function
to be holomorphic (or, equivalently, the Laplace equation) in the Euclidean
space.

Both the wave equation and the Laplace equation, are better solved by
introducing a new coordinates: the light-cone coordinates, for the wave
equation, and the complex plane, for the Laplace equation. After the
transformations both metrics attain the same form, and so does the conformal
Killing equation, as illustrated in the table 2 below.

Table 2: Notations for light-cone and complex plane variables |  Light-cone | Complex
---|---|---
$\mu$ |  $-,+$ | $z,\bar{z}$
$x^{\mu}$ |  $(x^{-},x^{+})$ | $(z,\bar{z})$
$x^{-}=\frac{1}{\sqrt{2}}(t-x)$ | $z=\frac{1}{\sqrt{2}}(x^{0}+ix^{1})$
$x^{+}=\frac{1}{\sqrt{2}}(t+x)$ | $\bar{z}=\frac{1}{\sqrt{2}}(x^{0}-ix^{1})$
$\partial_{\mu}$ |  $\partial_{-}=\frac{1}{\sqrt{2}}(\partial_{t}-\partial_{x})$ | $\partial\equiv\partial_{z}=\frac{1}{\sqrt{2}}(\partial_{0}-i\partial_{1})$
$\partial_{+}=\frac{1}{\sqrt{2}}(\partial_{t}+\partial_{x})$ | $\bar{\partial}\equiv\partial_{\bar{z}}=\frac{1}{\sqrt{2}}(\partial_{0}+i\partial_{1})$
$g_{\mu\nu}$ |  $\eta_{\mu\nu}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$ | $\delta_{\mu\nu}=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix}$
$\varepsilon^{\mu\nu}$ |  $\varepsilon^{-+}=+1$ | $\varepsilon^{z\bar{z}}=+1$
Killing eq. |  $\partial_{+}f^{-}=0$ | $\partial f^{\bar{z}}\equiv\partial\bar{f}=0$
$\partial_{-}f^{+}=0$ | $\bar{\partial}f^{z}\equiv\bar{\partial}f=0$
$\partial_{\nu}\partial^{\nu}f_{\mu}=0$ |  $2\partial_{+}\partial_{-}f_{\mu}=0$ | $2\partial\bar{\partial}f_{\mu}=0$

The solutions to the conformal Killing equation split into two independent
parts. The right-going, $f^{-}=f^{-}(x^{-})$, and the left-going,
$f^{+}=f^{+}(x^{+})$, waves in the light-cone reformulation and the
holomorphic, $f=f(z)$, and the antiholomorphic, $\bar{f}=\bar{f}(\bar{z})$,
complex functions in the complex space. This split hints that a theory
allowing the conformal symmetry is separable into right-going and left-going,
respectively holomorphic and antiholomorphic, subspaces.

Notice the chosen order of indices ($-,+$) for the light-cone coordinates in
2. The order of indices determines the Levi-Civita symbol
$\varepsilon^{\mu\nu}$. This choice, in particular, ensures that the
transformation matrix

$S^{\mu}{}_{\nu}\equiv\partialderivative{x^{\prime\mu}}{x^{\nu}}=\frac{1}{\sqrt{2}}\begin{pmatrix}1&-1\\\
1&1\end{pmatrix}\,,$ (260)

has a positive and unit determinat, $\det S^{\mu}{}_{\nu}=+1$. Thus, tensor
densities, e.g. $\sqrt{-g}$ and $\varepsilon^{\mu\nu}$, do not get any extra
factor under this coordinate change.

Additionaly, in order to ensure analyticity, the usual choice is to compactify
space dimension, in Minkowski space, by setting periodic boundary conditions,
[14, 22], i.e. identifying

$x\sim x+L,$ (261)

where $L$ is the periodicity length. Thus, effectively working with a
cylindrical manifold as illustrated by Figure 1. Moreover, the transformation
into the light-cone coordinates leads to coordinates $x^{+}$ and $x^{-}$ both
to be periodic, with equal periodicity $P$,

$P=L/{\sqrt{2}}.$ (262)

This allows the Fourier decomposition of $f^{\mu}$ into a discrete set of
solutions.

periodic boundary

$x^{-}=\text{const.}$$x^{+}=\text{const.}$$L$$x_{0}$$t$$x$

$x^{+}=\text{const.}$$x^{-}=\text{const.}$$x_{0}$$t$$x$

Figure 1: Cylindrical manifold

Picking a point on the cylinder $x_{0}=(x^{+}_{0},x^{-}_{0})$ and drawing the
lines $x^{+}=\text{const.}$ and $x^{-}=\text{const.}$ starting at the point
$x_{0}$ divides the cylinder into periodic rhombi-like “tiles” with one
diagonal equal to the spatial periodicity $L$. The shaded regions in Figure 1
illustrate this. This effectively compactifies the
$\mathbb{R}\times\mathbb{S}^{1}$ into $\mathbb{S}^{1}\times\mathbb{S}^{1}$. An
important remark here is that this compactification onto
$\mathbb{S}^{1}\times\mathbb{S}^{1}$ may or may not occur, depending on the
theory and its inherent existence of $x^{\pm}$ split.

Another peculiarity of light-cone coordinates is the requirement to set
boundary conditions on both lines, $x^{+}=\text{const.}$ and
$x^{-}=\text{const.}$, passing through the point $x_{0}$, to find a unique
solution. Initial value kind of a problem, where one of the $x^{\pm}$
coordinates is promoted to be “time” and the initial values of fields are
given on the line of constant “time”, is not enough to obtain the full
solution.

For the Euclidean metric the plane $\mathbb{R}^{2}$ is immediately isomorphic
to the complex plane $\mathbb{C}$, for which the natural compactification is
the Riemann sphere. Therefore, the whole plane is already in analytic domain.
One immediate consequence of dealing with Euclidean space is the loss of a
natural choice of time coordinate which plays a special role in Hamiltonian
mechanics. Here, all directions are equal, and it is a matter of convenience
to promote one coordinate to the special time-like position. Moreover,
Euclidean space gives greater freedom to construct coordinates and in two
dimensions the most convenient choice is _radial parametrization_ , that spans
the space by concentric circles around the origin and the radius of the circle
represents the “time” coordinate $x^{0}$, while the position at a circle
represents the “space” coordinate $x^{1}$. This naturally leads to periodic
space dimension. Imposing the periodicity of $x^{1}$ to be $L$, the
corresponding coordinates are
$w=e^{\frac{2\pi}{L}z}=e^{\frac{2\pi}{L}(x^{0}+ix^{1})}$,
$\bar{w}=e^{\frac{2\pi}{L}\bar{z}}=e^{\frac{2\pi}{L}(x^{0}-ix^{1})}$. These
coordinates can be viewed as a projection of a cylinder onto a plane. The
strength of this coordinate system becomes evident when we realize that
integrals over the space domain (e.g. Noether charge (8)) turn into integrals
over closed curves (circles), thus, naturally pointing to the use of residue
theorem.

It should be stressed that $z$ and $\bar{z}$ are taken as independent, rather
than complex conjugated232323Complex conjugation of $z$ is denoted here by
$z^{*}$. variables. The Euclidean space is tacitly complexified, i.e. first
the coordinates $x^{0}$ and $x^{1}$ are promoted to complex variables, which
formally means that we start from the manifold $\mathbb{C}\times\mathbb{C}$
rather than $\mathbb{R}\times\mathbb{R}$. In that way transition to the new
variables $z$ and $\bar{z}$ is just a change of variables, henceforth $z$ and
$\bar{z}$ are independent variables, each in its own $\mathbb{C}$-plane. The
physical theory is obtained after solving the problem at hand and restricting
solutions only to $z^{*}=\bar{z}$. It is this cut that turns the conformal
Killing equation $\bar{\partial}f=0$ into the holomorphic condition for $f$
(similarly, antiholomorphic condition for $\bar{f}$). Since it is expected to
do this cut in the end, it is common practice to restrict to (anti)holomorphic
solutions at the very beginning.

The cylindrical manifold and the radial parametrization are very close to each
other an it is just a matter of a proper choice of periodicity parameters, and
of the Wick rotation, to transform one situation into the other. In fact,
solving the problem in $\mathbb{C}\times\mathbb{C}$ provides result for
Minkowski spacetime if restricted to the cut where $z$ and $\bar{z}$ are pure
imaginary, i.e. $iz\in\mathbb{R}$ and $i\bar{z}\in\mathbb{R}$. In other words,
if “space” coordinate $x^{1}$ is real and “time” coordinate $x^{0}$ is
imaginary. That is formally equivalent to Wick-rotating time.

##  Appendix D All the Liouville actions used in this paper

Throughout the paper we discussed Liouville theory at eight separate
instances, each time in a different context. To discern, different subscripts
for the corresponding actions242424Except for the flat case, where the letter
used to indicate the action is non-curly $A$ instead of $\mathcal{A}$. were
used. For the sake of clarity, we collect all different definitions here, and
explain the nomenclature.

Flat spacetime, see equation (118)

$\displaystyle A_{\scriptscriptstyle{L}}[\Phi]=$
$\displaystyle\int\differential[2]{x}\quantity(\frac{1}{2}\eta^{\mu\nu}\partial_{\mu}\Phi\partial_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}).$
_Diffeomorphism_ invariant, see equation (146)
$\displaystyle\mathcal{A}_{\scriptscriptstyle{D}}[\Phi]=$
$\displaystyle\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}).$
_Non-Minimally_ coupled to metric, see equation (150)
$\displaystyle\mathcal{A}{}_{\scriptscriptstyle{NM}}[\Phi]=$
$\displaystyle\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}+\alpha
R\Phi).$ _Weyl-gauged_ , see equation (163)
$\displaystyle\mathcal{A}_{\scriptscriptstyle{W}}[\Phi,W_{\mu}]=$
$\displaystyle\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}+\frac{2}{\beta}\Phi\nabla_{\mu}W^{\mu}+\frac{2}{\beta^{2}}g^{\mu\nu}W_{\mu}W_{\nu}).$
Ricci-gauged, i.e., $W^{\mu}$ traded for the _Ricci_ scalar $R$, see equation
(169) $\displaystyle\mathcal{A}_{\scriptscriptstyle{R}}[\Phi]=$
$\displaystyle\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}+\frac{1}{\beta}\Phi
R+\frac{2}{\beta^{2}}g^{\mu\nu}W_{\mu}W_{\nu}),$

where

$2\nabla_{\mu}W^{\mu}=R.$

_Liouville_ theory commonly used, see equation (172)

$\displaystyle\mathcal{A}_{\scriptscriptstyle{L}}[\Phi]=$
$\displaystyle\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}+\frac{1}{\beta}R\Phi).$
_Polyakov_ effective action, see equation (177)
$\displaystyle\mathcal{A}_{\scriptscriptstyle{LP}}[\Phi]=$
$\displaystyle~{}\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}+\frac{1}{\beta}R\Phi)$
$\displaystyle+\frac{1}{2\beta^{2}}\int\differential[2]{x}\differential[2]{y}\sqrt{-g(x)}R(x)K(x,y)\sqrt{-g(y)}R(y),$

where

$\nabla^{2}_{x}K(x,y)=\frac{1}{\sqrt{-g(x)}}\delta^{(2)}(x-y).$

_Liouville_ action with the _Deser-Jackiw_ improvement, see equation (219)

$\displaystyle\mathcal{A}_{\scriptscriptstyle{LDJ}}[\Phi]=$
$\displaystyle\int\differential[2]{x}\sqrt{-g}\quantity(\frac{1}{2}g^{\mu\nu}\nabla_{\mu}\Phi\nabla_{\nu}\Phi-\frac{m^{2}}{\beta^{2}}e^{\beta\Phi}+\frac{1}{\beta}\Phi
R+\frac{2}{\beta^{2}}g_{\mu\nu}W^{\mu}_{\scriptscriptstyle{DJ}}W^{\nu}_{\scriptscriptstyle{DJ}}),$

where

$W^{\mu}_{\scriptscriptstyle{DJ}}=\frac{\varepsilon^{\mu\nu}}{2\sqrt{-g}}\quantity[\frac{\varepsilon^{\alpha\beta}}{\sqrt{-g}}\Gamma_{\beta\alpha\nu}+(\cosh\sigma-1)\partial_{\nu}\gamma+\partial_{\nu}r].$

##  Appendix E On Vielbein and spin-connection

The provided solution $W^{\mu}_{\scriptscriptstyle{DJ}}$ for

$2\nabla_{\mu}W^{\mu}=R\,,$

can be written explicitly without introducing the parametrization of the
metric, but rather introducing Vielbein formalism, [42, 4]. Such reformulation
of the problem in two dimensions shows explicitly that
$W^{\mu}_{\scriptscriptstyle{DJ}}$ is proportional to the spin connection,
which is demonstrated in the following.

In order to relate flat and curved spaces, one way is to introduce local
“orthonormal” bases, defined on the tangent space at each point of the curved
manifold. The transformation between the local orthonormal basis, labeled by
“flat” Latin indices $a,b,c,\ldots$, and coordinate basis, labeled by “curved”
Greek indices $\mu,\nu,\lambda,\ldots$, is realized by invertible matrices
$e^{a}_{\mu}$, called vielbein252525 The word “viel” is often replaced by
German word characterizing the dimension number, e.g. zweibein for two
dimensions, vierbein for four dimensions. Some authors prefer the names
tetrads, orthonormal basis or frame fields.  defined by

$g_{\mu\nu}=e^{a}_{\mu}\eta_{ab}e^{b}_{\nu}\,.$ (263)

Introducing the inverse $E^{\mu}_{a}$

$e^{a}_{\mu}E_{a}^{\nu}=\delta_{\mu}^{\nu}\,,\qquad
e^{a}_{\mu}E_{b}^{\mu}=\delta_{b}^{a}\,,$ (264)

the (263) can be expressed as

$E^{\mu}_{a}g_{\mu\nu}E^{\nu}_{b}=\eta_{ab}\,.$ (265)

A vector field $V$, at any given point can then be written either in the
coordinate basis with vector components $V^{\mu}$, or in local flat basis with
components $V^{a}$. The two are connected by

$V^{\mu}=E^{\mu}_{a}V^{a}\,,\qquad V^{a}=e^{a}_{\mu}V^{\mu}\,.$ (266)

While the Greek indices respond to general coordinate transformations

$V^{\prime\mu}=\partialderivative{x^{\prime\mu}}{x^{\nu}}V^{\nu}\,,$

the Latin indices only allow local Lorentz transformations,

$V^{\prime a}=\Lambda^{a}{}_{b}V^{b}\,.$

Different transformations would not preserve the metric $\eta_{ab}$ and the
local orthonormal basis.

The above can easily be generalized to tensors of any rank, [47]. Moreover,
multiindex objects are well-defined and can undergo simultaneous
transformations in both kinds of indices, e.g. vielbein transform

$e^{\prime
a}_{\mu}=\Lambda^{a}{}_{b}\partialderivative{x^{\nu}}{x^{\prime\mu}}e^{b}_{\nu}\,.$
(267)

Let us first here discuss a bit more in detail the implications of the
Vielbein formalism. This was a simple introduction of a local change of basis.
The important question is then how tensors in the local basis are parallel
transported. Or equivalently, how the covariant derivative looks like. Just
like in the coordinate basis the introduction of (Levi-Civita) connection,
$\Gamma^{\lambda}{}_{\mu\nu}$, cancels the non-tensorial contribution of the
partial derivative, another connection, $s_{\mu}{}^{a}{}_{b}$, is introduced
here to take care of Latin flat indices. This is called _spin connection_
262626 The main use of vielbein and spin connection is for dealing with
spinors, [14]. From here the name.  and the covariant derivative of a $(1,1)$
tensor $T^{a}{}_{b}$ in the local basis is then

$\nabla_{\mu}T^{a}{}_{b}\equiv\partial_{\mu}T^{a}{}_{b}+s_{\mu}{}^{a}{}_{c}T^{c}{}_{b}-s_{\mu}{}^{c}{}_{b}T^{a}{}_{c}\,.$
(268)

Again, the multiindex case is possible and both kinds of connections may
appear in the covariant derivative. Moreover, assuming the metric
compatibility, $\nabla_{\mu}g_{\alpha\beta}=0$, and consequently
$\nabla_{\mu}\eta_{ab}=0$, it follows that the spin connection is
antisymmetric in the Latin indices

$s_{\mu ab}=-s_{\mu ba}\,.$ (269)

A special example of multiindex covariant derivative is the one of vielbein,
for which the so-called full covariant derivative vanish by construction (the
“Vielbein postulate”),

$\nabla_{\mu}e^{a}_{\nu}=\partial_{\mu}e^{a}_{\nu}-{\Gamma^{\lambda}}_{\mu\nu}e^{a}_{\lambda}+{{s_{\mu}}^{a}}_{b}e^{b}_{\nu}=0\,.$
(270)

This equation can also serve as a starting point for the reformulation of the
Riemann tensor in terms of spin connection, rather than Levi-Civita
connection, which can be written as

${\Gamma^{\lambda}}_{\mu\nu}=E^{\lambda}_{a}(\partial_{\mu}e_{\nu}^{a}+{{s_{\mu}}^{a}}_{b}e^{b}_{\nu})\,.$
(271)

Thus, the Riemann tensor

${R^{\rho}}_{\sigma\mu\nu}\equiv\partial_{\mu}{\Gamma^{\rho}}_{\nu\sigma}-\partial_{\nu}{\Gamma^{\rho}}_{\mu\sigma}+{\Gamma^{\rho}}_{\mu\lambda}{\Gamma^{\lambda}}_{\nu\sigma}-{\Gamma^{\rho}}_{\nu\lambda}{\Gamma^{\lambda}}_{\mu\sigma}\,,$

after substitution of (271) becomes

$\begin{split}{R^{\lambda}}_{\rho\mu\nu}=&~{}E^{\lambda}_{a}e^{b}_{\rho}\quantity(\partial_{\mu}{{s_{\nu}}^{a}}_{b}-\partial_{\nu}{{s_{\mu}}^{a}}_{b}+{{s_{\mu}}^{a}}_{c}{{s_{\nu}}^{c}}_{b}-{{s_{\nu}}^{a}}_{c}{{s_{\mu}}^{c}}_{b})\,,\\\
=&~{}E^{\lambda}_{a}e^{b}_{\rho}{R^{a}}_{b\mu\nu}\,.\end{split}$ (272)

The EMT of a theory formulated in Vielbein formalism, obtained by variation of
an action $\mathcal{A}$, is

$T^{\mu\nu}=-\frac{1}{2e}\quantity(\functionalderivative{\mathcal{A}}{e^{a}_{\mu}}\eta^{ab}E^{\nu}_{b}+\functionalderivative{\mathcal{A}}{e^{a}_{\nu}}\eta^{ab}E^{\mu}_{b})\,,$
(273)

where

$e\equiv\det(e^{a}_{\mu})=\sqrt{-g}\,.$ (274)

#### Two dimensions

In two dimensions the Levi-Civita symbol has only two indices,
$\varepsilon^{ab}$, and any antisymmetric object has to be proportional the
Levi-Civita symbol, since in two dimensions it itself spans the whole space of
antisymmetric objects. Thus, in the case of metric compatible spin connection,
it is expected

$s_{\mu ab}\propto s_{\mu}\varepsilon_{ab}\,.$ (275)

Defining $s_{\mu}$ as

$s_{\mu}\equiv s_{\mu ab}\varepsilon^{ab}\,,$ (276)

it immediately follows

$s_{\mu ab}=-\frac{1}{2}s_{\mu}\varepsilon_{ab}\,.$ (277)

It should be stressed that although $s_{\mu}$ does not have any latin indices
it is _not_ a scalar under local Lorentz transformations.

Using the previous result together with

$\displaystyle\varepsilon^{ab}\varepsilon_{b}{}^{c}=$
$\displaystyle~{}\eta^{ac}\,,$ (278) $\displaystyle
E^{\mu}_{a}\varepsilon^{ab}E^{\nu}_{b}=$
$\displaystyle~{}\frac{\varepsilon^{\mu\nu}}{\sqrt{-g}}\,,$ (279)

leads to great simplification of the Riemann tensor (272)

${R^{\lambda}}_{\rho\mu\nu}=\frac{\varepsilon^{\lambda\sigma}}{\sqrt{-g}}g_{\sigma\rho}\frac{1}{2}\quantity(\partial_{\nu}s_{\mu}-\partial_{\mu}s_{\nu})\,.$
(280)

This, in turn, leads to a simple form of the Ricci scalar

$R=\frac{\varepsilon^{\mu\nu}}{\sqrt{-g}}\partial_{\nu}s_{\mu}\,,$ (281)

which greatly resembles the identification (170)

$2\nabla_{\mu}W^{\mu}=\frac{2}{\sqrt{-g}}\partial_{\mu}\quantity(\sqrt{-g}W^{\mu})=R\,.$
(282)

Thus, another form of the local solution to (170) is

$W^{\mu}=-\frac{\varepsilon^{\mu\nu}}{2\sqrt{-g}}s_{\nu}\,.$ (283)

Since $W^{\mu}$ is proportional to the spin connection this shows once more
that a local solution cannot be a vector.