Minimization of Deterministic Finite Automata Modulo the Edit Distance

This paper aims to provide a fresh perspective to the field of DFA minimization, which balances the conflicting objectives of state reduction and similarity of languages.

We introduce the problem of minimization of DFA modulo the edit distance, a novel approach that balances compactness with approximation flexibility. Unlike classical minimization, which focuses on preserving exact language equivalence, this approach allows for slight deviations between the original and minimized automata, measured by the edit distance, which enables significant state reduction while maintaining practical usability.

The problem is considered in two variants. In the fixed threshold variant (MIN-ED[$k$]), the goal is to find a DFA $ℬ$ with the minimal number of states such that the edit distance between the languages of the original DFA $𝒜$ and $ℬ$ is bounded by a given threshold $k\in \mathbb{N}$.

In the bounded threshold variant (MIN-BED), the objective is to find a minimal DFA $ℬ$ such that the edit distance between the languages of $𝒜$ and $ℬ$ is finite. This variant further loosens the constraints, allowing for more aggressive state reduction while still capturing the core structure of the original language.

These two perspectives provide a flexible framework for tailoring DFA minimization to the needs of specific applications, particularly in noisy or approximate environments.

Our main technical results are for the bounded threshold variant MIN-BED. We show that this problem is in general ${\mathrm{\Sigma }}_2^P$ and both NP-hard and coNP-hard, but we identify subclasses of DFA, which enjoy better complexity. We consider automata with a bounded depth of strongly connected components. We prove that for any $c$, restricting the problem to automata whose accepting runs visit at most $c$ different (maximal) strongly connected components reduces the complexity to NP. For cases $c\in \{1,2\}$, we provide polynomial-time algorithms and show NP-hardness for $c=3$.

For the fixed threshold variant MIN-ED[$k$], we prove that the problem is robustly PSpace-complete, in the sense that it is unclear how to restrict the class of DFA to gain better complexity results. In particular, we discuss that the hardness proof can be adapted to automata in which accepting runs visit at most one (maximal) strongly connected component.

Minimization of finite automata has been extensively studied [22, Chapter 10]. The foundational algorithms in this area were designed to reduce the state complexity of DFA while preserving their exact language equivalence. Notable among these are the algorithms proposed by Hopcroft [11], which works in $O(n\log n)$, the algorithm by Moore [20], which is quadratic in the worst case but enjoys better average-case complexity, and the algorithm by Brzozowski [5], which is exponential in the worst case, but often outperforms other algorithms in practice [2].

Building on these foundational methods, researchers have explored extensions and generalizations of DFA minimization. One significant direction is hyper-minimization, which allows for a relaxation of exact language equivalence by permitting finite differences between the languages of the original and minimized DFA. This approach has been studied extensively, with algorithms achieving $O(n\log n)$ complexity [10, 18]. Hyper-minimization has also been adapted to other automata models, such as deterministic tree automata [13] and deterministic weighted tree automata [19].

Language inclusion modulo the edit distance has been studied between regular languages represented by DFA and NFA [3], and regular and context-free languages represented by DFA, NFA, and DPDA [8].

Despite extensive research on DFA minimization, the problem of minimization modulo the edit distance has not been addressed in the literature. Our work fills this gap.

The edit distance between words $w,w^{\prime }$, denoted by $\text{ed}(w,w^{\prime })$, is the minimal number of operations: insertions of a letter, deletions of a letter, and substitutions of a letter, necessary to transform $w$ into $w^{\prime }$. For example, $\text{ed}(ab,acd)=2$ (one substitution and one insertion).

For a natural number $k$, we say that a language $ℒ$ is contained in a language ${ℒ}^{\prime }$ up to the edit distance $k$, denoted as $ℒ{\subseteq }_{\text{ed}}^k{ℒ}^{\prime }$, if and only if for each $w\in ℒ$ there is $w^{\prime }\in {ℒ}^{\prime }$ such that $\text{ed}(w,w^{\prime })\le k$. We extend this notion to ${\subseteq }_{\text{ed}}^{\mathrm{\infty }}$ by stating that $ℒ{\subseteq }_{\text{ed}}^{\mathrm{\infty }}{ℒ}^{\prime }$ if and only if for some $k\in \mathbb{N}$ we have $ℒ{\subseteq }_{\text{ed}}^k{ℒ}^{\prime }$. The relation ${\subseteq }_{\text{ed}}^k$ is transitive only for $k=\mathrm{\infty }$.

