Optimal Wheeler Language Recognition

Ruben Becker10000-0002-3495-3753
Davide Cenzato10000-0002-0098-3620
Sung-Hwan Kim10000-0002-1117-5020
Bojana Kodric10000-0001-7242-0096
Alberto Policriti20000-0001-8502-5896
Nicola Prezza10000-0003-3553-4953

R. Becker et al.

Ca' Foscari University of Venice, Italy

University of Udine, Italy

A Wheeler automaton is a finite state automaton whose states admit a total Wheeler order, reflecting the co-lexicographic order of the strings labeling source-to-node paths. A Wheeler language is a regular language admitting an accepting Wheeler automaton.
Wheeler languages admit efficient and elegant solutions to hard problems such as automata compression and regular expression matching, therefore deciding whether a regular language is Wheeler is relevant in applications requiring efficient solutions to those problems.
In this paper, we show that it is possible to
decide whether a DFA with $n$ states and $m$ transitions recognizes a Wheeler language in $O(mn)$ time. This is a significant improvement over the running time $O(n^{13} + m\log n)$ of the previous polynomial-time algorithm (Alanko et al., Information and Computation 2021).
A proof-of-concept implementation of this algorithm is available in a public repository.
We complement this upper bound with a conditional matching lower bound stating that, unless the strong exponential time hypothesis (SETH) fails, the problem cannot be solved in strongly subquadratic time.
The same problem is known to be
PSPACE-complete when the input is an NFA (D'Agostino et al., Theoretical Computer Science 2023). Together with that result, our paper essentially closes the algorithmic problem of Wheeler language recognition.

§ INTRODUCTION

Wheeler automata were introduced by Gagie et al. in [10] as a natural generalization of prefix-sorting techniques (standing at the core of the most successful string processing algorithms) to labeled graphs. Informally speaking, an automaton on alphabet $\Sigma$ is Wheeler if the co-lexicographic order of the strings labeling source-to-states paths can be “lifted” to a total order of the states (a formal definition is given in Definition <ref>).

As shown by the authors of [10], Wheeler automata can be encoded in just $O(\log|\Sigma|)$ bits per edge and they support near-optimal time pattern matching queries (i.e. finding all nodes reached by a path labeled with a given query string). These properties make them a powerful tool in fields such as bioinformatics, where one popular way to cope with the rapidly-increasing number of available fully-sequenced genomes, is to encode them in a pangenome graph: aligning short DNA sequences on pangenome graphs allows one to discover whether the sequences at hand contain variants recorded (as sub-paths) in the graph [8].

Wheeler languages — that is, regular languages recognized by Wheeler automata — were later studied by  Alanko et al. in [2]. In that paper, the authors showed that Wheeler DFAs (WDFAs) and Wheeler NFAs (WNFAs) have the same expressive power. As a matter of fact, the class of Wheeler languages proved to possess several other remarkable properties, in addition to represent the class of regular languages for which efficient indexing data structures exist. Such properties motivated them to study the following decisional problem (as well as the corresponding variant on NFAs / regular expressions):

Given a DFA $\mathcal A$, decide if  the regular language $\mathcal L(\mathcal A)$ recognized by $\mathcal A$ is Wheeler.

Alanko et al. [2]
provided the following characterization:
a language $\mathcal L$ is Wheeler if and only if, for any co-lexicographically monotone sequence of strings $\alpha_1 \prec \alpha_2 \prec \dots$ (or with reversed signs $\succ$) belonging to the prefix-closure of $\mathcal L$,
on the minimum DFA for $\mathcal L$ there
exists some $N \in \mathbb N$ and state $u$ such that
by reading
$\alpha_i$ from the source state we end up in state $u$ for all $i\geq N$. This characterization allowed them to
devise a polynomial-time algorithm solving WheelerLanguageDFA.
This result is not trivial for two main reasons: (1)
the smallest WDFA for a Wheeler language  $\mathcal L$ could be exponentially larger than the smallest DFA  for $\mathcal L$ [2],
(2) the corresponding WheelerLanguageNFA problem
(i.e., the input $\mathcal A$ is an NFA)
is PSPACE-complete [7].

Our Contributions

Despite being polynomial, the algorithm of Alanko et al. has a prohibitive complexity: $O(n^{13}+m\log n)$, where $m$ and $n$ are the number of transitions and states of the input DFA[While the authors only claim $m^{O(1)}$ time, a finer analysis yields this bound.].
In this paper, we present a much simpler parameterized (worst-case quadratic) algorithm solving WheelerLanguageDFA. The complexity of our algorithm depends on a parameter $p$ — the co-lex width of the minimum DFA $\mathcal A_{min}$ for the language [6] (Definition <ref>), which is never larger than $n$ and which measures the “distance” of $\mathcal A_{min}$ from being Wheeler; for example, if $\mathcal A_{min}$ is itself Wheeler, then $p=1$. We prove:

WheelerLanguageDFA can be solved in $O(mp + m\log n) \subseteq O(mn)$ time on any DFA $\mathcal A$ with $n$ states and $m$ edges, where $p\leq n$ is the co-lex width of the minimum automaton $\mathcal A_{min}$ equivalent to $\mathcal A$.

A proof-of-concept implementation of the algorithm behind Theorem <ref> is available at <https://github.com/regindex/Wheeler-language-recognizer>.

The intuition behind Theorem <ref> is the following. Starting from the characterization of Wheeler languages of Alanko et al. [2] based on monotone sequences, we show that $\mathcal L(\mathcal A)$ is not Wheeler if and only if the square automaton $\mathcal A_{min}^2 = \mathcal A_{min} \times \mathcal A_{min}$ contains a cycle $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots \rightarrow (u_k,v_k) \rightarrow (u_1,v_1)$ such that, for all $i=1, \dots, k$, the following two properties hold: (i) $u_i\neq v_i$ and (ii)
the co-lexicographic ranges of strings reaching $u_i$ and $v_i$ intersect.
As a result, after computing $\mathcal A_{min}$ ($O(m\log n)$ time by Hopcroft's algorithm) and directly building this “pruned” version of $\mathcal A_{min}^2$ in $O(mp + m\log n)$ time using recent techniques described in [13, 3], testing its acyclicity yields the answer.

We complement the above upper bound with a matching conditional lower bound. Our lower bound is obtained via a reduction from the following problem:

Given two sets $A$ and $B$, each containing $N$ vectors from $\{0,1\}^d$, decide whether there exist $a\in A$ and $b\in B$ such that $a^Tb = 0$.

By a classic reduction [15], for $d\in\omega(\log N)$ OV cannot be solved in time $O(N^{2-\eta} \poly(d))$ for any constant $\eta>0$
unless the strong exponential time hypothesis [12] (SETH) fails. We prove [Our lower bound states that there is no algorithm solving all instances in $O(m^{2-\eta})$ time. On sparse DFAs ($m \in \Theta(n)$) our algorithm runs in $O(mn) = O(m^2)$ time.] :

If WheelerLanguageDFA can be solved in time $O(m^{2-\eta})$ for some $\eta>0$ on a DFA with $m$ transitions on a binary alphabet, then the Orthogonal Vectors problem with $d \in \Omega(\log N)$ can be solved in time $O(N^{2-\eta} \poly(d))$.

To prove Theorem <ref>, we adapt the reduction used by Equi et al. [9] to study the complexity of the pattern matching on labeled graphs problem.
The intuition is the following.
Our new characterization of Wheeler languages states that we essentially need to find two distinct equally-labeled cycles in the minimum DFA for the language (in addition to checking some other properties on those cycles) in order to solve WheelerLanguageDFA. Given an instance of OV, we build a DFA (minimum for its language) having one (non-simple) cycle for each vector in the instance, such that the strings labeling two such cycles match if and only if the two corresponding vectors in the OV instance are orthogonal. As a result, a subquadratic-time solution of WheelerLanguageDFA on this DFA yields a subquadratic-time solution for the OV instance.

§ PRELIMINARIES

Let $\Sigma$ be a finite alphabet. A finite string $\alpha\in \Sigma^*$ 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$, with indices starting from 1.
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]$.
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$.
The co-lexicographic (or co-lex) order $\prec$ of two strings $\alpha,\beta\in \Sigma^* \cup \Sigma^\omega$ is defined as follows. (i) $\epsilon \prec \alpha$ for every $\alpha \in \Sigma^+ \cup \Sigma^\omega$, and (ii) if $\alpha = \alpha'a$ and $\beta=\beta'b$ (with $a,b\in \Sigma$ and $\alpha',\beta'\in \Sigma^* \cup \Sigma^\omega$), $\alpha \prec \beta$ holds if and only if $(a\prec b)  \vee (a=b \wedge \alpha' \prec \beta')$.
In this paper, the symbols $\prec$ and $\preceq$ will be used to denote the total order between the alphabet's characters and the co-lexicographic order between strings/$\omega$-strings.
Notation $[N]$ indicates the set of integers $\{1,2,\dots, N\}$.

DFAs, WDFAs, and Wheeler languages

In this paper, we work with deterministic finite state automata (DFAs):

A DFA $\mathcal A$ is a quintuple $(Q,\Sigma,\delta,s,F)$ where $Q$ is a finite set of states, $\Sigma$ is an alphabet set, $\delta:Q\times\Sigma\rightarrow Q$ is a transition function, $s(\in Q)$ is a source state, and $F(\subseteq Q)$ is a set of final states.

For $u,v\in Q$ and $a\in\Sigma$ such that $\delta(u,a)=v$, we define $\lambda(u,v)=a$.
We extend the domain of the transition function to words $\alpha\in \Sigma^*$ as usual, i.e., 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$.

In this work, $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 input DFA.

The notation $I_q$ indicates the set of words reaching $q$ from the initial state:

Let $\mathcal A = (Q, \Sigma, \delta, s, F) $ be a DFA.
If $q\in Q$, let $I_q$ be defined as follows:

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

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

A classic result in language theory [14] states that the minimum DFA — denoted with $\mathcal A_{min}$ — recognizing the language $\mathcal{L}(\mathcal A)$
of any DFA $\mathcal A$
is unique.
The DFA $\mathcal A_{min}$  can be computed from $\mathcal A$ in $O(m\log n)$ time with a classic partition-refinement algorithm due to Hopcroft

Wheeler automata were introduced in [10] as a generalization of prefix sorting from strings to labeled graphs. In this paper, we consider the particular case of Wheeler DFAs:

A Wheeler DFA (WDFA for brevity) [10]
$\mathcal A$ is a DFA for which there exists a total order $<\
\subseteq Q\times Q$ (called Wheeler order) satisfying the following three axioms:

(i) $s < u$ for every $u\in Q-\{s\}$.

(ii) If $u' = \delta(u,a)$, $v' = \delta(v,b)$, and $a \prec b$, then $u'<v'$.

(iii) If $u' = \delta(u,a) \neq \delta(v,a) = v'$ and $u<v$, then $u' < v'$.

The symbol $<$ will indicate both the total order of integers and the Wheeler order among the states of a Wheeler DFA.
The meaning of symbol $<$ will always be clear from the context.
Definition <ref> defines the Wheeler order in terms of local axioms. On DFAs, an equivalent global definition is the following [2]:

Let $u,v$ be two states of a DFA $\mathcal A$.
Let $u <_{\mathcal A} v$ if and only if $(\forall \alpha \in I_u) ( \forall \beta \in I_v) ~(\alpha \prec \beta)$.

$\mathcal A$ is Wheeler if and only if $<_{\mathcal A}$ is total, if and only if $<_{\mathcal A}$ is the (unique) Wheeler order of $\mathcal A$.

In fact, when a Wheeler order exists for a DFA, this order is unique [2] (as opposed to the NFA case).
The class of languages recognized by Wheeler automata is of particular interest:

A regular language $\mathcal{L}$ is said to be Wheeler if and only if there exists a Wheeler NFA $\mathcal A$ such that $\mathcal{L}=\mathcal{L}(\mathcal A)$, if and only if there exists a Wheeler DFA $\mathcal A'$ such that $\mathcal{L}=\mathcal{L}(\mathcal A')$.

The equivalence between WNFAs and WDFAs was established in [2].
In the same paper [2], the authors provided a Myhill-Nerode theorem for Wheeler languages that is crucial for our results.
Their result can be stated in terms of the minimum accepting DFA for $\mathcal L$. We first need the following definition:

Given a DFA $\mathcal A$, two distinct states $u \neq v$ of $\mathcal A$ are said to be entangled if there exists a monotone infinite sequence $\alpha_1\prec\beta_1\prec\cdots\prec\alpha_i\prec\beta_i\prec\alpha_{i+1}\prec\beta_{i+1}\prec\cdots$ (or with reversed sign $\succ$) such that $\alpha_i\in I_u$ and $\beta_i\in I_v$ for every $i\ge 1$.

The characterization of Wheeler languages of Alanko et al. [2] states that:

For a DFA $\mathcal A$, $\mathcal{L}(\mathcal A)$ is not Wheeler if and only if there exist entangled states $u$ and $v$ in its minimum DFA $\mathcal A_{min}$.

Lemma <ref> is at the core of our algorithm for recognizing Wheeler languages.