We say that DFA $𝒜,ℬ$ are equivalent up to the edit distance $k\in \mathbb{N}\cup \{\mathrm{\infty }\}$, denoted as $𝒜{\equiv }_{\text{ed}}^kℬ$, if and only if $ℒ(𝒜){\subseteq }_{\text{ed}}^kℒ(ℬ)$ and $ℒ(ℬ){\subseteq }_{\text{ed}}^kℒ(𝒜)$. Notice that $𝒜{\equiv }_{\text{ed}}^kℬ$ is an equivalence relation if and only if $k=\mathrm{\infty }$; in other cases, it is symmetric and reflexive, but not necessarily transitive.

We study decision problems called MIN-ED[$k$] for $k\in \mathbb{N}$ and MIN-BED defined as follows:
MIN-ED[$k$]: minimization modulo a fixed edit distance $k$
Input: A DFA $𝒜$ and a number $m$.  
Output: Is there a DFA $ℬ$ with at most $m$ states such that $𝒜{\equiv }_{\text{ed}}^kℬ$?
MIN-BED: minimization modulo a bounded edit distance
Input: A DFA $𝒜$ and a number $m$.  
Output: Is there a DFA $ℬ$ with at most $m$ states such that $𝒜{\equiv }_{\text{ed}}^{\mathrm{\infty }}ℬ$?

We recall a condition for checking containment modulo a bounded edit distance presented in [3, Theorem 4.1]. This condition is used in Sections 3 and 4.

Following [3], we consider minimal DFA, which recognize infinite languages. Note that all DFA that recognize finite non-empty languages are equivalent modulo a bounded edit distance, while the DFA that recognizes the empty language is only equivalent to itself. Conversely, a DFA that recognizes an infinite language can be equivalent modulo a bounded edit distance only to a DFA recognizing infinite language. Therefore, considering only DFA that recognize infinite languages removes only trivial cases.

For a DFA $𝒜$ (minimal and recognizing an infinite language), let $\text{SCC}(𝒜)$ be the set of all (maximal) strongly connected components of $𝒜$ containing an accepting state or from which an accepting state is reachable.

We define $\text{dag}(𝒜)$ as a directed acyclic graph whose set of nodes is $\text{SCC}(𝒜)$, and there is an edge from $C_1$ to $C_2$ if and only if $C_1\ne C_2$ and there is a transition from some state of $C_1$ to some state in $C_2$. Let ${\text{dag}}^{\ast }(𝒜)$ be the reflexive and transitive closure of $\text{dag}(𝒜)$.

For $C\in \text{SCC}(𝒜)$, we define $ℒ(𝒜|C)$ as the language of words such that $w\in ℒ(𝒜|C)$ if, starting from some state in $C$, the automaton can read the whole word $w$ without leaving $C$. More precisely, it is the language of words $w_1\mathrm{\dots }{w}_n$ such that there are $q^0\mathrm{\dots }{q}^n\in C$ satisfying, for all $i$, $\delta (q^{i-1},w_i)=q^i$.

Now, consider two DFA $𝒜$ and $ℬ$. We say that a path $\pi =C_1\mathrm{\dots }{C}_n$ in $\text{dag}(𝒜)$ is covered by a path ${\pi }^{\prime }=D_1\mathrm{\dots }{D}_m$ in ${\text{dag}}^{\ast }(ℬ)$ if and only if $n=m$ and for every $1\le i\le n$ we have $ℒ(𝒜|C_i)\subseteq ℒ(ℬ|D_i)$. Checking whether a path is covered by a path can be decided in polynomial time [3, Lemma 4.4].

It has been shown in [3, Theorem 4.1] that $ℒ(𝒜){\subseteq }_{\text{ed}}^{\mathrm{\infty }}ℒ(ℬ)$ if and only if every path in $\text{dag}(𝒜)$ is covered by some path in ${\text{dag}}^{\ast }(ℬ)$ (the result from [3, Theorem 4.1] holds even for non-deterministic finite automata). Furthermore, due to [3, Theorem 4.1], we have $ℒ(𝒜){\subseteq }_{\text{ed}}^{\mathrm{\infty }}ℒ(ℬ)$ if and only if $ℒ(𝒜){\subseteq }_{\text{ed}}^kℒ(ℬ)$ for any $k\ge (|𝒜|+1)\cdot (|ℬ|+1)$.

Note that a DFA $𝒜$ may contain a rejecting sink state, which has no counterpart in $\text{dag}(𝒜)$. Furthermore, some states of $𝒜$ may not belong to any SCC (for example, the initial state of $𝒜$ if it is not reachable from any other state). In particular, if $\text{dag}(𝒜)$ has no root, i.e., the node from which all other nodes are reachable, then the initial state of $𝒜$ does not belong to any SCC. We will use this fact further on.

Consider a program that receives some data, computes something and sends the response, after which it can start over or terminate. Traces of such a program can be represented over the alphabet $\{r,c,s,t\}$ as depicted in Figure 1 (left).

Observe that $𝚜$ is a sink state; the sink state is present in all automata, but we do not draw it or discuss it for better clarity.

Assume that we want to learn the (target) automaton ${𝒜}^T$ depicted in Figure 1 (left) from noisy data, which contains as a positive example the word $rcsrcsrcs$ instead of $rcsrcsrcst$. It is possible that the learning procedure produces the automaton that is depicted in Figure 1 (right).

Observe that the automaton ${𝒜}^L$ from Figure 1 (right) is minimal in the classical sense, and also minimal w.r.t. hyper-minimization [10, 18] as there is no language that differ from the language of ${𝒜}^L$ on some finite set of words whose automaton has less states.

Observe that ${𝒜}^T{\equiv }_{\text{ed}}^1{𝒜}^L$. Clearly $ℒ({𝒜}^T){\subseteq }_{\text{ed}}^1ℒ({𝒜}^L)$ because $ℒ({𝒜}^T)\subseteq ℒ({𝒜}^L)$. To see $ℒ({𝒜}^L){\subseteq }_{\text{ed}}^1ℒ({𝒜}^T)$, observe that any word accepted by ${𝒜}^L$ but not by ${𝒜}^T$ is of the form ${(rcs)}^{4k+3}$ for some $k$, and it can be modified to be accepted by ${𝒜}^T$ by appending $t$. In this case, the automaton ${𝒜}^L$ is the minimal automaton equivalent to ${𝒜}^T$ up to edit distance $1$. Therefore, minimizing ${𝒜}^T$ allows to overcome the problem introduced by the noised data.

Now consider an automaton ${𝒜}^K$ which is a copy of ${𝒜}^L$, but with the state $q_2$ accepting. In this case, this automaton accepts the word $rc$, which cannot be transformed into any word accepted by ${𝒜}^T$ with edit distance $1$. Therefore, ${𝒜}^T{\not\equiv }_{\text{ed}}^1{𝒜}^K$. It can be checked, however, that ${𝒜}^T{\equiv }_{\text{ed}}^2{𝒜}^K$ and ${𝒜}^T{\equiv }_{\text{ed}}^{\mathrm{\infty }}{𝒜}^K$.

We first show that the MIN-BED problem is in ${\mathrm{\Sigma }}_2^P$. Recall that a language $P$ is in ${\mathrm{\Sigma }}_2^P$ if there is a language $P^{\prime }$ in coNP such that $x\in P$ if and only if there exists $y$ of polynomial size in $|x|$ such that $(x,y)\in P^{\prime }$.

Given two DFA $𝒜,ℬ$, checking whether $𝒜{\equiv }_{\text{ed}}^{\mathrm{\infty }}ℬ$ amounts to checking two inclusions: $ℒ(𝒜){\subseteq }_{\text{ed}}^{\mathrm{\infty }}ℒ(ℬ)$ and $ℒ(ℬ){\subseteq }_{\text{ed}}^{\mathrm{\infty }}ℒ(𝒜)$. Since the inclusions can be checked in coNP [3, Theorem 5.2], checking equivalence can also be done in coNP.

To solve MIN-BED for an instance $(𝒜,m)$, assume that (otherwise the answer is yes with $ℬ=𝒜$). Then, non-deterministically pick a DFA $ℬ$ of the size at most $m$ and return whether $𝒜{\equiv }_{\text{ed}}^{\mathrm{\infty }}ℬ$. It follows that the problem is in ${\mathrm{\Sigma }}_2^P$.

Recall the condition for checking containment modulo a bounded edit distance (Section 2.2), which involves checking coverage of all paths in $\text{dag}(𝒜)$. As we strive for better complexity results, we will restrict the class of DFA to those with polynomially many paths in dag. Later on, we consider DFA $𝒜$ such that $\text{dag}(𝒜)$ has bounded depth.

It has been shown in [3] that deciding language containment up to a bounded edit distance is coNP-complete. This does not directly imply that the MIN-BED problem or even deciding the equivalence up to a bounded edit distance is coNP-hard. For instance the language inclusion on languages represented by deterministic pushdown automata (DPDA) is undecidable [12], while the equivalence problem for DPDA is decidable [25]. Still, we show coNP-hardness of MIN-BED by adapting the reduction from [3].