§.§ Infima and suprema strings

Lemma <ref> suggests that the Wheeler order can be defined by looking just at the lower and upper bounds of $I_u$ for each state $u\in Q$. Let us define:

For a DFA $\mathcal A=(Q,\Sigma,\delta,s,F)$, let $u\in Q$ be a state of $\mathcal A$. The infimum string $\inf I_u$ and supremum string $\sup I_u$ are the greatest lower bound and the least upper bound, respectively, of $I_u$:

\begin{align*}
\inf I_u &= \gamma\in\Sigma^*\cup\Sigma^\omega \mbox{ s.t. } (\forall \beta\in\Sigma^*\cup\Sigma^\omega \mbox{ s.t. }(\forall\alpha\in I_u~\beta\preceq\alpha)~ \beta\preceq\gamma) \\
\sup I_u &= \gamma\in\Sigma^*\cup\Sigma^\omega \mbox{ s.t. } (\forall \beta\in\Sigma^*\cup\Sigma^\omega \mbox{ s.t. } (\forall\alpha\in I_u~\alpha\preceq\beta)~ \gamma\preceq\beta)
\end{align*}

Kim et al. [13] and Conte et al. [4] use the above definition to give yet another equivalent definition of Wheeler order:

Let $u,v$ be two states of a WDFA $\mathcal A$.
Let $u < v$ if and only if $\sup{I_u}\preceq \inf{I_v}$. Then $<$ is the Wheeler order of $\mathcal A$.

Following Lemma <ref>, it is convenient to represent each state $u\in Q$ as an open interval $\mathcal{I}(u)=(\inf I_u,\sup I_u)$, i.e the subset of $\Sigma^* \cup \Sigma^\omega$ containing all strings co-lexicographically strictly larger than $\inf I_u$ and strictly smaller than $\sup I_u$.
Note that, for two states $u,v\in Q$,
if $|I_u|,|I_v|>1$ then
$\mathcal{I}(u)\cap \mathcal{I}(v)=\emptyset$ if and only if $\sup I_u\preceq \inf I_v$ or $\sup I_v\preceq \inf I_u$. If $|I_u| = 1$ (analogously for $|I_v| = 1$), then $\mathcal I(u) = \emptyset$ so $\mathcal{I}(u)\cap \mathcal{I}(v)$ is always empty.

As shown by Kim et al. [13], the set $\{\inf I_u:u\in Q\}$ can be encoded by a pruned version of $\mathcal A$: for each state $u$, we prune all but one incoming edge of $u$ such that, in the pruned automaton, the unique path entering in $u$ spells precisely string $\inf I_u$ (cycles encode infinite strings). Similarly, a second pruned version of $\mathcal A$ is used to encode $\{\sup I_u:u\in Q\}$.
The authors of [3] show that the union $\{\inf I_u:u\in Q\}\cup\{\sup I_u:u\in Q\}$ of all infima and suprema strings of a DFA can be computed and sorted efficiently:

Given a DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$, we can compute and sort co-lexicographically the set $\{\inf I_u:u\in Q\}\cup\{\sup I_u:u\in Q\}$ in $O(m\log n)$ time, where $m=|\delta|$ and $n=|Q|$.

Following [13], in the rest of the paper the intervals $\mathcal{I}(u)=(\inf I_u,\sup I_u)$ are encoded as pairs of integers: the co-lexicographic ranks of $\inf I_u$ and $\sup I_u$ in $\{\inf I_u:u\in Q\}\cup\{\sup I_u:u\in Q\}$. Using this representation, the check $\mathcal{I}(u) \cap \mathcal{I}(v) \neq \emptyset$ can be trivially performed in constant time.

We conclude this section by mentioning two useful properties of infima and suprema strings which will turn out useful later on in this work.

Let $u$ be a state of a DFA $\mathcal{A}$, and $\gamma\in\Sigma^*$ be a finite string. Then the following holds:

*  If $\inf I_u$ ($\sup I_u$) is finite, then $\inf I_u\in I_u$ ($\sup I_u\in I_u$).

*  For any finite suffix $\alpha'$ of $\inf I_u$ or $\sup I_u$, there exists $\alpha\in I_u$ suffixed by $\alpha'$.

*  $I_u$
is a singleton if and only if $\inf I_u=\sup I_u$.

*  If $\inf I_u\prec \gamma^\omega$, then there exists $\alpha\in I_u$ such that $\alpha\prec\gamma^\omega$; similarly, if $\gamma^\omega\prec\sup I_u$, then there exists $\alpha\in I_u$ such that $\gamma^\omega\prec\alpha$.

(1)-(3) See <cit.>.

(4) Assume that $\inf I_u\prec\gamma^\omega$.
If $\inf I_u$ is finite, then $\inf I_u\in I_u$ by (<ref>) and the claim follows by setting $\alpha=\inf I_u$.
Let us assume $\inf I_u$ has infinite length.
Let $\alpha'$ be the shortest suffix of $\inf I_u$ such that $\alpha'\prec\gamma^\omega$ and $\alpha'$ is not a suffix of $\gamma^\omega$; note that $\alpha'$ is finite, otherwise $\alpha'=\inf I_u=\gamma^\omega$ by definition of $\prec$, which contradicts the assumption $\inf I_u\prec\gamma^\omega$.
Then by (<ref>), there exists $\alpha\in I_u$ suffixed by $\alpha'$. By definition of $\alpha'$, prepending characters to the beginning of $\alpha'$ does not affect the relative co-lex order with respect to $\gamma^\omega$, therefore $\alpha\prec\gamma^\omega$. The case with $\gamma^\omega\prec\sup I_u$ is analogous.

§ RECOGNIZING WHEELER LANGUAGES

In this section, we present our algorithm to decide if the language accepted by a DFA $\mathcal{A}=(Q,\Sigma,\delta,s,F)$ is Wheeler.
Let $\mathcal{A}_{min}=(Q_{min},\Sigma,\delta_{min},s_{min},F_{min})$ be the minimum-size DFA accepting $\mathcal{L}(\mathcal{A})$.