We now restrict the class of DFA to those with polynomially many paths in dag and show an improved complexity results.

Notice that we do not require $\text{dag}(ℬ)$ to have polynomially many paths.

We now focus on the case of DFA $𝒜$ such that $𝒜$ is non-trivial and $\text{SCC}(𝒜)$ is a singleton $\{C\}$. This means that $𝒜$ may contain states that are not in any SCC and the sink $\{s_r\}$.

For DFA of SCC-depth 3, the MIN-BED problem is NP-hard. We present a complementary result that for DFA of SCC-depth at most 2, minimization modulo a bounded edit distance can be computed in polynomial time.

Recall the example in Figure 2: the main idea there is to have many SCCs in the “middle layer” of the automaton – SCCs that have predecessors and successors in the corresponding DAG. Because of that, the states (being single-state maximal SCCs) $s_1$ and $s_2$, that have the same language ($ℒ(e^{\ast })$), cannot be merged. However, for SCCs with no successors, it holds that they can be merged if they have the same language – and the same holds for SCCs with no predecessors. We build on this idea to solve the minimization modulo a bounded edit distance for DFA of SCC-depth 2, where each SCC has either no successors or no predecessors. One needs to be careful though; even if the input automaton has the SCC depth 2, it might happen that the minimal equivalent one has SCC depth 3, as we will show later on (Example 13).

For a path $\pi$, by $\pi [i]$ we denote the $i$th element of $\pi$ (starting from 1). We say that a path $\pi$ is weakly covered by ${\pi }^{\prime }$ if there is a sequence $i_1\le \mathrm{\cdots }\le i_k$ such that ${\pi }^{\prime }[i_1]\mathrm{\dots }{\pi }^{\prime }[i_k]$ covers $\pi$. For example, the path $CCC$ is weakly covered by $C{C}^{\prime }$ because of the sequence $1,1,1$.

Let $𝒜$ be a DFA of SCC-depth at most $2$. A subset $E$ of paths of $\text{dag}(𝒜)$ is:

• $\mathrm{■}$

  noncollapsible if for each path $C,D$ in $\text{dag}(𝒜)$ of length $2$ we have $ℒ(𝒜|C)⊈ℒ(𝒜|D)$ and $ℒ(𝒜|C)⊉ℒ(𝒜|D)$.

• $\mathrm{■}$

  irredundant if there is no proper subset $E^{\prime }$ of $E$ such that every path in $E$ is weakly covered by a path in $E^{\prime }$.

• $\mathrm{■}$

  a minimal cover if it is noncollapsible, irredundant, and paths from $E$ weakly cover all paths in $\text{dag}(𝒜)$.

Let $𝒜,ℬ$ be DFA. A path $C_1,\mathrm{\dots },C_k$ is tightly covered by a path $D_1,\mathrm{\dots },D_k$ if for every $i$ we have $ℒ(𝒜|C_i)=ℒ(ℬ|D_i)$.

We show that if $𝒜,ℬ$ are equivalent modulo a bounded edit distance, then every path in a minimal cover of paths in $\text{dag}(𝒜)$ is tightly covered by some path from ${\text{dag}}^{\ast }(ℬ)$. The intuition is that each paths in the minimal cover defines a “maximal” possible language, that has to be covered by some path of ${\text{dag}}^{\ast }(ℬ)$, which in turn has to be covered by some path of ${\text{dag}}^{\ast }(𝒜)$. The language maximality then guarantees the equality of the languages.

Now, we construct a DFA equivalent modulo a bounded edit distance to $𝒜$ with the minimal number of states. To do so, we first compute a minimal cover of paths in $\text{dag}(𝒜)$. This is done iteratively in polynomial time, by starting from all the noncollapsible paths of $\text{dag}(𝒜)$, and removing paths that can be covered by other paths. Then, we split the SCCs of the minimal cover into two categories: starters, which are the first SCCs of the paths (including paths of length 1), and finishers, which are the second SCCs of the paths of lengths 2. We remove duplicates in each category, minimize each SCC, and construct the target automaton $\widetilde{𝒜}$ that consists of a disjoint union of all the remaining starters and finishers.

For each path of length 2 in the minimal cover, we find a corresponding starter and a finisher, and connect all the states of the starter to all the states of the finisher (connecting any state from the starter to any state of the finisher would also work). This may require extending the alphabet with additional letters; we need at most $|P|$ such letters.

If it is possible to pick a state of some starter as an initial state, then we do; otherwise we add one additional starting state. We connect the initial state to all the starters.

We add transitions from the initial state to all the starters (possibly using another letter). The detailed algorithm is presented in Algorithm 1. A quick check shows that it works in polynomial time.

The DFA min-depth-2($𝒜$) is constructed in such a way that $\text{dag}(\text{min-depth-2(}𝒜\text{)})$ consists of nodes from $L_1\cup L_2$ with edges from $C$ to $D$ if and only if $C\in L_1^{\prime },D\in L_2^{\prime }$ and the path $C,D$ is tightly covered by some path from $P$.

The automaton min-depth-2($𝒜$) is not unique as the transitions between different SCCs may use different letters; the choice of letters is irrelevant as it can be fixed with a bounded edit distance.

Hamming distance calculates the minimum number of single-character substitutions required to transform one word into another, assuming both words are of the same length. In contrast, edit distance also allows insertions and deletions of characters, making it applicable to words of different lengths. Hamming distance could be more advantageous in scenarios where fixed-length words are present, or situations where insertions and deletions are unrealistic, like comparing fixed-length DNA sequences. However, its limitation to equal-length words makes it less suitable than edit distance in cases where inputs may vary in length or include additional elements.

We now briefly discuss how our results could be adapted for the Hamming distance metrics. For fixed $k\in \mathbb{N}$, the PSpace-hardness result from Theorem 15 can be easily adapted to the Hamming distance. For the bounded Hamming distance case, i.e, $k=\mathrm{\infty }$, the result would be different from those obtained for equivalence modulo a bounded edit distance. First, our results for a bounded edit distance rely on the condition from [3, Theorem 4.1] presented in Section 2.2 for DFA to be equivalent modulo a bounded edit distance. Up to our best knowledge, there is no counterpart of this condition for the Hamming distance. Second, due to Proposition 9, we have focused on non-universal DFA, for which a rejecting sink state is reachable from every state, as all universal DFA are equivalent modulo finite edit distance to a single-state DFA. Proposition 9 does not extend to language equivalence modulo a bounded Hamming distance. For example, the language consisting of words of even length is equivalent modulo a bounded edit distance to the language of all words, whereas it is not equivalent modulo a bounded Hamming distance. For these reasons, we leave the study of minimization modulo a bounded Hamming distance as future work.

While we have discussed symmetric similarity measure, in some applications only one-sided errors are allowed. For instance, in formal verification, abstraction methods reduce a given model size by constructing an over-approximation, which is verified against a specification. In such a case, there are no false positives, i.e., the answers that the specification is met are correct, while there may be false negatives due to over-approximation. Over-approximation should balance the size of the minimized model and the false-negatives rate. We can address it with similarity relations.

Consider the following relation: $ℒ{⪯}_{\text{ed}}^k{ℒ}^{\prime }$ if $ℒ\subseteq {ℒ}^{\prime }$ and ${ℒ}^{\prime }{\subseteq }_{\text{ed}}^kℒ$. For $k=\mathrm{\infty }$, this is a transitive relation. This leads to the following minimization problem: given a DFA $𝒜$, find a minimal $ℬ$ such that $ℒ(𝒜){⪯}_{\text{ed}}^{\mathrm{\infty }}ℒ(ℬ)$. This approach gives us a close over-approximation; an automaton that accepts all the words that $𝒜$ accepts and perhaps some additional words, but only if the additional words are close (w.r.t. the edit distance) to some accepted words.

Again, for fixed $k\in \mathbb{N}$, the PSpace-hardness result from Theorem 15 can be easily adapted to the asymmetric distance ${⪯}_{\text{ed}}^{\mathrm{\infty }}$. For $k=\mathrm{\infty }$, most results can be easily adapted to the asymmetric distance ${⪯}_{\text{ed}}^{\mathrm{\infty }}$: containment in ${\mathrm{\Sigma }}_2^P$ (Proposition 3), coNP-hardness (Theorem 4), NP-completeness (Theorem 8), triviality of minimization with unrachable sink state (Proposition 9), and minimization of a DFA being a single SCC with a sink (Theorem 10). However, minimization of DFA of SCC-depth $2$ does not extend easily to the asymmetric distance ${⪯}_{\text{ed}}^{\mathrm{\infty }}$.

While potentially useful in applications like formal verification, these asymmetric relations exhibit challenges such as counter-intuitive behaviour, and require further investigation into their properties and practical applications.