The square automaton
$\mathcal A_{min}^2=\mathcal{A}_{min}\times\mathcal{A}_{min}=(Q^2_{min}=Q_{min}\times Q_{min},\Sigma,\delta',(s_{min},s_{min}),F^2_{min}=F_{min}\times F_{min})$
is the automaton whose states are pairs of states of  $\mathcal{A}_{min}$ and whose transition function is defined as
$\delta'((u,v),a)=(\delta_{min}(u,a),\delta_{min}(v,a))$ for $u,v\in Q_{min}$ and $a\in\Sigma$.

We are ready to prove our new characterization of Wheeler languages.
The characterization states that $\mathcal A_{min}^2$ can be used to detect repeated cycles in $\mathcal A_{min}$, and that we can use this fact to check if $\mathcal L(\mathcal A_{min}) = \mathcal L(\mathcal A)$ is Wheeler:

For a DFA $\mathcal{A}$, $\mathcal{L}(\mathcal{A})$ is not Wheeler if and only if $\mathcal A_{min}^2$ contains a cycle $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots \rightarrow (u_k,v_k) \rightarrow (u_1,v_1)$ such that, for $1\le \forall i \le k$, the following hold: (i) $u_i\neq v_i$ and (ii) $\mathcal{I}(u_i)\cap\mathcal{I}(v_i)\ne\emptyset$.

Assume that $\mathcal{A}^2_{min}$ contains such a cycle $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots \rightarrow (u_k,v_k) \rightarrow (u_1,v_1)$ where $k$ is the cycle length.
Then, by definition of $\mathcal{A}^2_{min}$ there exist cycles $u_1 \rightarrow u_2 \rightarrow \dots \rightarrow u_k \rightarrow u_1$ and $v_1 \rightarrow v_2 \rightarrow \dots \rightarrow v_k \rightarrow v_1$ in $\mathcal{A}_{min}$, both of which are labeled by the same string  $\gamma = \lambda(u_1,u_2)\cdots\lambda(u_{k-1},u_{k}) \lambda(u_{k},u_{1}) = \lambda(v_1,v_2)\cdots\lambda(v_{k-1},v_{k}) \lambda(v_{k},v_{1})$ of length $k$.

Let $\gamma_1=\max\{\inf I_{u_1},\inf I_{v_1}\}$ and $\gamma_2=\min\{\sup I_{u_1},\sup I_{v_1}\}$.
First, we claim that $\gamma_1\prec\gamma_2$.
To see this, without loss of generality, let us assume that $\inf I_{u_1}\preceq \inf I_{v_1}$.
First, observe that $|I_{u_1}|,|I_{v_1}|>1$ because $u$ and $v$ are on two cycles (hence $I_{u_1}$ and $I_{v_1}$ contain an infinite number of strings), so by Lemma <ref>.<ref> both $\inf I_{u_1}\prec \sup I_{u_1}$ and $\inf I_{v_1}\prec \sup I_{v_1}$ hold. Since $\mathcal{I}(u_1)\cap\mathcal{I}(v_1)\ne\emptyset$, it also holds that $\inf I_{v_1} \prec \sup I_{u_1}$.
Then, $\inf I_{u_1} \preceq \inf I_{v_1} \prec \sup I_{u_1},\sup I_{v_1}$. Therefore $\gamma_1=\inf I_{v_1}\prec \min\{\sup I_{u_1},\sup I_{v_1}\} = \gamma_2$.

As a consequence, we can see that at least one of the following must hold: (i) $\gamma_1\prec\gamma^\omega$ and (ii) $\gamma^\omega\prec\gamma_2$; note that the complement of the case (i) is $\gamma^\omega\preceq \gamma_1$, which implies $\gamma^\omega\prec\gamma_2$ because $(\gamma^\omega\preceq)\gamma_1\prec\gamma_2$.
Therefore, by Lemma <ref>.<ref>, there must exist $\alpha\in I_{u_1}$ and $\beta \in I_{v_1}$ such that either $\alpha,\beta\prec \gamma^\omega$ or $\gamma^\omega\prec\alpha,\beta$ hold.

Note that it cannot be $\alpha=\beta$ because $\mathcal{A}_{min}$ is a DFA.
Without loss of generality, let us assume $\alpha\prec\beta$.
We consider the case $\alpha\prec\beta\prec\gamma^\omega$; the other case ($\gamma^\omega\prec \alpha\prec\beta$) is symmetric.
Let $l$ be any integer such that $\max\{|\alpha|,|\beta|\}< l\cdot|\gamma|$.
Then we can see that, for every $d\ge 0$, the following three properties hold: (i) $\alpha(\gamma^{l})^d\prec\beta(\gamma^{l})^d\prec\alpha(\gamma^{l})^{d+1}\prec\beta(\gamma^{l})^{d+1}$, (ii) $\alpha(\gamma^{l})^d\in I_{u_1}$ (because $\alpha\in I_{u_1}$ and $\gamma$ labels a cycle from $u_1$, so $\delta_{min}(u_1,\gamma^k)=u_1$ for any integer $k\geq 0$) and, similarly, (iii) $\beta(\gamma^{l})^d\in I_{v_1}$.
Properties (i-iii) imply that
there is an infinite monotone nondecreasing sequence of strings alternating between $I_{u_1}$ and $I_{v_1}$, i.e.,
$u_1$ and $v_1$ are entangled (Definition <ref>) and, by Lemma <ref>, $\mathcal L(\mathcal A_{min}) = \mathcal L(\mathcal A)$ is not Wheeler.

Assume that $\mathcal L(\mathcal A_{min}) = \mathcal L(\mathcal A)$ is not Wheeler. By Lemma <ref>,  there exist entangled states $u_0 \neq v_0$ in $\mathcal{A}_{min}$ (in particular, $\mathcal I(u_0)\cap \mathcal I(v_0) \neq \emptyset$).
Without loss of generality, we can assume that there is an infinite nondecreasing sequence $S_0=\alpha_1\prec\beta_1\prec\alpha_2\prec\beta_2\prec\cdots$ such that, for every $i\ge 1$, $\alpha_i\in I_{u_0}$ and $\beta_i\in I_{v_0}$ (the other case with the reversed sign is analogous).

Observe that, since the alphabet is finite, $S_0$  must ultimately (i.e., from a sufficiently large index $i$) contain strings $\alpha_i, \beta_i$ sharing the last character. We can therefore assume without loss of generality that all strings in  $S_0$ end with the same character $a$.
Then, there exist $u_1,v_1$ such that $\delta_{min}(u_1,a)=u_0$ and $\delta_{min}(v_1,a)=v_0$.
Note that, by the determinism of $\mathcal A_{min}$, it must be $u_1 \neq v_1$.
Moreover, we can choose two entangled such $u_1,v_1$.
To see this,
let $u_1^1,\dots, u_1^s$ and $v_1^1,\dots, v_1^r$ be the $s$ and $r$ $a$-predecessors of $u_0$ and $v_0$, respectively, i.e., $\delta_{min}(u_1^i,a)=u_0$ and $\delta_{min}(v_1^j,a)=v_0$ for all $1\leq i \leq s$ and $1\leq j \leq r$.
Assume for the purpose of contradiction that $u_1^i$ and $v_1^j$ are not entangled for all pairs $u_1^i, v_1^j$. Then, by definition of entanglement
any monotone sequence
$\mu_1 \prec \mu_2 \prec \dots \in I_{u_1^i} \cup I_{v_1^j}$ ultimately ends up in just one of the two sets: there exists $N\in \mathbb N$ such that either $\mu_N, \mu_{N+1}, \dots \in I_{u_1^i}$ or $\mu_N, \mu_{N+1}, \dots \in I_{v_1^j}$.
Since this is true for any pair $u_1^i$, $v_1^j$, any monotone sequence $\mu_1 \prec \mu_2 \prec \dots \in
\bigcup_{i=1}^s I_{u_1^i} \cup \bigcup_{j=1}^r I_{v_1^i}$ ultimately ends up in either (i) $\bigcup_{i=1}^s I_{u_1^i}$ or (ii) $\bigcup_{j=1}^r I_{v_1^i}$. But then, this implies that sequence $S_0$ cannot exist: any monotone sequence $\mu_1a \prec \mu_2a \prec \dots \in I_{u_0} \cup I_{v_0}$ ultimately ends up in either (i) $I_{u_0}$  or  (ii) $I_{v_0}$.

Summing up, we found
$u_1\neq v_1$ such that $\delta_{min}(u_1,a)=u_0$, $\delta_{min}(v_1,a)=v_0$, and
$u_1, v_1$ are
entangled (in particular, $\mathcal I(u_1)\cap \mathcal I(v_1) \neq \emptyset$).
We iterate this process for $k = |Q_{min}|^2$ times; this yields two paths $u_k \rightarrow u_{k-1} \rightarrow \dots \rightarrow u_0$ and $v_k \rightarrow v_{k-1} \rightarrow \dots \rightarrow v_0$ labeled with the same string of length $k$, with $u_i\neq v_i$ and $\mathcal I(u_i)\cap \mathcal I(v_i) \neq \emptyset$ for all $0\leq i \leq k$. But then, since we chose $k = |Q_{min}|^2$, by the pigeonhole principle there must exist two indices $j \leq i$ such that $(u_i,v_i) = (u_j,v_j)$.
In particular, there exists $k'\leq k$ such that $u_i \rightarrow u_{i-1} \rightarrow \dots \rightarrow u_{i-k'+1} \rightarrow u_i$ and $v_i \rightarrow v_{i-1} \rightarrow \dots \rightarrow v_{i-k'+1} \rightarrow v_i$ are two cycles of the same length $k'$, labeled with the same string, such that $u_t\neq v_t$ and $\mathcal I(u_t)\cap \mathcal I(v_t) \neq \emptyset$ for all indices $i-k'+1 \leq t \leq i$. This yields our main claim.

§ THE ALGORITHM

Theorem <ref> immediately gives a quadratic algorithm for WheelerLanguageDFA:

* Compute $\mathcal{A}_{min}=(Q_{min},\Sigma,\delta_{min},s_{min},F_{min})$ by Hopcroft's algorithm [11].

* On $\mathcal A_{min}$, compute intervals $\mathcal I(u)$ for each $u\in Q_{min}$, using [
In Appendix <ref> we discuss more in detail how to apply <cit.> on $\mathcal A_{min}$.] <cit.>.

* Compute $\mathcal A_{min}^2$.

* Remove from $\mathcal A_{min}^2$ all states $(u,v)$
(and incident transitions) such that either $u=v$ or $\mathcal I(u) \cap \mathcal I(v) = \emptyset$. Let $\mathcal {\hat A}_{min}^2$ be the resulting pruned automaton.

* Test acyclicity of $\mathcal {\hat A}_{min}^2$.
If $\mathcal {\hat A}_{min}^2$ is acyclic,
return . Otherwise, return .

Since, by its definition,  $\mathcal A_{min}$ cannot be larger than  $\mathcal A$, in the rest of the paper we will for simplicity assume that $\mathcal A_{min}$ has $n$ nodes and $m$ transitions. Steps (1) and (2) run in $O(m\log n)$ time.
Note that, for each transition $\delta_{min}(u,a)=u'$ and for each node $v\neq u$, by the determinism of $\mathcal A_{min}$ there exists at most one transition $\delta_{min}(v,a)=v'$ labeled with $a$ and originating in $v$; such a pair of transitions define one transition of $\mathcal A_{min}^2$. It follows that the number of transitions (thus the size) of $\mathcal A_{min}^2$ is $O(mn)$, therefore steps (3-5) run in $O(mn)$ time (acyclicity can be tested in $O(|\mathcal A_{min}^2|)$ time using, for example, Kahn's topological sorting algorithm). Overall, the algorithm runs in $O(mn)$ time.

§.§ A parameterized algorithm

Our algorithm can be optimized by observing that we can directly build $\mathcal {\hat A}_{min}^2$, and that this automaton could be much smaller than $\mathcal A_{min}^2$.
For example observe that, if $\mathcal A_{min}$ is Wheeler, then $\mathcal I(u) \cap \mathcal I(v) = \emptyset$ for all states $u\neq v$ of $\mathcal A_{min}$ (see Definition <ref> and Lemma <ref>), so $\mathcal {\hat A}_{min}^2$ is empty.
As a matter of fact, we show that the size of $\mathcal {\hat A}_{min}^2$ depends on the width of the (partial [6]) order $<_{\mathcal A_{min}}$:

The co-lex width $width(\mathcal A)$ of a DFA $\mathcal A$ is the width of the order $<_{\mathcal A}$ defined in Definition <ref>.

The co-lex width is an important measure parameterizing problems such as pattern matching on graphs and compression of labeled graphs [5, 6].
Note that $width(\mathcal A_{min})=1$ if and only if $\mathcal A_{min}$ is Wheeler. In Appendix <ref> we prove:

Let $p = width(\mathcal A_{min})$. Then, $\mathcal {\hat A}_{min}^2$ has at most $2n(p-1)$ states and at most $2m(p-1)$ transitions and can be built from $\mathcal A_{min}$ in $O(mp)$ time.

The intuition behind Lemma <ref> is that $\mathcal {\hat A}_{min}^2$ contains only states $(u,v)$ such that $\mathcal I(u) \cap \mathcal I(v) \neq \emptyset$. By Lemma <ref>, this holds if and only if $u$ and $v$ are incomparable by the order  $<_{\mathcal A_{min}}$. Since the width of this order is (by definition) $p$, the bounds follow easily.
To build $\mathcal {\hat A}_{min}^2$, we sort the states of $\mathcal {\hat A}_{min}$ by the strings $\inf I_u$ and observe that incomparable states are adjacent in this order. It follows that we can easily build $\mathcal {\hat A}_{min}^2$ in time proportional to its size, $O(mp)$. The details of this algorithm can be found in Appendix <ref>.
Theorem <ref> follows.

§.§.§ Implementation

We implemented the algorithm of Theorem <ref> in C++. Our algorithm takes in input either a regular expression or a DFA and checks if the recognized language is Wheeler. We tested our algorithm on six randomly generated DFAs with different combinations of number of states and edges where $n=(500\cdot2^i: i=0,\ldots,5)$ and $m=3n$. Our experiments were run on a server with Intel(R) Xeon(R) W-2245498 CPU @ 3.90GHz with 8 cores and 128 gigabytes of RAM running Ubuntu 18.04 LTS 64-bit. As expected, our experimental results show that the running time of our algorithm grows linearly in $mp$. Since on our input instances, $p$ is roughly similar to $n$, and we double $n$ at each step, the running time shows a quadratic growth (see Table <ref>). The code is available at the GitHub repository <https://github.com/regindex/Wheeler-language-recognizer.git>.

Wall clock time for checking whether six different DFAs recognize a Wheeler language. We report on the x-axis the number of states and edges (left) and $mp$ (right).

§ A MATCHING CONDITIONAL LOWER BOUND

In this section, we show that an algorithm for WheelerLanguageDFA with running time $O(m^{2-\eta})$, yields an algorithm for the Orthogonal Vectors problem (see Definition <ref>) with running time $O(N^{2-\eta}\poly(d))$, thus contradicting SETH. This is our second main theorem (Theorem <ref>) formulated
in the introduction. We prove this theorem using Theorem <ref> and the following proposition.

For an instance of the OV problem, we can in $O(N(d+\log N))$ time construct a DFA $\mathcal A$
with $m\in O(N(d+\log N))$ edges
that is minimum for its language $\mathcal L(\mathcal A)$ such that the OV instance is a YES-instance if and only if $\mathcal{A}^2$ contains a cycle $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots \rightarrow (u_k,v_k) \rightarrow (u_1,v_1)$ such that, for $1\le \forall i \le k$, the following hold: (i) $u_i\neq v_i$ and (ii) $\mathcal{I}(u_i)\cap\mathcal{I}(v_i)\ne\emptyset$.

Once this proposition is established, we can take an OV instance with sets of size $N$ containing vectors of dimension $d \in \omega(\log N)$ and construct the DFA $\mathcal A$ of size $\Theta(m) = \Theta(N(d+\log N)) = \Theta(Nd)$. Now assume that we can solve WheelerLanguageDFA in $O(m^{2-\eta})$ on $\mathcal A$. Using Theorem <ref> and Proposition <ref>, we can thus solve the OV instance in $O((Nd)^{2-\eta}) = O(N^{2-\eta}\poly(d))$ time, as the OV instance is a YES instance if and only if the language recognized by $\mathcal A$ is not Wheeler. This shows Theorem <ref>.
The rest of this section is dedicated to illustrate how we prove Proposition <ref>. The details are deferred to Appendix <ref>.

§.§.§ Construction of $\mathcal A$

For a given instance $A=\{a_1,\ldots, a_N\}$ and $B=\{b_1,\ldots, b_N\}$ of the OV problem, we build a DFA $\mathcal{A}= (Q,\Sigma,\delta,s,F)$ with the properties in Proposition <ref> by adapting a technique of Equi et al. [9]. We first notice that we can, w.l.o.g., make the following assumptions on the OV instance: (1) The vectors in $A$ are distinct, (2) $N$ is a power of two, say $N= 2^\ell$. Furthermore, for an integer $i$ between 1 and $N$, let $\rho(i)$ be the bit-string of length $\ell$ that represents the integer $i - 1$ in binary.
We describe the construction of $\mathcal A$ based on a small example, while the general description is deferred to Appendix <ref>. We let $\Sigma=\{0,1,\#\}$. Later we show how to reduce the alphabet's size to 2.

shorten >=1pt,
every node/.style=minimum size=8mm

at (4, 5.85) $C^A_1:\quad a_1 = 110$;
at (4, 0)        $110\ \{0,1\}\{0,1\}\ \# $;
[circle, draw] (A)   at (0,0)         $\hat a_1$;
[circle, draw] (B)   at (2, -3.464)   $a_1^1$;
[circle, draw] (C)   at (6, -3.464)   $a_1^2$;
[circle, draw] (D)   at (8, 0)        $a_1^3$;
[circle, draw] (E)   at (6, 3.464)    $q_1^1$;
[circle, draw] (F)   at (2, 3.464)    $q_1^2$;
(A) edge [sloped] node $1$ (B)
(B) edge [sloped] node $1$ (C)
(C) edge [sloped] node $0$ (D)
(D) edge[bend right] [sloped] node $0$ (E)
(D) edge[bend left]  [sloped] node $1$ (E)
(E) edge[bend right] [sloped, below] node $0$ (F)
(E) edge[bend left]  [sloped, below] node $1$ (F)
(F) edge [sloped] node $\#$ (A);

at (4, 5.5) $C^A_2:\quad \textcolor{red}{a_2 = 100}$;
at (4, 0)        $\textcolor{red}{100}\ \{0,\textcolor{red}{1}\}\{\textcolor{red}{0},1\}\textcolor{red}{\ \#}$;
[circle, draw] (A)   at (0,0)         $\hat a_2$;
[circle, draw] (B)   at (2, -3.464)   $a_2^1$;
[circle, draw] (C)   at (6, -3.464)   $a_2^2$;
[circle, draw] (D)   at (8, 0)        $a_2^3$;
[circle, draw] (E)   at (6, 3.464)    $q_2^1$;
[circle, draw] (F)   at (2, 3.464)    $q_2^2$;
(A) edge[red, line width=1mm] [sloped] node $1$ (B)
(B) edge[red, line width=1mm] [sloped] node $0$ (C)
(C) edge[red, line width=1mm] [sloped] node $0$ (D)
(D) edge[bend right] [sloped] node $0$ (E)
(D) edge[bend left, red, line width=1mm] [sloped]  node $1$ (E)
(E) edge[bend right, red, line width=1mm]  [sloped, below] node $0$ (F)
(E) edge[bend left] [sloped, below]  node $1$ (F)
(F) edge[red, line width=1mm] [sloped] node $\#$ (A);

at (4, 5.5) $C^A_3:\quad a_3 = 111$;
at (4, 0)        $111 \  \{0,1\}\{0,1\}\ \#$;
[circle, draw] (A)   at (0,0)         $\hat a_3$;
[circle, draw] (B)   at (2, -3.464)   $a_3^1$;
[circle, draw] (C)   at (6, -3.464)   $a_3^2$;
[circle, draw] (D)   at (8, 0)        $a_3^3$;
[circle, draw] (E)   at (6, 3.464)    $q_3^1$;
[circle, draw] (F)   at (2, 3.464)    $q_3^2$;
(A) edge [sloped] node $1$ (B)
(B) edge [sloped] node $1$ (C)
(C) edge [sloped] node $1$ (D)
(D) edge[bend right] [sloped] node $0$ (E)
(D) edge[bend left] [sloped]  node $1$ (E)
(E) edge[bend right] [sloped, below] node $0$ (F)
(E) edge[bend left] [sloped, below]  node $1$ (F)
(F) edge [sloped] node $\#$ (A);

at (4, 5.5) $C^A_4:\quad a_4 = 011$;
at (4, 0)        $011 \  \{0,1\}\{0,1\}\ \#$;
[circle, draw] (A)   at (0,0)         $\hat a_4$;
[circle, draw] (B)   at (2, -3.464)   $a_4^1$;
[circle, draw] (C)   at (6, -3.464)   $a_4^2$;
[circle, draw] (D)   at (8, 0)        $a_4^3$;
[circle, draw] (E)   at (6, 3.464)    $q_4^1$;
[circle, draw] (F)   at (2, 3.464)    $q_4^2$;
(A) edge [sloped] node $0$ (B)
(B) edge [sloped] node $1$ (C)
(C) edge [sloped] node $1$ (D)
(D) edge[bend right] [sloped] node $0$ (E)
(D) edge[bend left] [sloped]  node $1$ (E)
(E) edge[bend right] [sloped, below] node $0$ (F)
(E) edge[bend left] [sloped, below]  node $1$ (F)
(F) edge [sloped] node $\#$ (A);

[xshift=0cm, yshift=-11.5cm]
at (4, 5.5) $C^B_1:\quad b_1 = 101$;
at (4, 0)        $0\{0,1\}0 \  00 \ \#$;
[circle, draw] (A)   at (0,0)         $\hat b_1$;
[circle, draw] (B)   at (2, -3.464)   $b_1^1$;
[circle, draw] (C)   at (6, -3.464)   $b_1^2$;
[circle, draw] (D)   at (8, 0)        $b_1^3$;
[circle, draw] (E)   at (6, 3.464)    $p_1^1$;
[circle, draw] (F)   at (2, 3.464)    $p_1^2$;
(A) edge [sloped] node $0$ (B)
(B) edge[bend right] [sloped] node $1$ (C)
(B) edge[bend left]  [sloped] node $0$ (C)
(C) edge [sloped] node $0$ (D)
(D) edge [sloped] node $0$ (E)
(E) edge [sloped] node $0$ (F)
(F) edge [sloped] node $\#$ (A);

[xshift=11cm, yshift=-11.5cm]
at (4, 5.5) $C^B_2:\quad b_2 = 101$;
at (4, 0)        $0\{0,1\}0 \  01 \ \#$;
[circle, draw] (A)   at (0,0)         $\hat b_2$;
[circle, draw] (B)   at (2, -3.464)   $b_2^1$;
[circle, draw] (C)   at (6, -3.464)   $b_2^2$;
[circle, draw] (D)   at (8, 0)        $b_2^3$;
[circle, draw] (E)   at (6, 3.464)    $p_2^1$;
[circle, draw] (F)   at (2, 3.464)    $p_2^2$;
(A) edge [sloped] node $0$ (B)
(B) edge[bend right] [sloped] node $1$ (C)
(B) edge[bend left]  [sloped] node $0$ (C)
(C) edge [sloped] node $0$ (D)
(D) edge [sloped] node $0$ (E)
(E) edge [sloped] node $1$ (F)
(F) edge [sloped] node $\#$ (A);

[xshift=22cm, yshift=-11.5cm]
at (4, 5.5) $C^B_3:\quad \textcolor{red}{b_3 = 010}$;
at (4, 0)        $\{0,\textcolor{red}{1}\}\textcolor{red}{0}\{\textcolor{red}{0},1\} \textcolor{red}{\ 10\ \#}$;
[circle, draw] (A)   at (0,0)         $\hat b_3$;
[circle, draw] (B)   at (2, -3.464)   $b_3^1$;
[circle, draw] (C)   at (6, -3.464)   $b_3^2$;
[circle, draw] (D)   at (8, 0)        $b_3^3$;
[circle, draw] (E)   at (6, 3.464)    $p_3^1$;
[circle, draw] (F)   at (2, 3.464)    $p_3^2$;
(A) edge[bend right, red, line width=1mm] [sloped] node $1$ (B)
(A) edge[bend left]  [sloped] node $0$ (B)
(B) edge[red, line width=1mm] [sloped] node $0$ (C)
(C) edge[bend right] [sloped] node $1$ (D)
(C) edge[bend left, red, line width=1mm]  [sloped] node $0$ (D)
(D) edge[red, line width=1mm] [sloped] node $1$ (E)
(E) edge[red, line width=1mm] [sloped] node $0$ (F)
(F) edge[red, line width=1mm] [sloped] node $\#$ (A);

[xshift=33cm, yshift=-11.5cm]
at (4, 5.5) $C^B_4:\quad b_4 = 111$;
at (4, 0)        $000 \  11 \ \#$;
[circle, draw] (A)   at (0,0)         $\hat b_4$;
[circle, draw] (B)   at (2, -3.464)   $b_4^1$;
[circle, draw] (C)   at (6, -3.464)   $b_4^2$;
[circle, draw] (D)   at (8, 0)        $b_4^3$;
[circle, draw] (E)   at (6, 3.464)    $p_4^1$;
[circle, draw] (F)   at (2, 3.464)    $p_4^2$;
(A) edge [sloped] node $0$ (B)
(B) edge [sloped] node $0$ (C)
(C) edge [sloped] node $0$ (D)
(D) edge [sloped] node $1$ (E)
(E) edge [sloped] node $1$ (F)
(F) edge [sloped] node $\#$ (A);

Illustration of the cycles generated for the bit vectors in the example $A=\{110, 100, 111, 011\}$ and $B=\{101, 101, 010, 111\}$. The two cycles $C^A_2$ and $C^B_3$ generate a match, i.e., can read the same string, as the vectors $a_2$ and $b_3$ are orthogonal.

Let $A=\{110, 100, 111, 011\}$ and $B=\{101, 101, 010, 111\}$ be the given instance of the OV problem. Thus $N=4$ and $\ell=\log_2N = 2$. Notice that the only pair of orthogonal vectors in $A$ and $B$ are $a_2 = 100$ and $b_3 = 010$.
In our DFA $\mathcal A$ we build (non-simple) cycles $C_i^A$ and $C_j^B$ for every vector $a_i$ and $b_j$ in $A$ and $B$ respectively.
As an example, for $a_2$ we build the cycle $C_2^A$ labeled with $100\{0,1\}\{0,1\}\#$, i.e. the bit string $100$ of $a_2$, followed by a sub-graph recognizing any bit string of length $\ell=2$, followed by $\#$. For $b_3$ we build the (non-simple) cycle $C_3^B$ labeled with $\{0,1\}0\{0,1\} 10 \#$, i.e., the bits 0 of $b_3$ are converted to a sub-graph recognizing both 0 and 1, and the bits 1 of $b_3$ are converted to an edge recognizing 0; this subgraph is followed by a path of length $\ell$ spelling $\rho(3) = 10$, which is followed by an edge labeled with $\#$. Notice that these two cycles indeed generate a match (underlined characters indicate the match): $\underline{100}\{0,\underline 1\}\{\underline 0,1\}\underline{\#}$ and $\{0,\underline 1\}\underline 0\{\underline 0,1\}  \underline{10}\underline{\#}$. It is not hard to see that a cycle $C_i^A$ and $C_j^B$ built in this way will match if and only if the two corresponding vectors are orthogonal. Characters $\#$ are introduced to synchronize the match (otherwise, other rotations of the cycles could match). The subgraphs between the part corresponding to the input vectors and the character $\#$ are introduced to avoid that two distinct cycles $C^B_i$ and $C^B_j$ ($i\neq j$) generate a match. Note that, since we assume that $A$ contains distinct vectors, distinct cycles $C^A_i$ and $C^A_j$ ($i\neq j$) will never generate a match.

The remaining details of the reduction ensure that (1) the graph is a connected DFA, (2) corresponding nodes (i.e. same distance from $\#$ in the cycles) $u,v$ in any pair of cycles $C^A_i$ and $C^B_j$ that correspond to orthogonal vectors $a_i$ and $b_j$, respectively, have a non-empty co-lexicographic intersection $\mathcal I(u) \cap \mathcal I(v)$, (3) the DFA is indeed minimum for its recognized language, and (4) the alphabet can be reduced to $\{0,1\}$ by an opportune mapping.

shorten >=1pt,
every node/.style=minimum size=7mm

at (-2.0, 0) $\mathcal A$:;

[circle, draw] (s)   at (0.5,0)  $s$;
[circle, draw] (b)   at (2.5,-4)  ;
[circle, draw] (a)   at (2.5,4)  ;
(s) edge [sloped] node $1$ (b);
(s) edge [sloped] node $0$ (a);
[circle, draw] (a1)   at (4.5,6)  ;
[circle, draw] (a2)   at (4.5,2)  ;
(a) edge [sloped] node $0$ (a1);
(a) edge [sloped] node $1$ (a2);
[circle, draw] (b1)   at (4.5,-2)  ;
[circle, draw] (b2)   at (4.5,-6)  ;
(b) edge [sloped] node $0$ (b1);
(b) edge [sloped] node $1$ (b2);

(d) at (6, 3) $\ldots$;
(d) at (6, -5) $\ldots$;

[draw = black, rounded corners, inner sep=100pt, dotted]
(-0.75, 1) – (2.5, 7.25) – (10.15, 8.5) – (10.15, -8.5) – (2.5, -7.25) – (-0.75, -1) – cycle ;
(empty)    at (1.0, -6.5)  $V^{out}$;

[circle, draw] (xN)   at (9, 2)  $x_{N}$;
at (9, 4.7) $\vdots$;
[circle, draw] (x1)   at (9, 7)  $x_{1}$;
[circle, draw] (y1)   at (9, -1.5)  $y_{1}$;
[circle, draw] (y2)   at (9, -3.5)  $y_{2}$;
at (9, -5) $\vdots$;
[circle, draw] (yN)   at (9, -7)  $y_{N}$;

[circle, draw] (y1p)   at (12, -1.5)  $y_{1}'$;
[circle, draw] (y2p)   at (12, -3.5)  $y_{2}'$;
[circle, draw] (yNp)   at (12, -7)  $y_{N}'$;
[circle, draw] (xNp)   at (12, 1)  $x_{N}''$;
[circle, draw] (xNpp)   at (12, 3)  $x_{N}'$;
[circle, draw] (x1p)   at (12, 6)  $x_{1}''$;
[circle, draw] (x1pp)   at (12, 8)  $x_{1}'$;

[circle, draw] (a1p)   at (15, 7)  $\hat a_{1}'$;
[circle, draw] (aNp)   at (15, 2)  $\hat a_{N}'$;
[circle, draw] (b1p)   at (15, -1.5)  $\hat b_{1}'$;
[circle, draw] (b2p)   at (15, -3.5)  $\hat b_{2}'$;
[circle, draw] (bNp)   at (15, -7)  $\hat b_{N}'$;

[circle, draw] (a1)   at (15, 7)  $\hat a_{1}$;
[circle, draw] (aN)   at (15, 2)  $\hat a_{N}$;
[circle, draw] (b1)   at (15, -1.5)  $\hat b_{1}$;
[circle, draw] (b2)   at (15, -3.5)  $\hat b_{2}$;
[circle, draw] (bN)   at (15, -7)  $\hat b_{N}$;

(y1) edge [sloped] node $0$ (y1p)
(y1p) edge [sloped] node $1$ (b1p);
(y2) edge [sloped] node $0$ (y2p)
(y2p) edge [sloped] node $1$ (b2p);
(yN) edge [sloped] node $0$ (yNp)
(yNp) edge [sloped] node $1$ (bNp);
(x1) edge [sloped] node $0$ (x1p)
(x1) edge [sloped] node $1$ (x1pp)
(x1p) edge [sloped] node $0$ (a1p)
(x1pp) edge [sloped] node $1$ (a1p);
(xN) edge [sloped] node $0$ (xNp)
(xN) edge [sloped] node $1$ (xNpp)
(xNp) edge [sloped] node $0$ (aNp)
(xNpp) edge [sloped] node $1$ (aNp);
(a1p) edge [sloped] node $0$ (a1)
(aNp) edge [sloped] node $0$ (aN)
(b1p) edge [sloped] node $0$ (b1)
(b2p) edge [sloped] node $0$ (b2)
(bNp) edge [sloped] node $0$ (bN);

[draw = black, rounded corners, inner sep=100pt, dotted]
(7.35, 9.0) – (13.65, 9.0) – (13.65, -9.0) – (7.35, -9.0) – cycle ;
(empty)    at (11, -8.5)  $I$;

[hanblue, fill=hanblue, opacity=0.4] (16, -1.5) ellipse (2cm and 0.9cm);
() at (17, -1.5) $C^B_1$;
[hanblue, fill=hanblue, opacity=0.4] (16, -3.5) ellipse (2cm and 0.9cm);
() at (17, -3.5) $C^B_2$;
at (16.5, -5) $\vdots$;
[hanblue, fill=hanblue, opacity=0.4] (16, -7) ellipse (2cm and 0.9cm);
() at (17, -7) $C^B_N$;

[orange, fill=orange, opacity=0.4] (16, 7) ellipse (2cm and 0.9cm);
() at (17, 7) $C^A_1$;
at (16.5, 4.7) $\vdots$;
[orange, fill=orange, opacity=0.4] (16, 2) ellipse (2cm and 0.9cm);
() at (17, 2) $C^A_N$;

[draw = black, rounded corners, inner sep=100pt, dotted]
(13.85, 8.0) – (18.1, 8.0) – (18.1, -8.0) – (13.85, -8.0) – cycle ;
(empty)    at (14.8, 8.5)  $C$;

[circle, draw] (t1)   at (19.5, 7)  $t_{1}$;
at (19.5, 4.7) $\vdots$;
[circle, draw] (tN)   at (19.5, 2)  $t_{N}$;
[circle, draw] (z1)   at (19.5, -1.5)  $z_{1}$;
[circle, draw] (z2)   at (19.5, -3.5)  $z_{2}$;
at (19.5, -5) $\vdots$;
[circle, draw] (zN)   at (19.5, -7)  $z_{N}$;

[] 		(CA1)   at (16.5, 7.2) ;
(CA1) edge [sloped, bend left=60] node $0$ (t1);
[] 		(CAN)   at (16.5, 2.2) ;
(CAN) edge [sloped, bend left=60] node $0$ (tN);
[] 		(CB1)   at (16.5, -1.3) ;
(CB1) edge [sloped, bend left=60] node $0$ (z1);
[] 		(CB2)   at (16.5, -3.3) ;
(CB2) edge [sloped, bend left=60] node $0$ (z2);
[] 		(CBN)   at (16.5, -6.8) ;
(CBN) edge [sloped, bend left=60] node $0$ (zN);

[circle, draw, accepting] (t)   at (28,0)  $t$;
[circle, draw] (tb)   at (26,-4)  ;
[circle, draw] (ta)   at (26,4)  ;
(tb) edge [sloped] node $1$ (t);
(ta) edge [sloped] node $0$ (t);

(d) at (22.5, 3) $\ldots$;
(d) at (22.5, -5) $\ldots$;

[circle, draw] (ta1)   at (24,6)  ;
[circle, draw] (ta2)   at (24,2)  ;
(ta1) edge [sloped] node $0$ (ta);
(ta2) edge [sloped] node $1$ (ta);

[circle, draw] (tb1)   at (24,-2)  ;
[circle, draw] (tb2)   at (24,-6)  ;
(tb1) edge [sloped] node $0$ (tb);
(tb2) edge [sloped] node $1$ (tb);

[draw = black, rounded corners, inner sep=100pt, dotted]
(29.25, 1) – (26, 7.25) – (18.3, 8.5) – (18.3, -8.5) – (26, -7.25) – (29.25, -1) – cycle ;
(empty)    at (27.5, -6.5)  $V^{in}$;

Illustration of our construction of $\mathcal A$ for an arbitrary instance $A=\{a_1,\ldots, a_N\}$ and $B=\{b_1,\ldots, b_N\}$ of the OV problem. The cycles $C_1^A, \dots, C_N^A, C_1^B, \dots, C_N^B$ are expanded in Figure <ref> on a particular OV instance.

An illustration of the overall construction for an arbitrary instance of the OV problem can be found in Figure <ref>. The complete proof is deferred to the appendix. We proceed with a sketch on how we achieve the above properties. Property (1) is achieved by connecting the above described cycles (we call the set of all cycles' nodes $C$), to the source node $s$ through a binary out-tree of logarithmic depth (we call these nodes $V^{out}$). Property (2) is achieved by connecting $V^{out}$ to $C$ through the nodes in $I$ that ensure that nodes $u \in C^A_i,v \in C^B_j$ in the same relative positions (i.e. same distance from $\#$) in their cycles that correspond to orthogonal vectors $a_i$ and $b_j$ are reached by strings of alternating co-lexicographic order, i.e., for a suitable string $\tau$, $I_u$ contains two strings suffixed by $00\tau$ and $11\tau$, while $I_v$ contains a string suffixed by $01\tau$.
This implies $\mathcal I(u) \cap \mathcal I(v) \neq \emptyset$.
Property (3) is instead achieved by connecting one node from each cycle $C^A_i$ and $C^B_j$ (the one with out-edge $\#$) with an edge labeled 0 to a complete binary in-tree (we call these nodes $V^{in}$) with root being the only accepting state $t$.
Observe that the
reversed automaton (i.e. the automaton obtained by reversing the direction of all the edges) is deterministic; this ensures that any two nodes in the graph can reach $t$ through a distinct binary string, witnessing that $\mathcal A$ is indeed minimal (by the Myhill-Nerode characterization of the minimum DFA [14]).
Property (4) can be easily satisfied by transforming the instance as follows. Edges labeled $0$ ($1$) are replaced with a directed path labeled with $00$ ($11$), while edges labeled $\#$ are replaced with a directed path labeled $101$. The pattern $101$ then appears only on the paths that originally corresponded to $\#$ and thus two transformed cycles match if and only if they used to match before the transformation. We note that also forward- and reverse- determinism (thus minimality) are maintained under this transformation (the nodes $\hat a'_i$ and $\hat b'_j$ in $I$ are introduced for maintaining reverse-determinism).

[1]
Abbott, H., Katchalski, M.: A Turán type problem for interval graphs.
Discrete Mathematics  25(1),  85–88 (1979).

[2]
Alanko, J., D'Agostino, G., Policriti, A., Prezza, N.: Wheeler languages.
Information and Computation  281,  104820 (2021).

[3]
Becker, R., Cáceres, M., Cenzato, D., Kim, S.H., Kodric, B., Olivares, F.,
Prezza, N.: Sorting finite automata via partition refinement (2023)

[4]
Conte, A., Cotumaccio, N., Gagie, T., Manzini, G., Prezza, N., Sciortino, M.:
Computing matching statistics on wheeler dfas. arXiv preprint
arXiv:2301.05338  (2023)

[5]
Cotumaccio, N., D'Agostino, G., Policriti, A., Prezza, N.:
Co-lexicographically ordering automata and regular languages. Part I
(2022), <https://arxiv.org/abs/2208.04931>

[6]
Cotumaccio, N., Prezza, N.: On Indexing and Compressing Finite Automata. In:
Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA). pp. 2585–2599 (2021). 10.1137/1.9781611976465.153

[7]
D'Agostino, G., Martincigh, D., Policriti, A.: Ordering regular languages and
automata: Complexity. Theoretical Computer Science  949,  113709
(2023). https://doi.org/10.1016/j.tcs.2023.113709,

[8]
Eizenga, J.M., Novak, A.M., Sibbesen, J.A., Heumos, S., Ghaffaari, A., Hickey,
G., Chang, X., Seaman, J.D., Rounthwaite, R., Ebler, J., Rautiainen, M.,
Garg, S., Paten, B., Marschall, T., Sirén, J., Garrison, E.: Pangenome
graphs. Annual Review of Genomics and Human Genetics  21(1),
139–162 (2020). 10.1146/annurev-genom-120219-080406,
<https://doi.org/10.1146/annurev-genom-120219-080406>, pMID: 32453966

[9]
Equi, M., Grossi, R., Mäkinen, V., Tomescu, A.I.: On the complexity of
string matching for graphs. In: Baier, C., Chatzigiannakis, I., Flocchini,
P., Leonardi, S. (eds.) 46th International Colloquium on Automata, Languages,
and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. LIPIcs,
vol. 132, pp. 55:1–55:15. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik (2019). 10.4230/LIPIcs.ICALP.2019.55,

[10]
Gagie, T., Manzini, G., Sirén, J.: Wheeler graphs: A framework for BWT-based
data structures. Theoretical Computer Science  698,  67–78 (2017).

[11]
Hopcroft, J.: An n log n algorithm for minimizing states in a finite automaton.
In: Theory of machines and computations, pp. 189–196. Elsevier (1971)

[12]
Impagliazzo, R., Paturi, R.: On the complexity of k-sat. Journal of Computer
and System Sciences  62(2),  367–375 (2001)

[13]
Kim, S.H., Olivares, F., Prezza, N.: Faster prefix-sorting algorithms for
deterministic finite automata (2023), to appear in the Proceedings of CPM

[14]
Nerode, A.: Linear automaton transformations. Proceedings of the American
Mathematical Society  9(4),  541–544 (1958)

[15]
Williams, R.: A new algorithm for optimal 2-constraint satisfaction and its
implications. Theor. Comput. Sci.  348(2-3),  357–365 (2005).

§ FUNDING
Ruben Becker, Davide Cenzato, Sung-Hwan Kim, Bojana Kodric, Nicola Prezza: Funded 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.

§ COMPUTING $\MATHCAL{I}(U)$ USING <CIT.>

We compute $\mathcal{I}(u)$ for each $u\in Q_{min}$ of the minimum DFA $\mathcal{A}_{min}$ using the partition refinement algorithm described in <cit.>.

In [3], it is assumed that some properties hold of the input automaton. In particular, (i) every state is reachable from the source state; (ii) the source state does not have any incoming transition; and (iii) input consistency, i.e. all transitions entering in a given state bear the same label.
It is worth noting that [3] does not assume the input automaton to be deterministic; their solution works for arbitrary NFAs.

The algorithm described in <cit.> works in three steps: (1) the infima strings are computed using <cit.>, (2) the suprema strings are computed using <cit.>, and finally (3) the two sets of strings are merged and sorted using the suffix doubling algorithm of [13] (running in linearithmic time on the pseudo-forests output by <cit.>).
Since, in our paper, we run <cit.> on the minimum DFA $\mathcal A_{min}$. This automaton satisfies (1),
but it does not necessarily satisfy (ii) and (iii). We now show that any DFA $\mathcal A$ satisfying (i) and (ii) can be transformed into two NFAs $\mathcal A_{inf}$ and $\mathcal A_{sup}$ satisfying conditions (i-iii) and preserving the infima/suprema strings of $\mathcal A$, respectively.
The transformation takes linear time in the input automaton.

We describe how to transform $\mathcal{A}$ into $\mathcal{A}_{inf}=(Q_{inf},\Sigma_{inf},\delta_{inf},s_{inf},F_{inf})$ that will be fed into <cit.> to compute the infima strings of $\mathcal{A}$.
The procedure for $\mathcal{A}_{sup}$ is symmetric.
In summary, we add two new states $s'$, $s''$, two new symbols $\$$ and $\#$ to the alphabet, and we define the transition function $\delta_{inf}$ appropriately in order to make $\mathcal{A}_{inf}$ satisfy (i-iii) while also preserving the infima strings of $\mathcal A$.

* We define $Q_{inf}=Q\cup\{s_{inf},s'\},\Sigma_{inf}=\Sigma\cup\{\$,\#\},s_{inf},F_{inf}=F$.

* To make $\mathcal{A}_{inf}$ input-consistent, for each state we keep only the incoming transitions with the minimum label. More formally, for $u,v\in Q\cup\{s'\}$ and $a\in\Sigma$ such that $\delta(v,a)=u$, $\delta_{inf}(v,a)=u$ iff $a=\lambda(u)$, where $\lambda(u) = \min\{c\in\Sigma:\exists w\in Q\cup\{s'\}~\delta(w,c)=u\}$ is the minimum label of $u$'s incoming transitions; for convenience, we define $\delta(s',\$)=s$ where $\$$ is a special symbol with $\$\prec a$ for all $a\in\Sigma$.

* To make $\mathcal{A}_{inf}$ connected, we connect the state $s'$ to every $u\in Q_{inf}\setminus\{s_{inf},s'\}$ with a transition $\delta_{inf}(s',\lambda(u))=u$.

* Finally, we create a transition from the new source $s_{inf}$ to $s'$ with label $\#$, and the order on $\Sigma_{inf}$ is defined as: $\$\prec a\prec\#$ for all $a\in\Sigma$. This prevents the transitions defined in the previous step from affecting the infima strings of the automaton.

We show that the infima strings are preserved after this transformation. More precisely, for any given state $u\in Q$, let $\alpha$ and $\beta$ be the infimum string of $u$ on $\mathcal{A}_{inf}$ and $\mathcal{A}$, respectively. Then we claim that (i) $\alpha=\beta$ if $\beta$ has infinite length, and (ii) $\alpha=\#\$\beta$ if $\beta$ is a finite string. Note that the order between a finite string and a string of infinite length is also preserved because $\$$ is smaller than any symbol $a\in\Sigma$.
Let us assume for a contradiction that there exists $u\in Q$ such that this is not satisfied. We consider two cases: (i) the condition is falsified because we removed transitions in Step 2 or (ii) the infimum string is preserved in Step 2 but adding the new state $s'$ and $s_{inf}$ with new transitions in Steps 3 and 4 affects the infimum string. (i) If Step 2 affects the infimum string, $\beta$ must end with some $b(\in\Sigma)$ with $b\ne a=\min\{c\in\Sigma:\exists w\in Q~\delta(w,c)=u\}$, which implies there exists $\alpha'\in\Sigma^*\cup\Sigma^\omega$ entering $u$ such that $\alpha'$ ends with $a$ thereby being $\alpha'\prec \beta$, contradicting the definition of the infimum string. (ii) If added states and transitions in Steps 3 and 4 affect the infimum string, then we can observe that it must be $\alpha=\#\cdot\lambda(u)$, and it must also hold $\alpha\preceq\beta$ by definition of infimum string. However, this can happen only for the source state $s$ of $\mathcal{A}$. To see this, we observe that every state $u(\ne s)$ in $\mathcal{A}$ has at least one incoming transitions because it is reachable from the source, thus $\beta=\beta'\cdot\lambda(u)$ for some non-empty string $\beta'\in\Sigma^+\cup\Sigma^\omega$. Because $a\prec \#$ for every $a\in\Sigma$, we have $\beta'\prec \#$, which implies $\beta'\cdot\lambda(u)\prec\#\cdot\lambda(u)$; thus the infimum string is not affected by Step 3 except on state $s$. Note that only the state $s$ can have the empty string as its infimum string on $\mathcal{A}$, i.e. $\beta=\epsilon$, which is a finite string. Now we show $\alpha=\#\$\beta$ holds in the case that $\beta$ is finite string, which also includes the case $u=s$. For any $u$ that has a finite infimum string $\beta$, we can observe that $\delta_{inf}(s,\beta)=u$ by Lemma <ref>.<ref> and there is no string $\gamma\in\Sigma^*$ such that $\gamma\prec\beta$ and $\delta_{inf}(s,\gamma)=u$ because the infimum string is preserved in Step 2. Since $\#\$$ is the unique string labeling the path from the new source $s''$ and $s$, $\#\$\beta$ is the smallest string labeling the path from $s''$ to $u$.

Transforming $\mathcal{A}$ info $\mathcal{A}_{sup}$ is symmetric. In Step 2, we keep only the transitions with maximum labels. In Step 4, we define $\#$ as the smallest symbol; i.e. $ \#\prec \$\prec a$ for every $a\in\Sigma$.

As far as the running time of the transformation is concerned, the number of states is increased by just 2 and the number of transitions is increased by at most $n+1=O(m)$, so the process takes linear time. Computing the co-lex order of the infima and suprema strings takes therefore $O(O(m)\lg (n+2))=O(m\lg n)$ time as claimed.

§ PARAMETERIZED ALGORITHM

§.§ Proof of Lemma <ref>

We first prove the following lemma.

Let $S=\{(x_i,y_i)\ :\ i\in [n]\}$ be a (multi-)set of $n$ open intervals over domain $x_i,y_i \in [2n]$ with $x_i<y_i$. For an integer $p\ge 1$, suppose there exist no $p+1$ pairwise intersecting intervals in $S$. Let $J=\{ (i,j)\in[n]^2:i\ne j\land (x_i,y_i)\cap(x_j,y_j) \neq\emptyset\}$ be the set of (indices of) intersecting intervals of $S$. Then $|J|\le 2n(p-1)$.

Consider the open-interval graph $G$ constructed from $S$ (that is, the undirected graph with set of nodes $S$ and edges connecting intersecting intervals).
Since no $p+1$ intervals in $S$ are pairwise intersecting, there is no clique of size $p+1$ in such an interval graph.

We apply the transformation of <cit.> to the set of open intervals $S = \{(x_i,y_i)\ :\ i\in[n]\}$
mapping each $(x_i,y_i)$ into a closed interval $[x_i,y_i]$ over domain $x'_i,y'_i \in [4n+1]$ with the property that $(x_i,y_i) \cap (x_j,y_j) \neq \emptyset$ if and only if $[x'_i,y'_i]\cap [x'_j,y'_j] \neq \emptyset$.
Let $S' = \{[x'_i,y'_i]\ :\ i\in[n]\}$ be the transformed interval set.
As a result, no $p+1$ intervals in $S'$ are pairwise intersecting.

The number of edges of a closed-interval graph (i.e. constructed from closed intervals) that does not contain a clique of size $p'=p+1$ is known to be not greater than $\frac{1}{2}(p'-1)(p'-2)+(n-p'+1)(p'-2) \le n(p-1)$ <cit.>.
Then, by <cit.>, also the open-interval graph $G$ corresponding to intervals $S$ contains at most $n(p-1)$ edges.
Note that the size of $J$ is equal to twice the number of edges of $G$. Our claim follows.

We proceed with the proof of Lemma <ref>.
Recall that $p=width(\mathcal{A}_{min})$ implies that there exist no $p+1$ pairwise incomparable states with respect to the order $<_{\mathcal{A}_{min}}$ defined in Definition <ref>.
From Lemma <ref>, this is equivalent to the fact that there are no $p+1$ pairwise intersecting open intervals $\mathcal{I}(u) = (\inf I_u, \sup I_u)$ in $\mathcal{A}_{min}$.
From Lemma <ref>,
the set $\{\mathcal{I}(u)=(\inf I_u, \sup I_u)\ :\ u\in Q_{min}\}$ contains at most $2n(p-1)$ pairs of intersecting intervals, implying that the number of states of $\mathcal {\hat A}_{min}^2$ is $|\{(u,v)\in Q_{min}^2: u\ne v\land\mathcal{I}(u)\cap\mathcal{I}(v)\ne\emptyset\}| \leq 2n(p-1)$.

Now we shall show the number of transitions of $\hat{\mathcal{A}}^2_{min}$ is at most $2m(p-1)$.
For each $a\in\Sigma$, consider the set $Q_a=\{u\in Q_{min}: \exists v\in Q_{min}:\delta'(u,a)=v\}$ of states of $Q_{min}$ that have an outgoing transition labeled with $a$.
Since $Q_a$ is a subset of $Q_{min}$, there are no $p+1$ pairwise intersecting intervals in the set $\{\mathcal{I}(u)=(\inf I_u, \sup I_u)\ :\ u\in Q_a\}$. By Lemma <ref>, this implies that $Q_a$ contains at most $2|Q_a|(p-1)$ pairs of intersecting intervals.
Observe that the pruned square automaton $\hat{\mathcal{A}}^2_{min}$ has a transition from $(u,v)\in Q^2_{min}$ to $(u',v')\in Q^2_{min}$ labeled by $a$ only if $(u,v)\in Q_a^2$ and $\mathcal{I}(u)\cap\mathcal{I}(v)\ne\emptyset$.
Since $\hat{\mathcal{A}}^2_{min}$ is a DFA, the state $(u,v)\in Q^2_{min}$ and letter $a$ uniquely determine this transition, so the number of transitions with label $a$ in $\hat{\mathcal{A}}^2_{min}$ is at most $2|Q_a|(p-1)$.
The total number of transitions in $\hat{\mathcal{A}}^2_{min}$ is therefore at most $\sum_{a\in\Sigma} 2|Q_a|(p-1)\le 2m(p-1)$ because $\sum_{a\in\Sigma}|Q_a|= m$.

The algorithm

We now present an algorithm to build $\mathcal {\hat A}_{min}^2$ in a time proportional to its size $O(mp)$.

We first
show how to build the $O(np)$ states of $\mathcal {\hat A}_{min}^2$ in $O(np)$ time.
We sort intervals[Recall that we represent each $\inf I_u$ and $\sup I_u$ with an integer in the range $[1,2n]$: the co-lexicographic rank of those strings in the set $\{\inf I_u:u\in Q\}\cup\{\sup I_u:u\in Q\}$. As a result, we can radix-sort these intervals in $O(n)$ time.]
$\mathcal I(u) = (\inf I_u,\sup I_u)$ for $u\in Q$ in increasing order by their first components $\inf I_u$. Let $\mathcal I(u_1), \dots, \mathcal I(u_n)$ be the resulting order. Notice that, given a state $u_i$, all states $u_j$ such that $\mathcal I(u_i) \cap \mathcal I(u_j) \neq \emptyset$ are adjacent in this order.
Then, the $O(np)$ states $(u,v)$ of $\mathcal {\hat A}_{min}^2$ can be built in $O(np)$ time with the following algorithm: (1) initialize $i=1$ and $j=2$. (2) If $j\leq n$ and $\mathcal I(u_i) \cap \mathcal I(u_j) \neq \emptyset$, then create states[Note that $\mathcal {\hat A}_{min}^2$ is symmetric: if $(u,v)$ is a state, then also $(v,u)$ is a state (a similar property holds for its transition function). Although we could further prune it by removing this symmetry, this would slightly complicate our notation.] $(u_i,u_j)$ and $(u_j,u_i)$ and increment $j$.
Otherwise, increment $i$ and set $j=i+1$. (3) If $i<n$, go to step (2).

Each step of the algorithm either creates a new state of $\mathcal {\hat A}_{min}^2$ or increments $i$ ($i$ can be incremented at most $n$ times). It follows that its running time is proportional to the number of states, $O(np)$.

To conclude, we show how to build the $O(mp)$ transitions of $\mathcal {\hat A}_{min}^2$ in $O(mp)$ time; let us denote with $\delta''$ the transition function of  $\mathcal {\hat A}_{min}^2$.
Let $\mathcal I(u_1), \dots, \mathcal I(u_n)$ be the order defined above. For each $a\in \Sigma$, we build an array $L_a$ defined as follows: $L_a$ contains all states $u_i$ such that $u_i$ has an outgoing edge labeled with $a$, sorted by increasing index $i$.
Let $m_a$ denote the number of nodes in array $L_a$.
Clearly, the total number of nodes in all arrays is $\sum_{a\in\Sigma} m_a  = m$ since we add a node in one of those arrays for each edge of $\mathcal A_{min}$; moreover, those arrays can be built in $O(m)$ time by simply visiting all nodes in the order $u_1, \dots, u_n$: when visiting $u_i$, for all $a\in \Sigma$ labeling an outgoing edge of $u_i$, append $u_i$ at the end of $L_a$.

To build the transition function $\delta''$ of $\mathcal {\hat A}_{min}^2$ in $O(mp)$ time, for each $a\in \Sigma$ we run the following algorithm. (1) initialize $i=1$ and $j=2$. (2) We distinguish three cases (A-C):

(A) If $j\leq m_a$ and $(L_a[i],L_a[j])$ and $(\delta_{min}(L_a[i],a),\delta_{min}(L_a[j],a))$ are both states of $\mathcal {\hat A}_{min}^2$ (as computed above), create the two symmetric transitions

\begin{array}{l}
\delta''((L_a[i],L_a[j]),a) = (\delta_{min}(L_a[i],a),\delta_{min}(L_a[j],a))\\
\delta''((L_a[j],L_a[i]),a) = (\delta_{min}(L_a[j],a),\delta_{min}(L_a[i],a))
\end{array}

and increment $j$.

(B) If $j\leq m_a$ and $(L_a[i],L_a[j])$ is a state
while $(\delta_{min}(L_a[i],a),\delta_{min}(L_a[j],a))$ is not, just increment $j$.

(C) If none of $(L_a[i],L_a[j])$ and $(\delta_{min}(L_a[i],a),\delta_{min}(L_a[j],a))$ are states in $\mathcal{A}^2_{min}$ or if $j > m_a$, increment $i$ and set $j=i+1$.

Each step of the algorithm either creates a new transition of $\mathcal {\hat A}_{min}^2$ (case A), visits a state $(L_a[i],L_a[j])$ of $\mathcal {\hat A}_{min}^2$ (case B: note that in this case $j$ is incremented, so no state is visited twice), or increments $i$ (case C: note that $i$ can be incremented at most $m_a$ times). It follows that its running time is proportional to the number of states plus the number of transitions, $O(mp)$.

§ REDUCTION DETAILS

We start with a detailed description of the DFA $\mathcal A= (Q, \Sigma, \delta, s, F)$ constructed for an OV instance  $A=\{a_1,\ldots, a_N\}$ and $B=\{b_1,\ldots, b_N\}$.
The states $Q$ of $\mathcal A$ consist of four disjoint sets $V^{out}$, $I$, $C$, and $V^{in}$. We will now define these four sets and the transitions connecting them (thus defining $\delta$). We refer the reader back to Figure <ref> for an illustration.

$V^{out}$: The set $V^{out}$ is connected as a complete binary out-tree of depth $\ell + 1$ with root being the source node $s$. This tree has $2N$ leaves that we call $x_1,\ldots, x_N$ and $y_1,\ldots, y_N$ and is such that a leaf node $x_i$ is reached from $s$ by a unique path labeled $0\rho(i)$, while a leaf node $y_j$ is reached from $s$ by a unique path labeled $1\rho(j)$.

$I$: The set $I$ consists of $5N$ nodes, $x_i'$, $x_i''$, and $\hat a_i'$ for $i\in [N]$ and $y_j'$ and $\hat b_j'$ for $j\in [N]$. A node $\hat a_i'$ is reachable from $x_i\in V^{out}$ by two paths through $x_i'$ and $x_i''$ labeled $11$ and $00$, respectively. A node $\hat b_j'$ is reachable from $y_j\in V^{out}$ by a path labeled $01$ through $y_j'$.

$C$: The set $C$ is composed of $2N$ disjoint sets (cycles), $C_i^A$ for $i\in[N]$ and $C_j^B$ for $j\in[N]$. Each set $C_i^A$ contains a node $\hat a_i$ and each set $C_j^B$ contains a node $\hat b_j$. Every node $\hat a_i$ ($\hat b_j$) is reachable from $\hat a'_i\in I$ ($\hat b'_j\in I$) by an edge labeled 0. Each set $C_i^A$ and $C_j^B$ consists of $d + \ell + 1$ nodes. These nodes are connected in a cycle-like way as illustrated in Figure <ref>: (1) From node $\hat a_i$, we can exactly read the bit string $a_i$ that is equal to the $d$ bits in the input vector $a_i$ (note that we slightly abuse notation here by denoting with $a_i$ both the string and the vector) by passing through the subsequent states $(\hat a_i = a_i^0), a_i^1, \ldots, a_i^d$. From $a_i^d$, we can then read any sequence of $d$ bits in $\{0,1\}^\ell$ by passing through the states $q_i^1,\ldots, q_i^\ell$ followed by the character $\#$ and arriving back at node $\hat a_i$. The latter sequence of nodes is the gadget $Q_i$ from Figure <ref>. (2) From node $\hat b_j$, we can also read strings of length $d$ that however depend on the input vector $b_j$, this time by passing through subsequent states $(\hat b_j=b_j^0), b_j^1, \ldots, b_j^d$. If $b_j[r]=1$, node $b_{j-1}^r$ is connected to node $b_j^r$ with one edge labeled with 0. If $b_j[r]=0$, node $b_{j-1}^r$ is connected to node $b_j^r$ with two edges, labeled with 0 and 1 respectively. From $b_j^d$, we can then read the string $\rho(j)$ by passing through the states $p_j^1,\ldots, p_j^\ell$ followed by the character $\#$ and arriving back at node $\hat b_j$. The latter sequence of nodes is the gadget $P_j$ from Figure <ref>.

$V^{in}$: The set $V^{in}$ is connected as a complete binary in-tree of depth $\ell + 1$ with root being a state $t$. This tree again has $2N$ leaves that we call $t_1,\ldots, t_N$ and $z_1,\ldots, z_N$ and is such that a leaf node $t_i$ can reach the root $t$ by a unique path labeled $\rho(i)0$, while a leaf node $z_j$ can reach $t$ by a unique path labeled $\rho(j)1$. Every node $t_i$ is reachable from $q_i^\ell\in C^A_i$ by an edge labeled $0$ and every node $z_j$ is reachable from $p_j^\ell\in C^B_j$ by an edge labeled $0$.

Finally we define the set of final states as $F:=\{t\}$. We proceed with the following observation:
The constructed DFA $\mathcal A$ is in fact minimal, i.e., $\mathcal A = \mathcal A_{min}$. This is an easy observation from inspecting the reversed automaton $\mathcal A^r$ that has the same set of states, $t$ as source node, and all transitions reversed compared to $\mathcal A$. We observe that $\mathcal A^r$ is also deterministic and thus every state in $\mathcal A^r$ is reached by a unique string from the source state $t$. It follows that every two states $u,v$ are clearly distinguishable in $\mathcal A$ by the Myhill-Nerode relation[Two states are Myhill-Nerode equivalent — i.e. they can be collapsed in the minimum DFA — if and only if they allow reaching final states with the same set of strings.] [14] as they can reach the only final state $t$ using a unique string.

shorten >=1pt,
every node/.style=minimum size=8mm

[yshift=6cm, xshift=4cm]
[orange] at (-0.5, 3.85) $C^A_i:$;
[circle, draw] (A)   at (0,0)  $\hat a_i$;
[circle, draw] (B)   at (4 - 2.8284, -2.8284) $a_i^1$;
[circle, draw] (C)   at (4, -4)  $a_i^2$;
[circle, draw] (D)   at (4 + 2.8284, -2.8284) $a_i^3$;
[circle, draw] (E)   at (8, 0)  $a_i^4$;
[circle, draw] (F)   at (4 + 2.8284, 2.8284) ;
[circle, draw] (G)   at (4, 4)  ;
[circle, draw] (H)   at (4 - 2.8284, 2.8284)  $a_i^d$;
(A) edge [sloped] node $a_i[1]$ (B)
(B) edge [sloped] node $a_i[2]$ (C)
(C) edge [sloped] node $a_i[3]$ (D)
(D) edge [sloped] node $a_i[4]$ (E)
(E) edge[white] [sloped] node[black] $\ldots$ (F)
(F) edge [sloped] node $a_i[d-1]$ (G)
(G) edge [sloped] node $a_i[d]$ (H)
(H) edge[line width=1mm, dashed] [sloped, color=darkgreen] node $Q_i$ (A);

[yshift=6cm, xshift=15cm]
[hanblue] at (-0.5, 3.85) $C^B_j:$;
[circle, draw] (A)   at (0,0)  $\hat b_j$;
[circle, draw] (B)   at (4 - 2.8284, -2.8284) $b_j^1$;
[circle, draw] (C)   at (4, -4)  $b_j^2$;
[circle, draw] (D)   at (4 + 2.8284, -2.8284) $b_j^3$;
[circle, draw] (E)   at (8, 0)  $b_j^4$;
[circle, draw] (F)   at (4 + 2.8284, 2.8284) ;
[circle, draw] (G)   at (4, 4)  ;
[circle, draw] (H)   at (4 - 2.8284, 2.8284)  $b_j^d$;
(A) edge [sloped] node $0$ (B)
(B) edge[bend left] [sloped] node $0$ (C)
(C) edge [sloped] node $0$ (D)
(D) edge[bend left] [sloped] node $0$ (E)
(E) edge[white] [sloped] node[black] $\ldots$ (F)
(F) edge [bend right] [sloped]node $0$ (G)
(G) edge [sloped] node $0$ (H)
(H) edge[line width=1mm, dashed] [sloped, color=darkyellow] node $P_j$ (A);

(B) edge[bend right] [sloped] node $1$ (C)
(D) edge[bend right] [sloped] node $1$ (E)
(F) edge [bend left] [sloped] node $1$ (G);

[yshift=-0.5cm, xshift=4cm]
[darkgreen] at (-2, 0) $Q_i:$;
[circle, draw] (A)   at (0,0)  $a_i^d$;
[circle, draw] (B)   at (4,0)  $q_i^1$;
[circle, draw] (C)   at (8,0) $q_i^2$;
[circle, draw] (D)   at (12,0) ;
[] 		(D)   at (10.5,0)  $\ldots$;
[circle] 	(E)   at (12,0)  ;
[circle, draw] 	(F)   at (16,0)  $q_i^{\ell}$;
[circle, draw] 	(G)   at (20,0)  $\hat a_i$;

(A) edge [above, bend left] node $0$ (B)
(B) edge [above, bend left] node $0$ (C)
(C) edge [above, bend left] node  (D)
(E) edge [above, bend left] node $0$ (F);

(A) edge [above, bend right] node $1$ (B)
(B) edge [above, bend right] node $1$ (C)
(C) edge [above, bend right] node  (D)
(E) edge [above, bend right] node $1$ (F);
(F) edge [above] node $\#$ (G);

[yshift=-3cm, xshift=4cm]
[darkyellow] at (-2, 0) $P_j:$;
[circle, draw] (A)   at (0,0)  $b_j^d$;
[circle, draw] (B)   at (4,0)  $p_j^1$;
[circle, draw] (C)   at (8,0) $p_j^2$;
[circle, draw] (D)   at (12,0) ;
[] 		(D)   at (10.5,0)  $\ldots$;
[circle] 	(E)   at (12,0)  ;
[circle, draw] 	(F)   at (16,0)  $p_j^\ell$;
[circle, draw] 	(G)   at (20,0)  $\hat b_j$;

(A) edge [above] node $\rho(j)[1]$ (B)
(B) edge [above] node $\rho(j)[2]$ (C)
(C) edge [above] node  (D)
(E) edge [above] node $\rho(j)[\ell]$ (F)
(F) edge [above] node $\#$ (G);

Illustration of $C_i^A$ and $C_j^B$ containing the subgraphs $Q_i$ and $P_j$, respectively.

§.§ Proof of Proposition <ref>

We are now ready to prove Proposition <ref>. We start with the following lemma.

Let $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots \rightarrow (u_k,v_k) \rightarrow (u_1,v_1)$ be a cycle in $\mathcal{A}^2$ such that, for $1\le \forall i \le k$, $u_i\neq v_i$. Then, there exist $r, s \in [N]$ and $\ell\in [k]$ such that $\hat a_r=u_\ell$ and $\hat b_s = v_\ell$ (or vice versa) and furthermore $\{u_1, \ldots, u_k\} = C_r^A$ and $\{v_1, \ldots, v_k\} = C_s^B$ (or vice versa).

For simplicity let us call $C=\{u_1, \ldots, u_k\}$ and $C'=\{v_1, \ldots, v_k\}$ and let us take the indices of those nodes modulo $k$, i.e., $u_{i+k} = u_i$.
We first notice that the only directed cycles in $\mathcal A$ are $C_r^A$ for $r\in[N]$ and $C_s^B$ for $s\in[N]$ and they are all of length $d+\ell$. Hence $k=d+\ell+1$. As the character $\#$ appears only once in every such cycle, it follows that there exists $\ell\in [k]$ such that $u_\ell, v_\ell\in \{\hat a_r:r\in [N]\} \cup \{\hat b_s:s\in [N]\}$.
We now proceed by showing that it cannot be that $C = C_r^A$ and $C' = C_{r'}^A$ for some $r,r'\in[N]$ or $C = C_s^B$ and $C' = C_{s'}^B$ for some $s,s'\in[N]$. First assume that $C = C_r^A$ and $C' = C_{r'}^A$ for some $r,r'\in[N]$. Notice that $r\neq r'$ by the assumption that $u_i\neq v_i$ for $1\le \forall i \le k$. We now directly get a contradiction as the labels of the edges $(u_\ell, u_{\ell +1}), \ldots, (u_{\ell + d - 1}, u_{\ell + d})$ and $(v_\ell, v_{\ell +1}), \ldots, (v_{\ell + d - 1}, v_{\ell + d})$ cannot match by the assumption that $A$ contains no two identical vectors. Now assume that $C = C_s^B$ and $C' = C_{s'}^B$ for some $s,s'\in[N]$. This analogously yields to a contradiction as $s\neq s'$ and the paths $P_s$ and $P_{s'}$ cannot have matching labels. It thus follows that $C = C_r^A$ for some $r\in[N]$ and $C' = C_{s}^B$ for some $s\in[N]$ (or vice versa). Consequently also $\hat a_r=u_\ell$ and $\hat b_s = v_\ell$ (or vice versa) and this completes the proof.

§.§.§ $(\Rightarrow)$

As the OV instance is a YES-instance, there exist vectors $a_r\in A$ and $b_s\in B$, $r,s\in[N]$ such that $a_r[i]\cdot b_s[i]=0$ for all $i\in [d]$. Let $C_r^A$ and $C_s^B$ be the node sets corresponding to $a_r$ and $b_s$ in $\mathcal A$ and let  $u_1, \ldots, u_{\ell + d + 1}$ and $v_1, \ldots, v_{\ell + d + 1}$ be the nodes in $C_r^A$ and $C_s^B$, respectively, starting from $u_1=\hat a_r$ and $v_1= \hat b_s$. We now need to show that these two cycles can be traversed using the same labels. For $i\in [d]$, transition  $(u_i, u_{i+1})$ is labeled $a_r[i]$. If $b_s[i]=0$, there exist transitions from $v_i$ to $v_{i+1}$ with both labels $0$ and $1$ and so we can always choose a transition matching $a_r[i]$. If $b_s[i]=1$, there exist only a transition labeled $0$ from $v_i$ to $v_{i+1}$, however in this case it must hold that $a_r[i]=0$ and thus the transition from $u_i$ to $u_{i+1}$ is again matched. Now for $d+1 \le i \le d + \ell$, node $u_{i+1}$ can be reached from node $u_i$ using any suitable transition. Then, it is clear that both cycles on the last transition $(u_{d+\ell+1}, u_1)$ and $(v_{d+\ell+1}, v_1)$ do the transition $\#$ resepctively. We call the string that can be read in both cycles $\gamma$. It remains to show that, for $1\le \forall i \le \ell + d + 1$, (i) $u_i\neq v_i$ and (ii) $\mathcal{I}(u_i)\cap\mathcal{I}(v_i)\ne\emptyset$. Property (i) is clearly true. For (ii), we let $s_1 = 0\rho(r)000\gamma[1..i]$, $s_2 = 1\rho(s)010\gamma[1..i]$, and $s_3 = 0\rho(r)110\gamma[1..i]$ and observe that $s_1 < s_2 < s_3$ and $s_1, s_3\in I_{u_i}$ as well as $s_2\in I_{v_i}$. It thus follows that $\mathcal{I}(u_i)\cap\mathcal{I}(v_i)\ne\emptyset$.

§.§.§ $(\Leftarrow)$

Let $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots \rightarrow (u_k,v_k) \rightarrow (u_1,v_1)$ be a cycle in $\mathcal{A}^2$ such that, for all $i \in [k]$, (i) $u_i\neq v_i$ and (ii) $\mathcal{I}(u_i)\cap\mathcal{I}(v_i)\ne\emptyset$. From Lemma <ref> it follows that there exist $r, s \in [N]$ and $\ell\in [k]$ such that $a_r=u_\ell$ and $b_s = v_\ell$ (or vice versa) and furthermore $\{u_1, \ldots, u_k\} = C_r^A$ and $\{v_1, \ldots, v_k\} = C_s^B$ (or vice versa). Furthermore $k=d+\ell+1$. W.l.o.g., assume that $a_r=u_1$, $b_s = v_1$ and $\{u_1, \ldots, u_k\} = C_r^A$ and $\{v_1, \ldots, v_k\} = C_s^B$. From $(u_1,v_1) \rightarrow (u_2,v_2) \rightarrow \dots (u_{d+1}, v_{d+1})$ we conclude that the label of $(v_i, v_{i+1})$ is equal to $a_r[i]$ for every $i\in [d]$. We are now ready to argue that $a_r[i] \cdot b_s[i]=0$ for every $i\in [d]$ and thus $a_r$ and $b_s$ are orthogonal. If $a_r[i]=0$, there is nothing to show. If $a_r[i]=1$, the previous claim yields that the label of $(v_i, v_{i+1})$ is $1$, which by definition of the transitions in $C_s^B$ implies that $b_s[i]=0$. Hence $a_r[i] \cdot b_s[i]=0$ also in this case.

§.§.§ Alphabet size 2

Finally, we observe that the constructed DFA $\mathcal A$ is over an alphabet of size $3$ as we introduced the letter $\#$ in addition to $0$ and $1$. We now apply the following transformation to $\mathcal A$ in order to obtain a DFA over the binary alphabet $\{0,1\}$. We replace every edge labeled with $0$ with a directed path of length 2 labeled with $00$, every edge labeled with $1$ with a directed path of length 2 labeled with $11$, and the edges labeled with $\#$ with a directed path of length 3 labeled with $101$. Since the pattern $101$ appears only on the paths that originally corresponded to the character $\#$, it is easy to see that two transformed cycles match if and only if they used to match before the transformation.
We note that this transformation preserves determinism of $\mathcal A$ as the nodes with outgoing edges labeled $\#$ have only two outgoing transitions, the one labeled $\#$ and one labeled $0$ going to the nodes in $V^{in}$. Recall that we used also determinism of the reversed graph $\mathcal A^r$ in order to argue that $\mathcal A$ is minimal. It is easy to see that the transformation also maintains determinism of the reversed graph as the nodes with ingoing transitions labeled $\#$ have only one second ingoing transition that is labeled $0$ (the one from the nodes in $I$).


# A Proposal for the Measurement and Documentation of Research Software
Sustainability in Interactive Metadata Repositories

Stephan Druskat  Department of German Studies and Linguistics
Humboldt-Universität zu Berlin
Berlin, Germany
<EMAIL_ADDRESS>
###### Abstract

This paper proposes an interactive repository type for research software
metadata which measures and documents software sustainability by accumulating
metadata, and computing sustainability metrics over them. Such a repository
would help to overcome technical barriers to software sustainability by
furthering the discovery and identification of sustainable software, thereby
also facilitating documentation of research software within the framework of
software management plans.

###### Index Terms:

Metadata, repositories, technical sustainability, information search and
retrieval, measurement, software management plans.

††publicationid: pubid: This work is licensed under a CC-BY-4.0 license.

The identification and discovery of sustainable research software present
technical barriers to software sustainability [1, p. 16f.]. This paper
proposes to tackle these barriers by accumulating and quantifying software
metadata in interactive metadata repositories (IMRs) to enable identification
of sustainable software through _sustainability measurement_ , and simplified
discovery of suitable software through _documentation of software and its
sustainability_.

In analogy to the discussion about data sustainability and funders’ mandate of
data management plans (DMPs), software management plans (SMPs) would be an
obvious tool for securing sustainability of newly developed software. DMPs
feature data repositories as natural targets for research data releases as
part of the data lifecycle documentation, and analogously, software
repositories should be an integral part of software lifecycles as detailed in
SMPs. In addition to source code repositories and distribution repositories
for deliverables, there are also already a large number of research data
repositories which archive research software source code and deliverables
along with some metadata (cf. re3data.org). However, while the latter may
provide support for assessing the suitability of a software for the intended
research application, they do not provide a lot of information about, not to
mention metrics of, the software’s sustainability. The same is true for
existing _metadata_ repositories dedicated to research software, e.g.,
SciencePAD, the EGI Applications Database, and the DiRT Directory. There are
also other platforms providing metadata for software, e.g., GitHub, Open Hub,
and Zenodo. Some of the metadata they provide – a rather small portion in the
case of GitHub and Zenodo, some more in the case of Open Hub – can indeed be
used to discover some sustainability aspects of the software they cover.
However, this facet is not presented explicitly in either of the platforms. In
any case, considering the available tools and platforms, users that are
interested in acquiring a comprehensive and in-depth understanding of how
sustainable a software is will have to interpret and extrapolate to a high
degree.

However, a repository can be a suitable means to provide documentation and
measurement of software sustainability, specifically by utilising software
metadata. In order to do so, it must: accumulate the metadata for a software
that is relevant for determining both its suitability for a research
application (to allow for straightforward discovery of software), and its
sustainability; compute sustainability metrics; document the metrics and
provide means to interactively evaluate and refine some of them. Such a
repository would also benefit projects which will be subject to funding
agencies’ potential mandate of SMPs, as it represents a natural means of
documenting the sustainability of software developed within the project.

The conception of the envisioned IMR poses at least three theoretical
challenges, namely (1) how to give “software sustainability” an
operationalisable definition, (2) how to define quantifiable criteria for
sustainability, and (3) how to design algorithms for computing comprehensible
and reproducible metrics for sustainability. While detailing (3) is beyond the
scope of this paper and is left for future research, (1) and (2) are
approached briefly in the following sections.

“Software sustainability” is an ambiguous concept, with different agents
approaching it from different angles. Reference [2] focuses on the ecological
sustainability of software, discussing software engineering only briefly.
Reference [3] focuses on the development process rather than the product.
Reference [4] – specifically discussing research software – names training,
availability, community recognition for developers, dedicated job
descriptions, and funding as defining factors for sustainability. A systematic
approach to a definition of sustainability in the context of software
engineering is presented in [5], which utilizes a basic definition of
sustainability as “preserving the function of a system over a defined
timespan” [5, p. 1184] for the refinement of detailed aspects of
sustainability for and in software engineering. However, while [5]’s approach
would be operationalisable, it uses a generic, multi-dimensional definition of
sustainability (cf. [6, p. 4]) and applies it to _engineering processes_
rather than to _features of products_ and is therefore not directly adaptable
for IMRs.

A definition of sustainability that can be operationalized for the purposes of
an IMR must in fact be based on the definition of “technical sustainability”
from [7, p. 470f.]: “Technical [sustainability] refers to longevity of
information, systems, and infrastructure and their adequate evolution with
changing surrounding conditions.” The two key points of this definition,
_longevity_ and _evolution_ , can be concretized by transforming another
existing global concept of “sustainability”. Following [8], an enhancement of
a three-dimensional general model of sustainability (“three column model”), we
can preliminarily define “software sustainability” via its goals: _The three
goals of software sustainability are_ (1) _ensuring the existence of the
software,_ (2) _preserving the potential for productive operation of the
software,_ (3) _creating and retaining possibilities for further development
and adaptation of the software._ This definition, finally, should be
employable for defining and categorizing suitable criteria for measuring the
sustainability of research software.

An IMR must accumulate quantifiable metadata pertaining to all three
sustainability goals. The parameters for the metrics to be computed over these
metadata must be based on criteria that are themselves categorized along the
lines of the sustainability goals. One starting point for the compilation of a
list of criteria is [9], which defines criteria for “sustainability”,
“maintainability”, and “usability” to facilitate the evaluation of software
products (e.g.: “Documentation is on the project web site”, “software has an
open source licence”, “source code is commented”). As the definition for
sustainability given above includes all three of these notions (usability
arguably counting towards goal (2)), the items given for the criteria in [9]
can be transformed into parameters for computing sustainability metrics for an
IMR, although some items may require further definitory work to make them
quantifiable. Further criteria that are not included in [9] – e.g., pertaining
to human resources available for a software project – can be identified
introspectively, elicitated or crowd-sourced, and made quantifiable.

In order to leverage fully the available metadata for a software, and at the
same time preserve the reproducibility of the sustainability metric and secure
it against manipulation, it is expedient to use more than one metric for the
representation of sustainability. E.g., a “hard” metric could be computed over
metadata that is both quantifiable and objective (such as whether a software
is open source or not), a “semi-hard” metric over metadata that is objective
but hard to quantify (e.g., use of a programming language or build system that
in itself may be more or less sustainable), and a “soft” metric taking into
account qualitative and subjective metadata (e.g., whether a UI is intuitive).
Both the “hard” and “semi-hard” metrics would be reproducible and would likely
be hard to tamper with, as they are based on objective metadata. The use of
these three metrics would additionally allow for user interaction with the
metadata, i.e., users could review and evaluate metadata, and these
evaluations could in turn be used to detect bad data and re-compute metrics
where necessary. User contributions in the form of, e.g., votes on or grading
of specific metadata points would inherently be constituting the “soft”
metric, while other forms of contributions, such as documenting the use of a
software (e.g., in conjunction with a reference to work documenting the use of
the software), could contribute to either of the “harder” metrics as well.
Interactivity can also be used for gamification purposes to attract users, and
provide software originators with further incentive to submit their data,
e.g., by releasing standings tables and issuing metrics graphics for use on
websites, etc.

The accumulation of the metadata can be performed by different means: direct
input by the originator of the software, harvesting data from existing
repositories via, e.g., GitHub and Open Hub APIs, dedicated crawling of source
code repositories, etc. The latter two methods can also be used for
verification and a preliminary quantification of the input. The metadata must
be available in the repository as structured text in a well-defined format,
e.g., based on XML or JSON.

In summary, an interactive metadata repository, field-specific or not, that
measures and documents the sustainability of software can be a valuable tool
not only for the discovery of research software, but also for the
identification of sustainable – and therefore preferable – software, and as an
integral part of the implementation of SMPs.

In future research, the author intends to further develop the idea of such
IMRs within the framework of a PhD thesis.

## References

  * [1] S. Hettrick, “Research software sustainability: Report on a Knowledge Exchange workshop,” The Software Sustainability Institute, Tech. Rep., 2016\. [Online]. Available: http://repository.jisc.ac.uk/6332/
  * [2] J. Gröger and M. Köhn, “Nachhaltige Software. Dokumentation des Fachgesprächs “Nachhaltige Software” am 28.11.2014,” Umweltbundesamt, Dokumentationen 07/2015, June 2015. [Online]. Available: http://www.umweltbundesamt.de/en/publikationen/nachhaltige-software
  * [3] K. Tate, _Sustainable Software Development: An Agile Perspective_. Boston, Mass.: Addison-Wesley, 2005.
  * [4] C. Goble, “Better software, better research,” _IEEE Internet Computing_ , vol. 18, no. 5, pp. 4–8, 2014.
  * [5] B. Penzenstadler, “Towards a definition of sustainability in and for software engineering,” in _Proceedings of the 28th Annual ACM Symposium on Applied Computing_ , ser. SAC ’13. New York, NY, USA: ACM, 2013, pp. 1183–1185. [Online]. Available: http://doi.acm.org/10.1145/2480362.2480585
  * [6] B. Penzenstadler and H. Femmer, “A generic model for sustainability with process- and product-specific instances,” in _Proceedings of the 2013 Workshop on Green in/by Software Engineering_ , ser. GIBSE ’13. New York, NY, USA: ACM, 2013, pp. 3–8. [Online]. Available: http://doi.acm.org/10.1145/2451605.2451609
  * [7] C. Becker, R. Chitchyan, L. Duboc, S. Easterbrook, B. Penzenstadler, N. Seyff, and C. C. Venters, “Sustainability design and software: The Karlskrona Manifesto,” in _2015 IEEE/ACM 37th IEEE International Conference on Software Engineering_ , vol. 2, May 2015, pp. 467–476.
  * [8] J. Jörissen, J. Kopfmüller, V. Brandl, and M. Paetau, _Ein integratives Konzept nachhaltiger Entwicklung_ , ser. Wissenschaftliche Berichte FZKA. Karlsruhe: Forschungszentrum Karlsruhe, 1999, no. 6393. [Online]. Available: http://www.itas.kit.edu/pub/v/1999/joua99a.pdf
  * [9] M. Jackson, S. Crouch, and R. Baxter, “Software evaluation: criteria-based assessment,” _Software Sustainability Institute_ , 2011.