betaFeedback

WorksComputer Science

Towards A Parametrized Complexity of Determinization

Abstract

Given a nondeterministic finite automaton (NFA), we want to estimate the difficulty of finding an equivalent deterministic finite automaton (DFA). We demonstrate that computing the state complexity of an NFA within polynomial precision is \textsf{PSPACE}-hard, and furthermore the same holds for the complexity of the subset construction, Brzozowski's algorithm, or, indeed, any determinization algorithm which runs at least as fast. This result implies that making any a priori estimate of the running time of the major determinization algorithms is inherently hard. To circumvent this—in the spirit of parametrized complexity—we try to identify complexity measures which can guarantee efficient determinization. Our main idea rests on linking the complexity of the subset construction to transition monoids using the semigroup complexity. We show that the semigroup complexity by itself can be reasonably approximated for certain classes of NFAs, and then introduce subset complexity—a refinement of the semigroup complexity which has a tighter connection with the subset construction. In certain scenarios, the subset complexity can be approximated in polynomial time, making it potentially viable for more practical applications.

Introduction

The equivalence in expressivity between nondeterministic finite automata (NFAs) and deterministic finite automata (DFAs) was one of the first foundational results in the theory of finite automata. The original proof by Rabin and Scott [24] introduced the powerset construction, a general algorithm for converting an arbitrary NFA into an equivalent DFA. Despite its simplicity and pedagogical value, a major drawback of the powerset construction is that it yields a DFA with exactly 2n2^n states, where nn is the number of states in the original NFA. Unfortunately, the equivalent DFA produced by the powerset construction is in general not minimal and can, thus, often be reduced using standard finite minimization techniques [14]. Moreover, in certain pathological cases, the minimal DFA Adet\mathcal{A}_{\mathrm{det}} is exponentially smaller than the DFA Apow\mathcal{A}_{\mathrm{pow}} returned by the powerset construction, meaning the algorithm may perform an exponential amount of unnecessary output. A trivial example illustrates this phenomenon: consider an arbitrary nn-state NFA with no final states. In this case, the minimal DFA is always the 1-state automaton accepting the empty language. Furthermore, this exponential blow-up is also unavoidable in the worst case—Moore [21] demonstrated the existence of an nn-state NFA, known as Moore’s automaton, for which the minimal equivalent DFA requires exactly 2n2^n states, i.e., the exponentially large DFA produced by the powerset construction is already minimal. Subsequent research identified even simpler classes of NFAs for which the powerset construction yields the minimal DFA [4].

Besides the powerset construction, several alternative determinization algorithms have been proposed, such as the classic subset construction [1], Brzozowski’s algorithm [5], width-based determinization [18] and many others [27]. However, there has been only little work analyzing the actual performance of determinization algorithms: some theoretical analysis of the complexity of the subset construction on homogeneous automata has been presented in [8], the average-case complexity of Brzozowski’s algorithm was analyzed in [10], and some more empirical approaches were used in [27]. This lack of attention can be explained by the seeming detachment of determinization complexity from any classical complexity metrics defined on the NFAs,1 such as, for example, the state complexity ∣Adet∣|\mathcal{A}_{\mathrm{det}}|: it is known that even NFAs with a state complexity of exactly 1 can be notoriously difficult to determinize [12]. Moreover, depending on the choice of the determinization algorithm for a specific NFA, the performance could vary significantly, hence it is difficult to come up with a general measure for it.

Despite these shortcomings, determinization remains one of the key transformations for finite automata, since many language operations such as complement, equivalence, and inclusion testing can be realized on DFAs in polynomial time, while in general, have worst-case exponential time complexity on NFAs [29]. As we see it, a complete theory for finite automata ought to answer the following questions: when can the transformation of an NFA into an equivalent DFA be done in polynomial time, and what is the best algorithm to achieve that? A satisfactory answer to this question could be an analog of parametrized complexity for NFA determinization. Unfortunately, due to all the difficulties mentioned above, there seems to be no obvious way to approach this problem, which is the primary motivation for this work.

In the first part of the article (Sections 3–5) we develop a theoretical framework to analyze the complexity of determinization. Specifically, in Section 3 we discuss the systematic difficulties behind classifying NFAs with respect to the time complexity of determinization, and show why many classical metrics, such as the state complexity, are destined to fail. In Section 4 we introduce a natural way (denoted with relation ≥\ge) to compare algorithms with worst-case exponential time complexities: a determinization algorithm improves on another one, if it is at least as fast on every possible input. These ideas culminate in Section 5, where we show that the running time of any determinization algorithm ALG\mathrm{ALG} which is at least as fast as the subset construction (or at least as fast as Brzozowski’s algorithm) is inherently unpredictable, as summarized below:

ALG ≥ Subsetconstruction(Theorem 21)orALG ≥ Brzozowski’salgorithm(Theorem 22)⟹approximatingruntime of ALGis PSPACE-hard\mathrm{ALG}\ \ge\ \begin{gathered}\text{Subset}\\\text{construction}\\\text{(Theorem 21)}\end{gathered} \quad\text{or}\quad \mathrm{ALG}\ \ge\ \begin{gathered}\text{Brzozowski's}\\\text{algorithm}\\\text{(Theorem 22)}\end{gathered} \quad\Longrightarrow\quad \begin{gathered}\text{approximating}\\\text{runtime of ALG}\\\text{is PSPACE-hard}\end{gathered}

Furthermore, a weaker version of this statement holds even if the exact state complexity of the underlying NFA is known (Corollary 23).

In the second part of the article (Sections 6–8), we focus on the performance of the subset construction, since it remains the backbone of many modern determinization algorithms [27]. In particular, its time complexity can be naturally parametrized using the size of the produced DFA, the subset automaton ASS\mathcal{A}_{\mathrm{SS}}. In Section 6 we discuss the semigroup complexity—a known measure that naturally bounds the size of the subset automaton, and derive explicit bounds for some restricted subclasses of NFAs (specifically unary, permutation, commutative, and dense automata). Section 7 then further develops this approach by introducing the subset complexity: a new measure that refines the semigroup complexity, while still bounding the size of the subset automaton. This creates the following hierarchy of complexity measures for non-deterministic automata:

semigroupcomplexity(Section 6) ≥ subsetcomplexity(Section 7) ≥ subsetautomaton∣ASS∣ ≥ statecomplexity∣ADET∣\begin{gathered} \text{semigroup}\\ \text{complexity}\\ \text{(Section 6)} \end{gathered} \ \ge\ \begin{gathered} \text{subset}\\ \text{complexity}\\ \text{(Section 7)} \end{gathered} \ \ge\ \begin{gathered} \text{subset}\\ \text{automaton}\\ |\mathcal{A}_{\mathrm{SS}}| \end{gathered} \ \ge\ \begin{gathered} \text{state}\\ \text{complexity}\\ |\mathcal{A}_{\mathrm{DET}}| \end{gathered}

Finally, Section 8 discusses computational aspects of the subset complexity, specifically scenarios where it can be bounded by a polynomial—something of relevance for determinization in practice.

This article forms an extended version of results partially presented in [2] and [3].

Background and Definitions

We start the technical portion of the paper by briefly reciting necessary definitions concerning finite automata; for a more comprehensive introduction, we refer to [14]. An alphabet Σ\Sigma is a finite, non-empty set of symbols. With Σ∗\Sigma^*, we denote the set of all finite strings, also called words, over Σ\Sigma. The symbol ε∈Σ∗\varepsilon\in\Sigma^* denotes the empty word, i.e., the unique word of length 0. Two words yy and xx are placed adjacent to each other, e.g., xyxy denotes the concatenation of those words.

Definition 1. A finite automaton (FA) A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma,Q,I,F,\delta) is a quintuple where Σ\Sigma is an alphabet, QQ is a finite set of states, I⊆QI \subseteq Q is a set of the initial states, F⊆QF \subseteq Q is a set of accepting states and δ⊆Q×(Σ∪{ε})×Q\delta\subseteq Q \times(\Sigma\cup\{\varepsilon\}) \times Q is a finite multiset of labeled transitions between states.

Note that a transition labeled with ε\varepsilon can be performed at any point. The size of a finite automaton A=(Σ,Q,I,F,δ)A = (\Sigma, Q, I, F, \delta) is its number of states ∣Q∣|Q|; we use the cardinality operator ∣A∣|A| to denote the size.

For the remainder of this article, we assume that all automata are ε\varepsilon-free, i.e., contain no ε\varepsilon transitions. This assumption is without loss of generality as there exist efficient procedures for removing ε\varepsilon-transitions [1].

Definition 2. A path π=q0→w1q1→w2⋯→wNqN\pi= q_0 \xrightarrow{w_1} q_1 \xrightarrow{w_2} \cdots\xrightarrow{w_N} q_N in an FA AA is a labeled sequence of states, where each label wn∈Σ∪{ε}w_n \in\Sigma\cup\{\varepsilon\} is a symbol from the alphabet, and each qn∈Qq_n \in Q is a state in AA, such that for all nn we have (qn−1,wn,qn)∈δ(q_{n-1}, w_n, q_n) \in\delta. We will refer to the concatenation of symbols along the path w1⋯wNw_1 \cdots w_N as the path’s yield.

We say that a word w∈Σ∗w \in\Sigma^* is recognized by the FA AA if there exists a path in AA from some initial state qI∈Iq_I \in I to some final state qF∈Fq_F \in F with yield ww. Moreover, we denote with L(A)⊆Σ∗\mathcal{L}(A) \subseteq\Sigma^* the language (set of all words) recognized by AA. Two FAs AA and A′A' are called equivalent if they accept the same language, i.e., if L(A)=L(A′)\mathcal{L}(A) = \mathcal{L}(A'). Given two languages L\mathcal{L} and L′\mathcal{L}' we define their concatenation

LL′={xy∣x∈L, y∈L′}(1)\mathcal{L}\mathcal{L}' = \{xy \mid x \in\mathcal{L},\ y \in\mathcal{L}'\} \tag*{(1)}

as the language accepting all concatenations of word pairs in them. In case L′={w}\mathcal{L}' = \{w\} is a singleton, we overload the notation and simply write Lw\mathcal{L}w for brevity.

Definition 3. A state q∈Qq \in Q is called accessible if there exists a path from II to qq, and co-accessible if there exists a path from qq to FF. An automaton where all states are both accessible and co-accessible is called trim.

Similarly to ε\varepsilon-transitions, we assume that all automata we deal with are trim, since removing inaccessible states can be trivially done using a depth-first search in linear time.

Definition 4. The reverse FA of an automaton AA, marked by ARA^R, is an FA obtained by reversing the direction of all transitions in AA and swapping the initial and final states.

We denote the subroutine transforming any FA AA into its reverse ARA^R as Reverse, and note that L(AR)=L(A)R\mathcal{L}(A^R) = \mathcal{L}(A)^R, i.e., the set of all reversed words from L(A)\mathcal{L}(A).

Definition 5. An FA A=(Σ,Q,I,F,δ)A = (\Sigma, Q, I, F, \delta) is deterministic if and only if the initial state is unique, i.e., ∣I∣=1|I| = 1, and for every (q,w)∈Q×Σ(q, w) \in Q \times\Sigma there is exactly one q′∈Qq' \in Q such that (q,w,q′)∈δ(q, w, q') \in\delta, i.e., the relation corresponds to a total function of type Q×Σ→QQ \times\Sigma\to Q. An FA that is not deterministic is called nondeterministic and an FA whose reverse ARA^R is deterministic is called co-deterministic.

As a shorthand, for any w∈Σ∗w \in\Sigma^*, we write δ(q,w)=δ(⋯δ(δ(q,w1),w2)⋯ ,wN)\delta(q,w) = \delta(\cdots\delta(\delta(q,w_1),w_2)\cdots,w_N) to denote an iterative application of the transition function to the word w=w1⋯wNw = w_1 \cdots w_N. Typically, DFAs are both easier to implement and to use—many properties, e.g., language equivalence between FAs, are hard to decide for general NFAs, but can be decided for deterministic automata in polynomial time [12].

Powerset Construction

It is well-known that NFAs and DFAs recognize the same class of languages: this fact is typically proven using the powerset construction. We define a naive procedure PowerConstr which, given an arbitrary NFA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta), constructs an equivalent DFA Apow=(Σ,2Q,QI,Fpow,δpow)\mathcal{A}_{\mathrm{pow}} = (\Sigma, 2^Q, Q_I, F_{\mathrm{pow}}, \delta_{\mathrm{pow}}), known as the powerset automaton. Every state Q∈2QQ \in2^Q, also called the powerstate, satisfies Q⊆QQ \subseteq Q and all transitions between powerstates in δpow\delta_{\mathrm{pow}} satisfy the condition

Qi→wQj  ⟺  ∃qi∈Qi ∃qj∈Qj such that (qi,w,qj)∈δ.(2)Q_i \xrightarrow{w} Q_j \iff\exists q_i \in Q_i\ \exists q_j \in Q_j\ \text{such that}\ (q_i,w,q_j) \in\delta. \tag*{(2)}

Furthermore, QI=IQ_I = I is a powerstate containing all initial states of A\mathcal{A} and FpowF_{\mathrm{pow}} is a set of powerstates containing at least one state from the final states FF. By construction, Apow\mathcal{A}_{\mathrm{pow}} is a DFA with ∣Apow∣=2∣A∣|\mathcal{A}_{\mathrm{pow}}| = 2^{|\mathcal{A}|} and one can easily show that L(Apow)=L(A)\mathcal{L}(\mathcal{A}_{\mathrm{pow}}) = \mathcal{L}(\mathcal{A}).

More generally, transforming a nondeterministic automaton into an equivalent deterministic one is commonly referred to as determinization. Because the resulting DFA is not unique in general, we will slightly narrow down this definition and require valid determinization algorithms to produce the minimal equivalent DFA Adet\mathcal{A}_{\mathrm{det}} for each NFA A\mathcal{A} (sometimes this is referred to as canonization, and Adet\mathcal{A}_{\mathrm{det}} is always unique up to isomorphism [14]). Overall, this has little effect on the underlying complexity, since DFA minimization can be performed in quasi-linear time by means of Hopcroft’s minimization algorithm [13]. In particular, we can easily apply Hopcroft’s minimization algorithm (denote it by Minimize) to the output DFA Apow\mathcal{A}_{\mathrm{pow}} from PowerConstr, which yields a valid determinization algorithm:

Adet=Minimize(PowerConstr(A)).(3)\mathcal{A}_{\mathrm{det}} = \mathrm{Minimize}(\mathrm{PowerConstr}(\mathcal{A})). \tag*{(3)}

Definition 6. Given an FA A\mathcal{A}, we call the number of states in its minimal equivalent deterministic automaton Adet\mathcal{A}_{\mathrm{det}} its state complexity, usually denoted as ∣Adet∣|\mathcal{A}_{\mathrm{det}}|.

Subset Construction

In practice, the most commonly implemented building block for determinization algorithms is the so-called subset construction [1], a dynamic version of the powerset construction which only keeps track of accessible states from Apow\mathcal{A}_{\mathrm{pow}}; hence, the states and transitions in the DFA returned by the subset construction are always a subset of the states and transitions of Apow\mathcal{A}_{\mathrm{pow}}. Algorithm 1 provides the pseudocode for an example implementation of the subset construction and, analogously to the powerset construction, it can be coupled with Minimize to obtain a valid determinization algorithm:

Adet=Minimize(SubsetConstr(A)).(4)\mathcal{A}_{\mathrm{det}} = \mathrm{Minimize}(\mathrm{SubsetConstr}(\mathcal{A})). \tag*{(4)}

Note that this creates a slight ambiguity—the term subset construction may refer both to Algorithm 1 and the composed determinization algorithm in Eq. (4). To

Algorithm 1 (SubsetConstr)
Require: $\mathcal{A} = (\Sigma, Q, I, F, \delta)$
$Q_I \leftarrow \{q \mid q \in I\}$
$\mathcal{A}_{\mathrm{ss}} \leftarrow (\Sigma, Q_{\mathrm{ss}} := \varnothing, Q_I, F_{\mathrm{ss}} := \varnothing, \delta_{\mathrm{ss}} := \varnothing)$
push $Q_I$ on the stack
$Q_{\mathrm{ss}} \leftarrow \{Q_I\}$
while $|\mathrm{stack}| > 0$ do
  pop $Q$ from the stack
  for all $w \in \Sigma$ do
    $Q' \leftarrow \{q' \mid (q,w,q') \in \delta,\ q \in Q\}$
    $\delta_{\mathrm{ss}} \leftarrow \delta_{\mathrm{ss}} \cup \{Q \xrightarrow{w} Q'\}$
    if $Q' \notin Q_{\mathrm{ss}}$ then
      $Q_{\mathrm{ss}} \leftarrow Q_{\mathrm{ss}} \cup \{Q'\}$
      push $Q'$ on the stack
$F_{\mathrm{ss}} \leftarrow \{Q \in Q_{\mathrm{ss}} \mid Q \cap F \ne \varnothing\}$
return $\mathcal{A}_{\mathrm{ss}}$

distinguish the two, we will use the term SubsetConstr for Algorithm 1, and reserve the term subset construction for the composed algorithm. SubsetConstr roughly works as follows: given an input NFA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta), it explores all subsets of states accessible from the powerstate QIQ_I (composed of initial states II) by following the labeled transitions from δ\delta. Each newly found state Q⊆QQ \subseteq Q will be placed on the stack, and for every QQ on the stack, we search for all of its direct neighbors and place them on the stack and then remove QQ. This process is repeated iteratively until no new neighbors can be found, i.e., the stack becomes empty. Algebraically, this can be seen as multiplying the characteristic vector for the initial state QIQ_I with all possible sequences of transition matrices and terminating as soon as no new states can be produced. We will refer to the DFA Ass\mathcal{A}_{\mathrm{ss}} obtained by applying Algorithm 1 on A\mathcal{A} as the subset automaton.

Brzozowski's Algorithm

Algorithm 1 plays a key role in automata determinization far beyond the classical subset construction, as illustrated in the next result due to Brzozowski [5].

Theorem 7 (Brzozowski [5]). If an NFA A\mathcal{A} is trim and co-deterministic, then Algorithm 1 produces the minimal DFA Adet\mathcal{A}_{\mathrm{det}}.

Theorem 7 gave birth to a novel determinization algorithm based on Algorithm 1, which directly produces the minimal DFA given any trim NFA A\mathcal{A} as input. This algorithm is known as Brzozowski’s algorithm, defined as

ADET=SubsetConstr⁡(Reverse⁡(SubsetConstr⁡(Reverse⁡(A)))).(5)\mathcal{A}_{\mathrm{DET}} = \operatorname{SubsetConstr}(\operatorname{Reverse}(\operatorname{SubsetConstr}(\operatorname{Reverse}(\mathcal{A})))). \tag*{(5)}

Several other determinization algorithms based on Algorithm 1 exist, some examples can be found in [27]. Herewith, we wrap up our discussion of the algorithmic aspects of automata and move on to an alternative way of characterizing FAs through the algebraic approach using semigroups defined by the underlying transition matrices.

Transition Monoids

Definition 8. Consider an FA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta) and, for each w∈Σw \in\Sigma, define a binary relation T(w)T^{(w)} over QQ with (q,q′)∈T(w)⟺(q,w,q′)∈δ(q,q') \in T^{(w)} \Longleftrightarrow(q,w,q') \in\delta for all q,q′∈Qq,q' \in Q. A transition monoid S(A)S(\mathcal{A}) is a binary relation monoid over QQ generated by {T(w)∣w∈Σ}\{T^{(w)} \mid w \in\Sigma\} and closed under the relation composition operator ∘\circ with the identity relation id\mathrm{id}.

It is often more convenient to think of S(A)S(\mathcal{A}) as a monoid of ∣Q∣×∣Q∣|Q| \times|Q| matrices over the Boolean semifield B:=⟨{0,1},∨,∧,0,1⟩\mathbb{B} := \langle\{0,1\}, \lor, \land, 0, 1 \rangle closed under Boolean matrix multiplication with the identity element I\mathcal{I}, such that:

Ti,j(w)=1⟺(qi,qj)∈T(w).(6)T_{i,j}^{(w)} = 1 \quad\Longleftrightarrow\quad(q_i,q_j) \in T^{(w)}. \tag*{(6)}

Notice that the monoid S(A)S(\mathcal{A}) is, by construction, closely related to the regular language L(A)\mathcal{L}(\mathcal{A}).

Definition 9. A language L⊆Σ∗L \subseteq\Sigma^* is recognized by a monoid MM of binary relations over QQ if there exists a surjective morphism μ:Σ∗→M\mu: \Sigma^* \to M and a subset MF⊆MM_F \subseteq M, called an accepting subset, such that L=μ−1(MF)L = \mu^{-1}(M_F).

From the definition above it is immediately visible that S(A)S(\mathcal{A}) recognizes the language L(A)\mathcal{L}(\mathcal{A}). Indeed, if we view II and FF as Boolean vectors we can define the accepting subset as

SF:={M∈S(A)∣ITMF≠0}(7)S_F := \{M \in S(\mathcal{A}) \mid I^{\mathsf{T}} M F \ne0\} \tag*{(7)}

and a morphism μ\mu for an arbitrary word w=w1w2w3…wm∈Σ∗\boldsymbol{w} = w_1w_2w_3 \ldots w_m \in\Sigma^*

μ(w)=I⋅∏i=1mT(wi)∈S(A)(8)\mu(\boldsymbol{w}) = \mathcal{I} \cdot\prod_{i=1}^{m} T^{(w_i)} \in S(\mathcal{A}) \tag*{(8)}

with μ(ε)=I\mu(\varepsilon) = \mathcal{I}. As a consequence, the inverse μ−1(SF)\mu^{-1}(S_F) only contains words w∈Σ∗\boldsymbol{w} \in\Sigma^* that are a yield of at least one path from II to FF in A\mathcal{A}. The duality between automata and semigroups has been extensively studied; for a more detailed overview, we refer to [22].

Troubles with Determinization

As mentioned in § 1, the problem of converting an NFA into an equivalent DFA is difficult because the state complexity of many NFAs can be exponentially large. Two classical examples demonstrating this phenomenon are the nn-state Moore automaton [21] and the nn-state Meyer–Fischer automaton [20], both of which exhibit a state complexity of 2n2^n; see Figure 1.

An $n$-state Moore automaton $\mathcal{A}_{\mathrm{Moore}}$ and an $n$-state Meyer–Fischer automaton $\mathcal{A}_{\mathrm{MF}}$

Figure 1. An nn-state Moore automaton AMoore\mathcal{A}_{\mathrm{Moore}} (left) and an nn-state Meyer–Fischer automaton AMF\mathcal{A}_{\mathrm{MF}} (right). Both of them are nondeterministic with a state complexity of 2n2^n for every n≥2n \ge2.

Example 10. The blow-up occurring in a Meyer–Fischer automaton AMF\mathcal{A}_{\mathrm{MF}} has a particularly intuitive explanation. Let ∣w∣a|w|_a denote the number of times the symbol aa appears in a word w∈{a,b}∗w \in\{a,b\}^*. Then, the language accepted by an nn-state AMF\mathcal{A}_{\mathrm{MF}} can be described as

L(AMF)={xy∣x∈{ε}∪({a,b}∗b), y∈{a,b}∗ and ∣y∣a≡0(modn)}.(9)\mathcal{L}(\mathcal{A}_{\mathrm{MF}}) = \{xy \mid x \in\{\varepsilon\} \cup(\{a,b\}^*b),\ y \in\{a,b\}^* \text{ and } |y|_a \equiv0 \pmod{n}\}. \tag*{(9)}

For every word w∈L(AMF)w \in\mathcal{L}(\mathcal{A}_{\mathrm{MF}}), the nondeterministic Meyer–Fischer automaton guesses a prefix that ends with bb (or is empty), such that the number of symbols aa in the remaining suffix is a multiple of nn. To accomplish that, any deterministic counterpart of AMF\mathcal{A}_{\mathrm{MF}} needs to keep track of all parities modulo nn for all occurrences of bb in ww, i.e., exactly 2n2^n possible options.

This is enough to conclude that there cannot exist an efficient (i.e., polynomial-time in the size of the NFA) procedure for converting NFAs into minimal DFAs. Nevertheless, it is worth emphasizing that not all NFAs will exhibit exponential blow-up, since many classes of NFAs—the most naive example being automata with no accepting states—can be converted into an equivalent DFA quite efficiently [18]. It is natural to raise the following question:

How should one quantify the complexity of NFA determinization?

Before we attempt to answer the question, we first need to formulate the mathematical principles that the desired measure should satisfy. To keep it concise and sufficiently ambiguous, we will state them in terms of natural language only:

  1. The complexity measure corresponds directly to the determinization difficulty of the underlying automaton.

  2. The complexity measure is algorithmically feasible to compute or estimate.

Due to the famous Myhill–Nerode theorem [14], the minimal deterministic automaton Adet\mathcal{A}_{\mathrm{det}} is unique up to isomorphism; hence the most straightforward attempt to assess the complexity of determinization is to consider the state complexity ∣Adet∣|\mathcal{A}_{\mathrm{det}}|. Unfortunately, this approach immediately clashes with both of our principles. To illustrate the first issue, let us consider the following 1-state deterministic automaton

AUNIV:=({a,b},{q},{q},{q},{(q,a,q),(q,b,q)}),(10)\mathcal{A}_{\mathrm{UNIV}} := (\{a,b\}, \{q\}, \{q\}, \{q\}, \{(q,a,q),(q,b,q)\}), \tag*{(10)}

which is minimal and accepts the universal language L(AUNIV)={a,b}∗\mathcal{L}(\mathcal{A}_{\mathrm{UNIV}}) = \{a,b\}^{*}, i.e., all words over the binary alphabet Σ={a,b}\Sigma= \{a,b\}.

Theorem 11 (NFA Universality [12]). Given an nn-state NFA A\mathcal{A}, deciding whether L(A)=L(AUNIV)\mathcal{L}(\mathcal{A}) = \mathcal{L}(\mathcal{A}_{\mathrm{UNIV}}) is PSPACE-complete.

Theorem 11 shows that determinization becomes intractable even when the state complexity of the underlying NFA is exactly 1, since any determinization procedure can be modified to decide universality. In particular, this implies that there does not exist a polynomial-time fixed-parameter tractable (FPT) determinization algorithm parametrized by state complexity ∣ADET∣|A_{\mathrm{DET}}|, and hence the complexity of NFA determinization is not related to the underlying state complexity.

We continue our journey by examining how (ii) relates to the state complexity. First, we define what a feasible estimate or approximation means in our context. Let F\mathcal{F} be any metric, which associates a natural number with every possible FA (for example F\mathcal{F} could count the states, i.e., F(A)=∣A∣\mathcal{F}(\mathcal{A}) = |\mathcal{A}|).

Definition 12. Let A\mathcal{A} be an arbitrary NFA and let f:N→Nf : \mathbb{N} \to\mathbb{N} be some function satisfying f(i)≥if(i) \ge i for all i∈Ni \in\mathbb{N}. We say that m^\hat{m} is an ff-approximation of metric F\mathcal{F} on A\mathcal{A} if

F(A)≤m^≤f(F(A)+∣A∣),(11)\mathcal{F}(\mathcal{A}) \le\hat{m} \le f(\mathcal{F}(\mathcal{A}) + |\mathcal{A}|), \tag*{(11)}

i.e., m^\hat{m} is an upper bound with slackness specified by ff.

Below we focus on the particular choice for the metric—the state complexity, i.e., F(A)=∣ADET∣\mathcal{F}(\mathcal{A}) = |\mathcal{A}_{\mathrm{DET}}|. Now we are ready to show that the state complexity does not allow for any reasonable approximation scheme by proving the following result.

Proposition 13. For any polynomial pp, it is PSPACE-hard to compute a pp-approximation to the state complexity.

Proof. To show PSPACE-hardness, we construct a polynomial reduction from the NFA universality problem. Let A\mathcal{A} be an arbitrary NFA and let n=∣A∣n = |\mathcal{A}|. Further, assume that there exists an algorithm that, given any NFA, produces a pp-approximation to its state complexity. We show that we could use such an algorithm to decide whether A\mathcal{A} accepts the universal language, which is PSPACE-hard by Theorem 11.

Without loss of generality, we assume that Σ={a,b}\Sigma= \{a,b\}. Next, we construct an automaton A′\mathcal{A}' over the alphabet Σ′={a,b,#}\Sigma' = \{a,b,\#\} with 2(n+1)2(n+1) states using a copy of A\mathcal{A}, a copy of AMOORE\mathcal{A}_{\mathrm{MOORE}} and two copies of AUNIV\mathcal{A}_{\mathrm{UNIV}} as shown in Figure 2. Specifically, A′\mathcal{A}' is the union of the following two NFAs:

Construction for automaton $\mathcal{A}'$

Figure 2. Construction for automaton A′\mathcal{A}' consisting of a union of two nondeterministic automata: the upper one is a connection of Auniv\mathcal{A}_{\mathrm{univ}} and Amoore\mathcal{A}_{\mathrm{moore}} using symbol #\#, and the lower one is the connection of A\mathcal{A} and Auniv\mathcal{A}_{\mathrm{univ}} using symbol #\#. In both cases the final states of the first automaton are connected to the initial states of the second one, with the corresponding initial/final labels dropped.

  1. We construct the first automaton as follows. Let Auniv\mathcal{A}_{\mathrm{univ}} be the 1-state minimal DFA that accepts Σ∗\Sigma^*, and let Amoore\mathcal{A}_{\mathrm{moore}} be the nn-state Moore automaton. Then, concatenate Auniv\mathcal{A}_{\mathrm{univ}} to Amoore\mathcal{A}_{\mathrm{moore}} by adding a #\#-labeled transition from the unique state in Auniv\mathcal{A}_{\mathrm{univ}} to the initial state of Amoore\mathcal{A}_{\mathrm{moore}}. Then, the initial state of Amoore\mathcal{A}_{\mathrm{moore}} no longer serves as an initial state, and the single state in Auniv\mathcal{A}_{\mathrm{univ}} no longer serves as a final state.

  1. We construct the second automaton as follows. Let Auniv\mathcal{A}_{\mathrm{univ}} be another copy of the 1-state minimal DFA that accepts Σ∗\Sigma^*. Then, concatenate A\mathcal{A} to Auniv\mathcal{A}_{\mathrm{univ}} by adding a #\#-labeled transition from all final states in A\mathcal{A} to the initial state of Auniv\mathcal{A}_{\mathrm{univ}}. The unique state in Auniv\mathcal{A}_{\mathrm{univ}} no longer serves as an initial state, and A\mathcal{A} no longer has any final states.

Clearly, the first automaton accepts the language Σ∗#L(Amoore)\Sigma^*\#\mathcal{L}(\mathcal{A}_{\mathrm{moore}}) while the second accepts the language L(A)#Σ∗\mathcal{L}(\mathcal{A})\#\Sigma^*. Thus, A′\mathcal{A}' accepts (Σ∗#L(Amoore))∪(L(A)#Σ∗)(\Sigma^*\#\mathcal{L}(\mathcal{A}_{\mathrm{moore}})) \cup(\mathcal{L}(\mathcal{A})\#\Sigma^*). On the one hand, if A\mathcal{A} is universal, then L(A)=Σ∗\mathcal{L}(\mathcal{A}) = \Sigma^*, and the union of these languages is precisely Σ∗#Σ∗\Sigma^*\#\Sigma^*. Consequently, the state complexity of A′\mathcal{A}' is 3. On the other hand, if L(A)\mathcal{L}(\mathcal{A}) is not universal, then there exists a word x∈{a,b}∗x \in\{a,b\}^* such that x∉L(A)x \notin\mathcal{L}(\mathcal{A}), meaning that

x#L(Amoore)⊆L(A′)and{x#y∣y∈L(Amoore)}c∩L(A′)=∅.(12)x\#\mathcal{L}(\mathcal{A}_{\mathrm{moore}}) \subseteq\mathcal{L}(\mathcal{A}') \quad\text{and} \quad\{x\#y \mid y \in\mathcal{L}(\mathcal{A}_{\mathrm{moore}})\}^{c} \cap\mathcal{L}(\mathcal{A}') = \varnothing. \tag*{(12)}

Consider the minimal deterministic automaton for A′\mathcal{A}', which we denote with Adet′\mathcal{A}'_{\mathrm{det}}. Let qq be the state in Adet′\mathcal{A}'_{\mathrm{det}} to which the path π\pi with the yield x#x\# leads. Now, observe that the right language of qq is L(Amoore)\mathcal{L}(\mathcal{A}_{\mathrm{moore}}). Because L(Amoore)\mathcal{L}(\mathcal{A}_{\mathrm{moore}}) has a state complexity nn, the state complexity of Adet′\mathcal{A}'_{\mathrm{det}} is at least 2n2^n. Thus, depending on whether A\mathcal{A} is universal or not, the state complexity of A′A' will be either 3 or at least 2n2^n. Hence, any pp-approximation m^\hat{m} to the state complexity of A′A' satisfies

m^≤p(3+∣A′∣)=p(2n+5)(13)\hat{m} \le p(3 + |A'|) = p(2n + 5) \tag*{(13)}

in the former case and m^≥2n\hat{m} \ge2^n in the latter; since p(2n+5)<2np(2n + 5) < 2^n for all sufficiently large nn, any algorithm producing a pp-approximation for the state complexity of A′A' would necessarily decide the universality of AA.

A variety of alternative analytical measures for automata complexity have been introduced over time, with most notable ones being listed in [6]. A promising approach was presented in [18], which describes a novel determinization algorithm parametrized by the width of the NFA, but unfortunately it is superexponential in the worst case. More generally, there seems to be little connection between the complexity of determinization algorithms and any of the known complexity measures for NFAs, perhaps with the exception of the semigroup complexity, which we will discuss more in § 6. Hence—following the spirit of this article—we instead propose a more algorithmic approach to tackling this problem.

The Algorithmic Landscape

It seems that our desired measure of determinization complexity should be tied to the underlying determinization algorithms. Ideally, we would want to find an optimal determinization algorithm and then link some complexity measure to its running time. However, a variety of different determinization algorithms exist and, as alluded to in the previous section, all of them necessarily have a worst-case exponential runtime. Hence, to achieve our goal, we need to start by answering the following question:

How should one compare exponential-time determinization algorithms?

Space Complexity

Since worst-case time complexity cannot be used as a sensible measure, a different metric to consider is the space complexity. Although this question does not seem to have appeared in the literature, an observation made by Stefan Kiefer in [15] provides a sketch of a general NFA determinization algorithm using only polynomial space (here we rely on the classical definition where the underlying Turing machine has separate working and output tapes, allowing for exponentially large outputs). Below we present a slightly more formal statement of this idea.

Theorem 14 (Polynomial Space [15]). There exists a determinization algorithm that transforms any nn-state NFA AA into a minimal equivalent DFA AdetA_{\mathrm{det}} with space complexity O(n2)O(n^2).

Proof. The proof of this result consists essentially of two main components: the construction of an oracle for the powerset automaton using only polynomial space and the algorithm from [9] capable of performing deterministic automata minimization in NL.

Given an NFA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta), the oracle provides access to the adjacency matrices of the powerset automaton Apow\mathcal{A}_{\mathrm{pow}} by receiving a query and returning a binary response. A query consists of a tuple of powerstates Qi,Qj∈P(Q)Q_i, Q_j \in\mathcal{P}(Q) and a symbol w∈Σw \in\Sigma, and returns 1 if transition Qi→wQjQ_i \xrightarrow{w} Q_j exists in Apow\mathcal{A}_{\mathrm{pow}}, and 0 otherwise. To check for Qi→wQjQ_i \xrightarrow{w} Q_j the oracle simply verifies whether

{q′∣(q,w,q′)∈δ, q∈Qi}∩Qj≠∅,(14)\{q' \mid(q,w,q') \in\delta,\ q \in Q_i\} \cap Q_j \ne\emptyset, \tag*{(14)}

which can be clearly done in O(n)O(n) space. Using the oracle as input to the minimization algorithm, we are able to communicate an automaton of exponential size using only polynomial space, and since the minimization algorithm is logarithmic in the input size, we conclude that A\mathcal{A} can be determinized on a nondeterministic Turing machine with linear space. By applying the famous Savitch’s theorem [25], we conclude the existence of a deterministic algorithm for NFA determinization requiring only O(n2)O(n^2) memory. □\square

While the existence of a worst-case space efficient determinization is reassuring, the construction above will always have exponential time complexity, making it highly impractical. Of course, we could attempt to improve that, but this only confirms that the space complexity alone cannot be the desired measure for our problem.

Comparing Algorithms

Our next attempt at answering the original question uses the following idea: instead of comparing the worst-case time complexities of algorithms, we compare the number of steps they use (given a canonical model of computation, i.e., RAM2^2)2 individually on every input NFA A\mathcal{A}.

Definition 15. We say that a determinization algorithm ALG1\mathrm{ALG}_1 improves another determinization algorithm ALG2\mathrm{ALG}_2, i.e., ALG1≥ALG2\mathrm{ALG}_1 \ge\mathrm{ALG}_2, if there exists a constant cc such that for any FA A\mathcal{A}, the number of steps required to compute Adet\mathcal{A}_{\mathrm{det}} using ALG1\mathrm{ALG}_1 is at most cc times larger than the number of steps required to compute Adet\mathcal{A}_{\mathrm{det}} using ALG2\mathrm{ALG}_2.

Definition 15 feels quite intuitive: an algorithm ALG1\mathrm{ALG}_1 is an improvement over ALG2\mathrm{ALG}_2, if and only if for any input automaton A\mathcal{A} it is at least as fast as ALG2\mathrm{ALG}_2 (measured up to a constant). We can easily deduce that the subset construction is an improvement over the powerset construction (as presented in § 2.1).

Unsurprisingly, the ordering ≥\ge is not total, as illustrated by the observation below; hence there is likely no optimal determinization algorithm.

Proposition 16. The subset construction and Brzozowski’s algorithm are incomparable under ≥\ge, i.e., neither of them is an improvement of the other.

Proof. We first show that the subset construction does not improve Brzozowski’s algorithm. Indeed, consider Moore’s automaton AMoore\mathcal{A}_{\mathrm{Moore}} with an explicit dead state q∅q_{\varnothing}, and mark all states as final. This does not affect Algorithm 1, which means that it still produces exponentially many states. In contrast, Brzozowski’s algorithm terminates immediately, since Reverse produces an automaton where all states are both initial and reachable, which then gets transformed into a DFA with a single state. To show the other direction, it is sufficient to exhibit some DFA A\mathcal{A} whose reverse AR\mathcal{A}^{R} has exponential state complexity. The existence of DFAs with this property is well-known, and later in Section 5 such a DFA is explicitly constructed (see the modified Meyer–Fischer automaton AMMF\mathcal{A}_{\mathrm{MMF}} in Figure 4 for more details).

Modified Meyer–Fischer automaton and its reverse

Figure 4. Modified Meyer–Fischer automaton AMMF\mathcal{A}_{\mathrm{MMF}} with an additional state pbp_b (left) satisfying L(AMMF)=L(AMF)\mathcal{L}(\mathcal{A}_{\mathrm{MMF}})=\mathcal{L}(\mathcal{A}_{\mathrm{MF}}) for AMF\mathcal{A}_{\mathrm{MF}} with t=n(k+1)t=n(k+1). Its reverse, (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R (right), is deterministic.

Remark 17. Note that the ordering ≥\geq behaves like a lattice. Indeed, for any two determinization algorithms Alg1\mathrm{Alg}_1 and Alg2\mathrm{Alg}_2 one can construct an algorithm Alg1∨Alg2\mathrm{Alg}_1 \vee\mathrm{Alg}_2 (i.e., join) which improves both of them: simply run both algorithms in parallel on the same input, and terminate as soon as one of them terminates. In a similar manner, one can construct the meet Alg1∧Alg2\mathrm{Alg}_1 \wedge\mathrm{Alg}_2 by always waiting for Alg1\mathrm{Alg}_1 and Alg2\mathrm{Alg}_2 to terminate.

Some previous work on determinization algorithms can be naturally expressed using our notion of improvement too: [27] presents five different determinization algorithms (note that the authors do not require the final DFA to be minimal, hence the algorithms ought to be coupled with Hopcroft’s Minimize), four of which are improvements of the subset construction.

Measuring Time Complexities

Let us briefly analyze the more granular time complexity of our determinization algorithms. First, consider the subset construction, and in particular Algorithm 1. As noted in [8], the number of steps it takes on A\mathcal{A} lies within O(∣Σ∣∣ASS∣∣A∣2)O(|\Sigma||\mathcal{A}_{\mathrm{SS}}||\mathcal{A}|^2). The addition of Minimize adds a logarithmic factor log⁡∣ASS∣\log|\mathcal{A}_{\mathrm{SS}}| (which can be bounded by ∣A∣|\mathcal{A}|), hence the final number of steps that the subset construction uses on A\mathcal{A} is within

O(∣Σ∣(∣ASS∣∣A∣2+∣ASS∣log⁡∣ASS∣))=O(∣Σ∣∣ASS∣∣A∣2).(15)O\left(|\Sigma|\left(|\mathcal{A}_{\mathrm{SS}}||\mathcal{A}|^2+|\mathcal{A}_{\mathrm{SS}}|\log|\mathcal{A}_{\mathrm{SS}}|\right)\right)=O\left(|\Sigma||\mathcal{A}_{\mathrm{SS}}||\mathcal{A}|^2\right). \tag*{(15)}

Brzozowski’s algorithm, as formulated in Section 2.3, effectively consists of two runs of the subset construction: in the first stage it produces the subset automaton for AR\mathcal{A}^{R} and, in the second stage, it produces another subset automaton, which, by Theorem 7, coincides with the minimal DFA ADET\mathcal{A}_{\mathrm{DET}}. Denote by ABR\mathcal{A}_{\mathrm{BR}} the subset automaton for AR\mathcal{A}^{R}, then the number of steps that Brzozowski’s algorithm uses on A\mathcal{A} lies within

O(∣Σ∣(∣A∣2∣ABR∣+∣ABR∣2∣ADET∣)).(16)O\left(|\Sigma|\left(|\mathcal{A}|^2|\mathcal{A}_{\mathrm{BR}}|+|\mathcal{A}_{\mathrm{BR}}|^2|\mathcal{A}_{\mathrm{DET}}|\right)\right). \tag*{(16)}

Definition 18. A determinization algorithm Alg\mathrm{Alg} is said to admit an ff-approximation if the metric F\mathcal{F} measuring the number of steps (i.e., time complexity) of Alg\mathrm{Alg} on a given input A\mathcal{A} admits an ff-approximation (as in Definition 12).

As observed earlier, the metric F\mathcal{F} from Definition 18 both for the subset construction and Brzozowski’s algorithm is dominated by the sizes of the corresponding subset automata. In what follows, we will attempt to better understand this metric and analyze its asymptotic behavior and computational aspects.

Time Complexity is Inapproximable

In this section we demonstrate that the performance of almost all efficient determinization algorithms is extremely difficult to estimate, with the key findings presented in Theorem 21 and Theorem 22 below. Before stating these results, we begin by making two straightforward observations about SubsetConstr.

Lemma 19. The NFA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta) is universal if and only if every state QQ in the subset automaton Ass\mathcal{A}_{\mathrm{ss}} (produced by Algorithm 1) contains a final state from A\mathcal{A}.

Proof. To show the left implication, observe that if all states generated by applying the subset construction contain a final state, then all states in Ass\mathcal{A}_{\mathrm{ss}} are accepting by design of Algorithm 1; hence, Ass\mathcal{A}_{\mathrm{ss}} accepts a universal language. To show the right implication, observe that if there does exist a state QQ generated by Algorithm 1 that does not contain a final state, then, since all states in Ass\mathcal{A}_{\mathrm{ss}} are accessible, there exists a path π\pi with yield yy from QIQ_I to QQ, which means that y∉L(Ass)y \notin L(\mathcal{A}_{\mathrm{ss}}).

Lemma 20. Let AMF=(Σ,QMF,I,F,δMF)\mathcal{A}_{\mathrm{MF}} = (\Sigma, Q_{\mathrm{MF}}, I, F, \delta_{\mathrm{MF}}) be an nn-state Meyer–Fischer automaton. Consider the powerstate Q1=QMFQ_1 = Q_{\mathrm{MF}} in its powerset automaton Apow\mathcal{A}_{\mathrm{pow}}. Then, all transitions leaving Q1Q_1 in Apow\mathcal{A}_{\mathrm{pow}} are self-loops.

Proof. Because being in the state Q1Q_1 corresponds to simultaneously being in all the states {q1,…,qn}\{q_1, \ldots, q_n\} of AMF\mathcal{A}_{\mathrm{MF}},3 the claim follows by observing that every state in AMF\mathcal{A}_{\mathrm{MF}} has at least one incoming transition with label aa and one with bb. Thus, once one lands in Q1Q_1, one will always transition back to all states in Q1Q_1.

Equipped with these lemmas, we are now ready to discuss the main results of this section.

Theorem 21. For any polynomial pp, it is PSPACE-hard to compute a pp-approximation for the subset construction or any improvement thereof.

Proof. We begin by showing the claim only for the subset construction. To show PSPACE-hardness of computing a pp-approximation, we again construct a polynomial reduction from the NFA universality problem. Assume that we have access to an algorithm which, given any A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta), computes a pp-approximation m^\hat{m} to the size of A\mathcal{A}’s subset automaton. Let n=∣A∣n = |\mathcal{A}| and let dd be the degree of the polynomial pp and without loss of generality assume that Σ={a,b}\Sigma= \{a,b\}. Given a fixed positive integer k∈Nk \in\mathbb{N} consider an n(k+1)n(k+1)-state Meyer–Fischer automaton AMF\mathcal{A}_{\mathrm{MF}} over Σ\Sigma. As with the n(k+1)n(k+1)-state Moore automaton, the n(k+1)n(k+1)-state Meyer–Fischer AMF\mathcal{A}_{\mathrm{MF}} has a state complexity of 2n(k+1)2^{n(k+1)}. In addition, the Meyer–Fischer automaton has a unique initial state p1p_1 which is also the unique accepting state, as shown in the top part of Figure 3.

The construction of the automaton $\mathcal{A}'$ from an arbitrary NFA $\mathcal{A}$ and the Meyer–Fischer automaton $\mathcal{A}_{\mathrm{MF}}$

Figure 3. The construction of the automaton A′\mathcal{A}' from an arbitrary NFA A\mathcal{A} with an explicit dead state q∅q_{\varnothing} and the n(k+1)n(k+1)-state Meyer–Fischer automaton AMF\mathcal{A}_{\mathrm{MF}}. All nonfinal states of A\mathcal{A} are connected to the initial state p1p_1 of AMF\mathcal{A}_{\mathrm{MF}} using symbol #\# and all final states (q4q_4 is the only one in A\mathcal{A}) are connected to all states of AMF\mathcal{A}_{\mathrm{MF}} using the same symbol #\#. In the diagram, t=n(k+1)t=n(k+1).

Without loss of generality assume that A\mathcal{A} has an explicit dead state q∅q_{\varnothing}, i.e., if some state q∈Qq \in Q is missing an explicit transition for some symbol w∈Σw \in\Sigma, we augment A\mathcal{A} with transition q→wq∅q \xrightarrow{w} q_{\varnothing}. In other words, A\mathcal{A}’s transition function is total.

Next, we create an automaton A′\mathcal{A}' over the alphabet Σ′={a,b,#}\Sigma' = \{a,b,\#\} by conjoining A\mathcal{A} and AMF\mathcal{A}_{\mathrm{MF}} as follows (see Figure 3):

  1. We add #\#-labeled transitions from all nonfinal states of A\mathcal{A} to AMF\mathcal{A}_{\mathrm{MF}}’s initial state p1p_1. The state p1p_1 is no longer initial in A′\mathcal{A}'.

  2. We add #\#-labeled transitions from all final states in A\mathcal{A} to all states of AMF\mathcal{A}_{\mathrm{MF}}. The final states from FF are no longer final in A′\mathcal{A}'.

Next, we analyze an application of the subset construction to A′\mathcal{A}' by breaking its computation into two stages. In the first stage, we only traverse transitions with symbols aa and bb. This corresponds exactly to running Algorithm 1 on A\mathcal{A}. After the first stage is completed, i.e., after no new states can be generated, we allow Algorithm 1 to consider other symbols from Σ′\Sigma'. Note that our decomposition into two stages is little more than an enforcement of a specific ordering of the computation performed by Algorithm 1 when determinizing A′\mathcal{A}'—it does not change what is computed, since the set of powerstates generated by Algorithm 1 does not depend on the order in which they are explored. We denote the resulting subset automaton as Ass′\mathcal{A}'_{\mathrm{ss}}.

Let us observe the (incomplete) subset automaton after the first stage. We first consider the case where A\mathcal{A} is universal. Due to Lemma 19, all states in the (incomplete) subset automaton contain at least one final state from A\mathcal{A}. Hence, in the second stage of the subset construction, any #\#-labeled transition leads to the powerstate Q1={p1,…,pt}Q_1 = \{p_1,\ldots,p_t\}, where, due to Lemma 20, we either remain forever (for Σ\Sigma-labeled transitions) or transition into the powerstate ∅\varnothing (for #\#-labeled transitions). This means that exactly 2 additional states are produced in the second stage.

Next, we consider the case where A\mathcal{A} is not universal and let x∈{a,b}∗∖L(A)x \in\{a,b\}^* \setminus L(\mathcal{A}) be an arbitrary word not in the language. Observe that in this case

x#L(AMF)⊆L(A′)and{x#y∣y∈L(AMF)∁}∩L(A′)=∅.(17)x\#L(\mathcal{A}_{\mathrm{MF}}) \subseteq L(\mathcal{A}') \quad\text{and}\quad\{x\#y \mid y \in L(\mathcal{A}_{\mathrm{MF}})^{\complement}\} \cap L(\mathcal{A}') = \varnothing. \tag*{(17)}

since every path with yield xx ends in a non-final state of A\mathcal{A}, meaning that x#x\# leads exclusively to p1p_1 in A′\mathcal{A}'. Now consider the minimal deterministic automaton for A′\mathcal{A}', which we denote with Adet′\mathcal{A}'_{\mathrm{det}} and let q′q' be the state in Adet′\mathcal{A}'_{\mathrm{det}} to which the path π\pi with the yield x#x\# leads. Observe that the right language of q′q' is L(AMF)L(\mathcal{A}_{\mathrm{MF}}), meaning that the number of states in Adet′\mathcal{A}'_{\mathrm{det}} satisfies ∣Adet′∣≥2n(k+1)|\mathcal{A}'_{\mathrm{det}}| \geq2^{n(k+1)}.

In summary, if A\mathcal{A} is universal, then the subset automaton Ass′\mathcal{A}'_{\mathrm{ss}} will have exactly 2 more states than Ass\mathcal{A}_{\mathrm{ss}}, while if A\mathcal{A} is not universal, it will require at least 2n(k+1)2^{n(k+1)} states. Moreover, since A\mathcal{A} has only nn states, the size of Ass\mathcal{A}_{\mathrm{ss}} will be at most 2n2^n. Thus, if A\mathcal{A} is universal, we have ∣Ass′∣≤2n+2|\mathcal{A}'_{\mathrm{ss}}| \leq2^n + 2. And, if A\mathcal{A} is not universal, we have ∣Ass′∣≥∣Adet′∣≥2n(k+1)|\mathcal{A}'_{\mathrm{ss}}| \geq|\mathcal{A}'_{\mathrm{det}}| \geq2^{n(k+1)}. It follows that if A\mathcal{A} is universal, any pp-approximation m^\hat{m} for m=∣Ass′∣m = |\mathcal{A}'_{\mathrm{ss}}| will satisfy

m^≤p(m+∣A′∣)∈O((m+n(k+2))d)=O((2n+2+n(k+2))d).(18)\hat{m} \leq p(m + |\mathcal{A}'|) \in O\left((m+n(k+2))^d\right) = O\left((2^n+2+n(k+2))^d\right). \tag*{(18)}

And, if A\mathcal{A} is not universal, m^≥2n(k+1)\hat{m} \geq2^{n(k+1)}. We choose k≫dk \gg d, the degree of pp. If we assume that nn is sufficiently large then, by comparing m^\hat{m} and 2n(k+1)2^{n(k+1)}, we can decide the universality of A\mathcal{A}.

Due to Eq. (15), the number of steps in the subset construction is proportional to mm by a factor of ∣A′∣2=n2(k+2)2|\mathcal{A}'|^2 = n^2(k+2)^2, hence a polynomial approximation for the number of steps can be converted into a polynomial approximation for m=∣Ass′∣m = |\mathcal{A}'_{\mathrm{ss}}|.

We conclude that it is PSPACE-hard to compute a pp-approximation for the subset construction on general NFAs. This argument also holds for any improvements of the subset construction, since the number of steps can be smaller than ∣Ass′∣|\mathcal{A}'_{\mathrm{ss}}| in case A\mathcal{A} is universal, but has to be at least ∣Adet′∣≥2n(k+1)|\mathcal{A}'_{\mathrm{det}}| \geq2^{n(k+1)} in case A\mathcal{A} is not. Thus, any pp-approximation decides universality of A\mathcal{A} for any improvement of the subset construction.

Theorem 22. For any polynomial pp, it is PSPACE-hard to compute a pp-approximation for Brzozowski’s algorithm or any improvement thereof.

Proof. Let A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma,Q,I,F,\delta) be an FA with n=∣A∣n = |\mathcal{A}|, pp an arbitrary polynomial of degree dd, and let k∈Nk \in\mathbb{N} be some positive integer. We will construct A′\mathcal{A}' similarly to Theorem 21, but instead of adjoining the n(k+1)n(k+1)-state Meyer–Fischer automaton AMF\mathcal{A}_{\mathrm{MF}} we will adjoin the modified Meyer–Fischer automaton, denoted with AMMF\mathcal{A}_{\mathrm{MMF}}, as presented in Figure 4. We designed AMMF\mathcal{A}_{\mathrm{MMF}} in such a way that L(AMF)=L(AMMF)\mathcal{L}(\mathcal{A}_{\mathrm{MF}})=\mathcal{L}(\mathcal{A}_{\mathrm{MMF}}) but, in contrast to the original, AMMF\mathcal{A}_{\mathrm{MMF}} is co-deterministic (its reverse is given explicitly in Figure 4).

Notice that Lemma 20 also holds for AMMF\mathcal{A}_{\mathrm{MMF}}, thus, analogously to Theorem 21, if A\mathcal{A} is universal, no matter when we take a transition with label #\#, we will stay forever in Q1={p1,…,pt,pb}Q_1=\{p_1,\ldots,p_t,p_b\}, which is accepting. Thus, the underlying language satisfies

L(ADET′)=L(A′)=L(A)#{a,b}∗={a,b}∗#{a,b}∗.(19)\mathcal{L}(\mathcal{A}'_{\mathrm{DET}})=\mathcal{L}(\mathcal{A}')=\mathcal{L}(\mathcal{A})\#\{a,b\}^{*}=\{a,b\}^{*}\#\{a,b\}^{*}. \tag*{(19)}

Similarly, if A\mathcal{A} is not universal, then the state complexity ∣ADET′∣|\mathcal{A}'_{\mathrm{DET}}| is at least 2n(k+1)2^{n(k+1)} due to Eq. (17).

Our goal is to show that for any universal A\mathcal{A}, Brzozowski’s algorithm will not produce too many states on A′\mathcal{A}'. To achieve that we will analyze its execution using two stages: first reversing A′\mathcal{A}', running Algorithm 1 and reversing the result and, second, running Algorithm 1 again.

Claim 1. The number of states after the first stage of Brzozowski’s algorithm on A′\mathcal{A}' is at most k2n+2k2^{n+2}.

The first stage of Brzozowski’s algorithm corresponds to running Algorithm 1 on (A′)R(\mathcal{A}')^R which is, effectively, the concatenation of (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R with AR\mathcal{A}^R using #\# (recall that the copy of A\mathcal{A} within A′\mathcal{A}' has no final states).

First, Algorithm 1 is launched on initial states from (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R, but, while exploring only Σ\Sigma-labeled transitions, no new states will be created because (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R is already deterministic. As soon as #\#-labeled transitions are encountered, the situation changes: all #\#-labeled transitions from (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R lead either into the powerstate Q=QQ=Q or Q′=FQ'=F in AR\mathcal{A}^R. In the spirit of Theorem 21 we enforce the following ordering on the execution of Algorithm 1:

  1. Take any #\#-transition from (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R into QQ and find all reachable powerstates

  2. Take any #\#-transition from (AMMF)R(\mathcal{A}_{\mathrm{MMF}})^R into Q′Q' and find all reachable powerstates

Notice that after both 1. and 2. are completed, there are no new states for Algorithm 1 to discover within (A′)R(\mathcal{A}')^{R}, hence it has to terminate. Furthermore, the number of states discovered in 1. is at most 2n2^n, as is the number of states discovered in 2.—indeed, both 1. and 2. can be interpreted as running two instances of Algorithm 1 on two separate copies of nn-state NFA AR\mathcal{A}^{R}. Hence, after the first stage on A′\mathcal{A}' we obtain some automaton ABR′\mathcal{A}'_{\mathrm{BR}} satisfying

∣ABR′∣≤∣AMMF∣+2n+2n=2n+1+n(k+1)+1≤k2n+2,(20)|\mathcal{A}'_{\mathrm{BR}}| \leq|\mathcal{A}_{\mathrm{MMF}}| + 2^n + 2^n = 2^{n+1} + n(k+1) + 1 \leq k2^{n+2}, \tag*{(20)}

which concludes the claim.

In the second stage, Brzozowski’s algorithm executes the subset construction on ABR′\mathcal{A}'_{\mathrm{BR}}, but this time the subset automaton for ABR′\mathcal{A}'_{\mathrm{BR}} is the minimal DFA ADET′\mathcal{A}'_{\mathrm{DET}} with exactly 3 states. Thus, if A\mathcal{A} is universal, then, due to Eq. (16), the total number of steps will be proportional to at most

∣A′∣2∣ABR′∣+∣ADET′∣∣ABR′∣2≤(n(k+2)+1)2k2n+2+3k222n+4≤n2k429n.(21)|\mathcal{A}'|^2|\mathcal{A}'_{\mathrm{BR}}| + |\mathcal{A}'_{\mathrm{DET}}||\mathcal{A}'_{\mathrm{BR}}|^2 \leq(n(k+2)+1)^2 k2^{n+2} + 3k^2 2^{2n+4} \leq n^2k^4 2^{9n}. \tag*{(21)}

On the other hand, if A\mathcal{A} is not universal, any algorithm will require at least ∣ADET′∣≥2n(k+1)|\mathcal{A}'_{\mathrm{DET}}| \geq2^{n(k+1)} many steps. Following the argument from Theorem 21, by choosing k≫dk \gg d, any pp-approximation for Brzozowski’s algorithm (or any improvement thereof) on A′\mathcal{A}' can be used to decide universality of A\mathcal{A}. □\square

As a bonus, we show a somewhat unexpected consequence—the performance of the subset construction and Brzozowski’s algorithm remains intractable even when the exact state complexity is known, and, as a consequence, it is also intractable to predict how much overhead these determinization algorithms require in addition to producing the minimal DFA.

Corollary 23. For any polynomial pp, it remains PSPACE-hard to compute a pp-approximation for the subset construction or Brzozowski’s algorithm even when the algorithm is applied to input NFAs whose state complexity is known in advance (in fact, equal to 1).

Proof. To show the claim, we modify the construction from Theorem 21. Let A∪\mathcal{A}^{\cup} denote the union automaton of A′\mathcal{A}' and AUNIV\mathcal{A}_{\mathrm{UNIV}} from Eq. (10), made universal over the alphabet Σ∪{#}\Sigma\cup\{\#\}, and denote the unique state of AUNIV\mathcal{A}_{\mathrm{UNIV}} by quq_u. Since L(A∪)=(Σ∪{#})∗L(\mathcal{A}^{\cup}) = (\Sigma\cup\{\#\})^*, the state complexity of A∪\mathcal{A}^{\cup} is known and is 1; the same holds for its reverse (A∪)R(\mathcal{A}^{\cup})^R. It is easy to see that the execution path of both subset construction is equivalent between A′\mathcal{A}' and A∪\mathcal{A}^{\cup}, and the same holds for (A′)R(\mathcal{A}')^R and (A∪)R(\mathcal{A}^{\cup})^R in case of Brzozowski’s algorithm. □\square

:::

Corollary 24. Any pp-approximation for the overhead of the subset construction on a given NFA A\mathcal{A}, i.e., the difference ∣ASS∣−∣ADET∣|\mathcal{A}_{\mathrm{SS}}| - |\mathcal{A}_{\mathrm{DET}}|, is PSPACE-hard to compute.

We informally summarize the findings in this section as follows: no metric can accurately measure the performance of any good determinization algorithm, sometimes even in the presence of additional advice. In the remaining part of this paper we therefore drop the accuracy requirement and instead look for metrics that can provide any information about potential performance of determinization.

Semigroup Complexity

Due to Theorem 21 and Theorem 22, no reasonable approximation for the complexity of determinization algorithms is possible (assuming PSPACE ≠\ne P) or, in other words, no potential metric can be both

  • (i) a reasonably accurate approximation

  • (ii) computable in polynomial time for all NFAs.

We will take a middle path between (i) and (ii) and, in what follows, focus on bounding the size of the subset automaton AssA_{\mathrm{ss}}, since it plays a key role in many determinization algorithms and, more generally, can serve as a simple practical indicator. One way of achieving such a bound is by looking at semigroup complexity [6], a metric measuring the size of the transition monoid S(A)S(A).

Theorem 25 (Semigroup Complexity). Given an NFA AA, its subset automaton AssA_{\mathrm{ss}} satisfies ∣Ass∣≤∣S(A)∣|A_{\mathrm{ss}}| \le|S(A)|.

Proof. Following Algorithm 1 we conclude that since every element of QssQ_{\mathrm{ss}} is the image of at least one relation in S(A)S(A), we have ∣Qss∣≤∣S(A)∣|Q_{\mathrm{ss}}| \le|S(A)|.

We remark that in general transition monoids tend to be very large, sometimes much larger than the actual number of states in the FA. For nn-state deterministic FAs over a binary alphabet, the syntactic monoid recognizing the same language can have size up to nn(1−2/n)n^n(1 - 2/\sqrt{n}) (see [11] for a deeper discussion). Furthermore, there is no general way of computing the exact semigroup complexity, hence, in what follows, we will restrict ourselves to subclasses of NFAs for which this is feasible.

Unary Automata

For any unary NFA A1A_1 let AA be its unique transition matrix. Then the bound on ∣S(A1)∣|S(A_1)| relies solely on the precedence graph G(A)G(A), i.e., a directed graph with ∣A∣|A| vertices and edges defined by the transition matrix AA.

Definition 26. Given a directed graph GG the cyclicity of GG, denoted with c(G)c(G), is the least common multiple of cyclicities of all maximal strongly connected components of GG, where the cyclicity of a strongly connected component CC is the greatest common divisor of the lengths of all cycles in CC.

The strongly connected components in any directed graph can be identified in linear time [26], therefore we can get a trivial upper bound for the cyclicity as the product of the cardinalities of all strongly connected components, since the cyclicity of each strongly connected component is at most its cardinality. The following result from semigroup theory allows us to directly bound the semigroup complexity.

Proposition 27 (Index and Period [19]). Let A1=({w},Q1,I1,F1,δ1)\mathcal{A}_1 = (\{w\}, Q_1, I_1, F_1, \delta_1) be an nn-state unary automaton with transition matrix AA. Then

c(G(A))≤∣S(A1)∣≤c(G(A))+n2−2n+2.(22)c(G(A)) \leq|S(\mathcal{A}_1)| \leq c(G(A)) + n^2 - 2n + 2. \tag*{(22)}

Permutation Automata

An NFA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta) is a permutation automaton if for every letter w∈Σw \in\Sigma the transition relation δ\delta defines a permutation of the set of states QQ. Note that in this case S(A)S(\mathcal{A}) is a permutation group generated by the corresponding transition matrices. Due to the famous Schreier–Sims algorithm [17] from computational group theory, the size of any permutation group can be computed in quasi-quadratic time.

Commutative Automata

An automaton A\mathcal{A} is commutative if all transition matrices in {T(w)∣w∈Σ}\{T^{(w)} \mid w \in\Sigma\} commute with each other. Its underlying language L(A)\mathcal{L}(\mathcal{A}) is closed under letter permutations, i.e., for any word w∈L(A)w \in\mathcal{L}(\mathcal{A}) and any permutation π\pi, we have π(w)∈L(A)\pi(w) \in\mathcal{L}(\mathcal{A}). The following result follows immediately.

Proposition 28. Given a commutative automaton A\mathcal{A}, define for any w∈Σw \in\Sigma the transition monoid generated by T(w)T^{(w)} as S(T(w))S(T^{(w)}). Then:

∣S(A)∣≤∏w∈Σ∣S(T(w))∣(23)|S(\mathcal{A})| \leq\prod_{w \in\Sigma} |S(T^{(w)})| \tag*{(23)}

In particular, this implies that any bound from § 6.1 can be applied individually to each unary subautomaton of A\mathcal{A}.

Dense Automata

Another interesting class of NFAs to consider is NFAs with many nondeterministic transitions. From the case of Moore’s automaton (see Figure 1) we know that adding a single nondeterministic transition—i.e., a transition whose addition makes the automaton no longer deterministic—can have an exponential effect on the state complexity of the NFA. In this section we show that, in some sense, the opposite is true, i.e., that in the presence of many transitions (i.e., when ∣δ∣|\delta| is large compared to ∣Q∣|Q|), the semigroup complexity (and hence the determinization) will likely stay sub-exponential.

Definition 29. An n×nn \times n Boolean matrix BB is rr-indecomposable if and only if for any non-zero Boolean (row) vector vv with ∣v∣|v| non-zero entries it holds:

∣vB∣≥min⁡{n,∣v∣+r}(24)|vB| \geq\min\{n, |v| + r\} \tag*{(24)}

This property has a direct relation to semigroup complexity: indeed, it is easy to see that any product of n/rn/r arbitrary n×nn \times n rr-indecomposable Boolean matrices results in a 1-block matrix. We will use the notation 1−o(1)1-o(1) to denote the probability which becomes arbitrarily close to 1 as the parameter n→∞n \to\infty. The subsequent result highlights the key fact linking indecomposable matrices to NFAs with many transitions.

Lemma 30 (Dense Matrices) [16]. An n×nn \times n Boolean matrix picked uniformly at random from the set of matrices with exactly (1+ϵ+r)nlog⁡n(1+\epsilon+r)n \log n non-zero entries will be rr-indecomposable with probability 1−o(1)1-o(1) for an arbitrary ϵ>0\epsilon> 0.

By combining the properties of indecomposable matrices bounding the size of the transition monoid with the distribution result on dense matrices from Lemma 30, we can formulate the final statement.

Proposition 31. Let d∈N+d \in\mathbb{N}_{+} be a constant, Σ\Sigma some fixed alphabet and A\mathcal{A} an NFA over Σ\Sigma sampled uniformly at random from the set of all NFAs where for every w∈Σw \in\Sigma the transition matrix T(w)T^{(w)} contains at least n2/dn^2/d transitions. Then, with probability 1−o(1)1-o(1) it holds:

∣S(A)∣≤ndlog⁡∣Σ∣+o(1)(25)|\mathcal{S}(\mathcal{A})| \le n^{d\log|\Sigma|+o(1)} \tag*{(25)}

Proof. Assume that all transition matrices in A\mathcal{A} are rr-indecomposable for some r∈Nr \in\mathbb{N}, and consider a product of arbitrary ⌈n−1r⌉\left\lceil\frac{n-1}{r}\right\rceil matrices from {T(w)∣w∈Σ}\{T^{(w)} \mid w \in\Sigma\}. Due to Definition 29, each row of the resulting product will have at least min⁡{n,1+⌊n−1r⌋⋅r}=n\min\{n,1+\lfloor\frac{n-1}{r}\rfloor\cdot r\}=n entries, thus we will get a 1-block matrix. Thus, all elements of S(A)\mathcal{S}(\mathcal{A}) with at least one zero entry will be the products of at most ⌈n−1r⌉−1\left\lceil\frac{n-1}{r}\right\rceil-1 transition matrices. This means that the cardinality of S(A)\mathcal{S}(\mathcal{A}) is bounded by the number of words over the alphabet Σ\Sigma with length of at most ⌈n−1r⌉−1\left\lceil\frac{n-1}{r}\right\rceil-1, i.e.

∣S(A)∣−1≤∑i=0⌈(n−1)/r⌉−1∣Σ∣i≤∣Σ∣⌈(n−1)/r⌉∣Σ∣−1≤2∣Σ∣(n−1)/r(26)|\mathcal{S}(\mathcal{A})|-1 \le\sum_{i=0}^{\lceil(n-1)/r\rceil-1}|\Sigma|^i \le\frac{|\Sigma|^{\lceil(n-1)/r\rceil}}{|\Sigma|-1} \le2|\Sigma|^{(n-1)/r} \tag*{(26)}

By Lemma 30, with probability 1−o(1)1-o(1) all randomly sampled transition matrices of A\mathcal{A} will be rr-indecomposable with r=ndlog⁡n−(1+ϵ)r=\frac{n}{d\log n}-(1+\epsilon) (note that our matrices have at least n2/dn^2/d non-zero entries, hence we are sampling with ϵ\epsilon of at least n/log⁡nn/\log n). Thus, by performing the substitution we get

∣S(A)∣≤2∣Σ∣d(n−1)log⁡nn−(1+ϵ)dlog⁡n≤∣Σ∣dlog⁡n+o(1)(27)|\mathcal{S}(\mathcal{A})| \le2|\Sigma|^{\frac{d(n-1)\log n}{n-(1+\epsilon)d\log n}} \le|\Sigma|^{d\log n+o(1)} \tag*{(27)}

with probability 1−o(1)1-o(1). □

We could not find any other major classes of automata where meaningful inference on their semigroup complexity can be performed. In the subsequent sections we attempt to mitigate this by modifying our proposed complexity metric.

Subset Complexity

Another natural way to bound the size of the subset automaton is to consider individual ranges R(T(w))\mathcal{R}(T^{(w)}) for Boolean transition matrices in {T(w)∣w∈Σ}\{T^{(w)} \mid w \in\Sigma\}. Since every state in the subset automaton corresponds to a characteristic vector over QQ, it has to be in the image of some transition matrix T(w)T^{(w)} for w∈Σw \in\Sigma. Hence, the size of their combined images is an upper bound on the size of the subset automaton.

Lemma 32 (Range Complexity). Let A\mathcal{A} be an NFA with a set of transition matrices {T(w)∣w∈Σ}\{T^{(w)} \mid w \in\Sigma\}. Then its subset automaton Ass\mathcal{A}_{\mathrm{ss}} satisfies

∣Ass∣≤1+∑w∈Σ∣R(T(w))∣,(28)|\mathcal{A}_{\mathrm{ss}}| \le1 + \sum_{w\in\Sigma} \left|\mathcal{R}\left(T^{(w)}\right)\right|, \tag*{(28)}

where R(T)\mathcal{R}(T) is the range of the matrix TT over the Boolean semifield B\mathbb{B}.

Proof. Let Ass=(Σ,Qss,I,Fss,δss)\mathcal{A}_{\mathrm{ss}}=(\Sigma,Q_{\mathrm{ss}},I,F_{\mathrm{ss}},\delta_{\mathrm{ss}}). Consider any QJ∈QssQ_J \in Q_{\mathrm{ss}} and let w1⋯wN∈Σ∗w_1\cdots w_N \in\Sigma^* be a word such that QJ=δ(QI,w1⋯wN)Q_J=\delta(Q_I,w_1\cdots w_N). Then, QJQ_J's characteristic vector is given by

J=ITT(w1)T(w2)⋯T(wN).(29)J=I^{\mathsf{T}}T^{(w_1)}T^{(w_2)}\cdots T^{(w_N)}. \tag*{(29)}

Moreover, because this holds for any JJ, we have

Qss∖{QI}⊆⋃w∈ΣR(T(w)T).(30)Q_{\mathrm{ss}}\setminus\{Q_I\}\subseteq\bigcup_{w\in\Sigma}\mathcal{R}\left(T^{(w)\mathsf{T}}\right). \tag*{(30)}

Note that the row space and the column space of a Boolean matrix have the same cardinality, i.e., ∣R(T(w)T)∣=∣R(T(w))∣|\mathcal{R}(T^{(w)\mathsf{T}})|=|\mathcal{R}(T^{(w)})| for every w∈Σw\in\Sigma. Applying the union bound and adding 1 to account for the initial state QIQ_I concludes the proof. □

Serendipitously, both the range bound and semigroup complexity can be naturally combined, admitting a more fine-grained perspective on the size of the subset automaton, each compensating for the slackness of the other.

Definition 33. Given an NFA A=(Σ,Q,I,F,δ)\mathcal{A}=(\Sigma,Q,I,F,\delta), we define the subset complexity ∥A∥\|\mathcal{A}\| as

∥A∥=min⁡Γ⊆Σ(1+∑w∈Σ∖Γ∣R(T(w))∣)∣S(Γ)∣,(31)\|\mathcal{A}\|=\min_{\Gamma\subseteq\Sigma}\left(1+\sum_{w\in\Sigma\setminus\Gamma}\left|\mathcal{R}\left(T^{(w)}\right)\right|\right)|\mathcal{S}(\Gamma)|, \tag*{(31)}

where Γ\Gamma is an arbitrary subset of the alphabet Σ\Sigma and S(Γ)\mathcal{S}(\Gamma) denotes the submonoid generated by the transitions {T(w)∣w∈Γ}\{T^{(w)}\mid w\in\Gamma\}.

Essentially, subset complexity allows us to split A\mathcal{A} into subautomata according to whether the symbols on the transitions are in Γ\Gamma or Σ∖Γ\Sigma\setminus\Gamma, respectively. Then, we either apply the monoid or the range bound independently. The subset complexity is the best possible split.

Theorem 34 (Subset Complexity). Let A\mathcal{A} be an NFA and let ASS\mathcal{A}_{\mathrm{SS}} be the DFA output by the subset construction with A\mathcal{A} as input. Then, we have ∣ASS∣≤∥A∥|\mathcal{A}_{\mathrm{SS}}| \le\|\mathcal{A}\|.

Proof. Let Γ⊆Σ\Gamma\subseteq\Sigma be arbitrary. We first show that

∣ASS∣≤(1+∑w∈Σ∖Γ∣R(T(w))∣)∣S(Γ)∣.(32)|\mathcal{A}_{\mathrm{SS}}| \le\left(1+\sum_{w\in\Sigma\setminus\Gamma}|\mathcal{R}(T^{(w)})|\right)|\mathcal{S}(\Gamma)|. \tag*{(32)}

For any word x∈Σ∗x\in\Sigma^*, let x=yz=yz1⋯zmx=yz=yz_1\cdots z_m be the unique decomposition where zi∈Γz_i\in\Gamma and m∈Nm\in\mathbb{N} is maximal. Furthermore, let QJ=δ(QI,x)Q_J=\delta(Q_I,x). Similarly to the proof of Proposition 32, we consider a characteristic vector JJ for QJQ_J. For clarity, we will denote transition matrices corresponding to symbols w∈Γw\in\Gamma with R(w)R^{(w)} and transition matrices which correspond to symbols w∉Γw\notin\Gamma with L(w)L^{(w)}. Then, the characteristic vector JJ can be written as

J=J′R(z1)⋯R(zm),(33)J=J'R^{(z_1)}\cdots R^{(z_m)}, \tag*{(33)}

where J′J' is either the initial characteristic vector I⊤I^\top (in case x=zx=z, i.e., y=εy=\varepsilon) or an element of ⋃w∈Σ∖ΓR(L(w)⊤)\bigcup_{w\in\Sigma\setminus\Gamma}\mathcal{R}(L^{(w)\top}), since the last symbol of yy lies outside of Γ\Gamma. Because ∣R(L(w)⊤)∣=∣R(L(w))∣|\mathcal{R}(L^{(w)\top})|=|\mathcal{R}(L^{(w)})|, there are at most 1+∑w∈Σ∖Γ∣R(L(w))∣1+\sum_{w\in\Sigma\setminus\Gamma}|\mathcal{R}(L^{(w)})| choices for a vector J′J' and ∣S(Γ)∣|\mathcal{S}(\Gamma)| choices for the matrix R(z1)⋯R(zm)R^{(z_1)}\cdots R^{(z_m)}. Thus, the total number of choices for JJ is bounded by the corresponding product. The minimum bound follows. □

Observe that the new notion of subset complexity is a direct improvement over both the monoid and the range bounds, since it allows us to cherry-pick individual transition matrices according to their properties to achieve the tightest bound.

Example 35. Consider the nn-state Moore automaton AMOORE\mathcal{A}_{\mathrm{MOORE}} from Figure 1 with state complexity of 2n2^n. We define a modified nn-state Moore automaton AMOORE′\mathcal{A}'_{\mathrm{MOORE}} as follows. Take the nn-state Moore automaton and replace the labels on the transitions qn→aq1q_n \xrightarrow{a} q_1 and qn→aq2q_n \xrightarrow{a} q_2 with a new symbol c∉{a,b}c\notin\{a,b\}. The new automaton AMOORE′\mathcal{A}'_{\mathrm{MOORE}} operates over the alphabet Σ={a,b,c}\Sigma= \{a,b,c\}; it is still nondeterministic, as shown in Figure 5 (left).

Two modified automata over an extended alphabet

Figure 5. An nn-state modified Moore automaton AMOORE′\mathcal{A}'_{\mathrm{MOORE}} over extended alphabet Σ={a,b,c}\Sigma=\{a,b,c\} (left) and an nn-state modified Meyer–Fischer automaton AMF′\mathcal{A}'_{\mathrm{MF}} where some labels on self loops with bb were swapped for aa (right).

Claim 1. For an nn-state modified Moore automaton AMOORE′A'_{\mathrm{MOORE}}, the following inequality holds ∥AMOORE′∥≤3n2+3n\lVert A'_{\mathrm{MOORE}}\rVert\le3n^{2}+3n.

Indeed, let Γ={a,b}\Gamma= \{a,b\} and observe that T(a)T(b)=T(a)T(a)T^{(a)}T^{(b)} = T^{(a)}T^{(a)}, which means that all matrices in the transition monoid S(Γ)S(\Gamma) can be obtained from a product sequence of the following form

T(b)T(b)⋯T(b)T(a)T(a)⋯T(a).T^{(b)}T^{(b)}\cdots T^{(b)}T^{(a)}T^{(a)}\cdots T^{(a)}.

Moreover, we have that (T(a))n=0(T^{(a)})^{n}=0, i.e., the zero matrix and (T(b))n−1=(T(b))n(T^{(b)})^{n-1}=(T^{(b)})^{n}, meaning that there are at most n+1n+1 distinct powers of T(a)T^{(a)} and nn distinct powers of T(b)T^{(b)} (counting the empty set). Hence, ∣S(Γ)∣≤n(n+1)=n2+n|S(\Gamma)| \le n(n+1)=n^{2}+n. Moreover, we have that ∣R(T(c))∣=2|\mathcal{R}(T^{(c)})|=2 because T(c)T^{(c)} is a rank-1 matrix. Applying Theorem 34 concludes the claim.

Example 36

Let us consider the modified Meyer–Fischer automaton AMF′A'_{\mathrm{MF}} where we replace the labels on all but kk of the bb-labeled self-loop transitions with aa, as shown in Figure 5 (right).

Claim 1. For an nn-state modified Meyer–Fischer automaton AMF′A'_{\mathrm{MF}} it holds: ∥AMF′∥≤(2k+1+1)(n2−2n+3)\lVert A'_{\mathrm{MF}}\rVert\le(2^{k+1}+1)(n^{2}-2n+3).

To demonstrate the claim we choose Γ={a}\Gamma= \{a\} and observe that the cyclicity of G(T(a))\mathcal{G}(T^{(a)}) is 1 because it is strongly connected and has a self-loop. By applying Proposition 27 we therefore obtain ∣S(Γ)∣≤n2−2n+3|S(\Gamma)| \le n^{2}-2n+3. Finally, we notice that ∣R(T(b))∣|\mathcal{R}(T^{(b)})| is at most 2k+12^{k+1} since T(b)T^{(b)} consists precisely of k+1k+1 non-zero columns. Applying Theorem 34 concludes the claim.

We note that in Examples 35 and 36 both the initial states II and the final states FF can be chosen arbitrarily: the subset complexity is fully agnostic about them.

Practical Considerations

In this section, we discuss some computationally feasible approaches for estimating the subset complexity from Theorem 34, which requires computing the size of the range space as well as the size of the transition monoid. Computing the cardinality of the range of a Boolean matrix is equivalent to counting maximal independent sets in bipartite graphs [28], which is a #P-complete problem [23]. The monoid size was partially examined in § 6 and is generally difficult to determine.

However, despite these obstacles, we managed to derive a somewhat efficiently computable upper bound for subset complexity by restricting the monoid to the one-letter case only. This idea gives insight into the determinization complexity of many non-trivial NFAs, and in particular, two-letter automata.

Lemma 37 (Lemma 1 in [7]). Given an n×nn \times n Boolean matrix AA, let rank⁡(A)\operatorname{rank}(A) be the rank of AA over the Galois field F2\mathbb{F}_2. Then the range of AA satisfies

rank⁡(A)≤∣R(A)∣≤2rank⁡(A)2/4+O(rank⁡(A)).(34)\operatorname{rank}(A) \leq|\mathcal{R}(A)| \leq2^{\operatorname{rank}(A)^2/4+O(\operatorname{rank}(A))}. \tag*{(34)}

Remark 38. The rank over F2\mathbb{F}_2 can be calculated using Gaussian elimination over F2\mathbb{F}_2. Other possibilities for bounding the range exist. For example, one can consider the size of maximum matching or the notion of Boolean width; see [7] for in-depth discussion. ♢

In § 6 we have discussed the connection between the cyclicity of the precedence graph and the semigroup complexity in the case of unary automata. Using the simplified bounds for range on symbols Σ∖{a}\Sigma\setminus\{a\} and monoid size on the remaining symbols Γ={a}\Gamma= \{a\} we get a simple upper bound on the subset complexity for any automaton A\mathcal{A}.

Proposition 39 (All-but-one). Given an nn-state NFA A=(Σ,Q,I,F,δ)\mathcal{A} = (\Sigma, Q, I, F, \delta), an arbitrary target symbol a∈Σa \in\Sigma and any ε>0\varepsilon> 0, the following holds

∥A∥∈O(∣Σ∣(c(G(T(a)))+n2)max⁡b∈Σ∖{a}2rank⁡(T(b))2/(4−ε)).(35)\|\mathcal{A}\| \in O\left(|\Sigma|(c(\mathcal{G}(T^{(a)})) + n^2) \max_{b \in\Sigma\setminus\{a\}} 2^{\operatorname{rank}(T^{(b)})^2/(4-\varepsilon)}\right). \tag*{(35)}

The proof is a straightforward application of Lemma 37 and Proposition 27, and gives us the following intuition about determinization: if all but one of the transition matrices are of low rank, then the subset complexity will be polynomially bounded (the cyclicity is large only in very artificial cases).

Conclusion

Given an NFA, we have attempted to develop a method for measuring its determinization complexity, i.e., the difficulty of transforming it into the corresponding minimal DFA. First, we began by examining the shortcomings of classical complexity measures and concluded that the ideal measure should be intrinsically connected to the underlying determinization algorithms. Unfortunately, it turned out to be PSPACE-hard to provide any accurate approximation for the performance of many major determinization algorithms under any reasonable definition thereof.

In the second part, we focused primarily on the state complexity of the subset automaton Ass\mathcal{A}_{\mathrm{ss}} which, in our opinion, is integral to understanding determinization. We then linked the subset automaton with the size of the underlying transition monoid and investigated different methods to bound it. Finally, we defined a new metric—the subset complexity—and examined some subclasses of automata for which it is particularly suitable to apply.

Acknowledgments

The authors thank the anonymous referees for several suggestions and, in particular, Ian McQuillan for fruitful discussions about generalizing results from Section 5.

References

  1. [1]C. Allauzen, M. Riley, J. Schalkwyk, W. Skut, M. Mohri, Openfst: A general and efficient weighted finite-state transducer library: extended abstract of an invited talk. In: Implementation and Application of Automata: 12th International Conference (CIAA). Springer, 2007, 11–23. https://link.springer.com/chapter/10.1007/978-3-540-76336-9_3
  2. [2]I. Baburin, R. Cotterell, An Analysis of On-the-fly Determinization of Finite-state Automata. 2023. https://arxiv.org/abs/2308.14077
  3. [3]I. Baburin, R. Cotterell, A close analysis of the subset construction. In: Descriptional Complexity of Formal Systems. Springer Nature Switzerland, 2025, 17–33. https://link.springer.com/chapter/10.1007/978-3-031-97106-6_2DOI
  4. [4]H. Bordihn, M. Holzer, M. Kutrib, Determination of finite automata accepting subregular languages. Theoretical Computer Science 410 (2009) 35, 3209–3222. Descriptional Complexity of Formal Systems. https://www.sciencedirect.com/science/article/pii/S0304397509003788DOI
  5. [5]J. A. Brzozowski, Canonical regular expressions and minimal state graphs for definite events. In: Proceedings of the Symposium on Mathematical Theory of Automata. MRI Symposia Series 12, Polytechnic Press, Polytechnic Institute of Brooklyn, New York, NY, USA, 1962, 529–561.
  6. [6]J. A. Brzozowski, Towards a theory of complexity of regular languages. Journal of Automata, Languages and Combinatorics 23 (2018) 1–3, 67–101. https://doi.org/10.25596/jalc-2018-067
  7. [7]B.-M. Bui-Xuan, J. A. Telle, M. Vatshelle, Boolean-width of graphs. Theoretical Computer Science 412 (2011) 39, 5187–5204. https://www.sciencedirect.com/science/article/pii/S030439751100418X
  8. [8]J.-M. Champarnaud, Subset construction complexity for homogeneous automata, position automata and zpc-structures. Theoretical Computer Science 267 (2001) 1-2, 17–34. https://www.sciencedirect.com/science/article/pii/S0304397500002930DOI
  9. [9]S. Cho, D. T. Huynh, The parallel complexity of finite-state automata problems. Information and Computation 97 (1992) 1, 1–22. https://www.sciencedirect.com/science/article/pii/089054019290002W
  10. [10]S. De Felice, C. Nicaud, On the average complexity of brzozowski’s algorithm for deterministic automata with a small number of final states. Developments in Language Theory (2014), 25–36. https://doi.org/10.1007/978-3-319-09698-8_3
  11. [11]M. Holzer, B. König, On deterministic finite automata and syntactic monoid size. Theoretical Computer Science 327 (2004) 3, 319–347. https://www.sciencedirect.com/science/article/pii/S0304397504004840
  12. [12]M. Holzer, M. Kutrib, Descriptional and computational complexity of finite automata—a survey. Information and Computation 209 (2011) 3, 456–470. Special Issue: 3rd International Conference on Language and Automata Theory and Applications (LATA 2009). https://www.sciencedirect.com/science/article/pii/S0890540110001999DOI
  13. [13]J. Hopcroft, An n log n algorithm for minimizing states in a finite automaton. In: Z. Kohavi, A. Paz (eds.), Theory of Machines and Computations. Academic Press, New York, 1971, 189–196. https://www.sciencedirect.com/science/article/pii/B9780124177505500221DOI
  14. [14]J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. 2nd edition, Addison-Wesley, Boston, MA, USA, 2001.
  15. [15]S. Kiefer, Complexity of NFA to DFA minimization with binary threshold. Theoretical Computer Science Stack Exchange. https://cstheory.stackexchange.com/q/50706
  16. [16]K. H. Kim, F. W. Roush, Two-generator semigroups of binary relations. Journal of Mathematical Psychology 17 (1978) 3, 236–246. https://www.sciencedirect.com/science/article/abs/pii/0022249678900184DOI
  17. [17]D. E. Knuth, Efficient representation of perm groups. Combinatorica 11 (1991) 1, 33–43. https://link.springer.com/article/10.1007/BF01375471arxiv.org/abs/math/9201304
  18. [18]D. Kuperberg, A. Majumdar, Width of Non-deterministic Automata. In: R. Niedermeier, B. Vallée (eds.), 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs) 96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 2018, 47:1–47:14. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.47
  19. [19]G. Markowsky, Bounds on the index and period of a binary relation on a finite set. Semigroup Forum 13 (1976) 1, 253–259. https://link.springer.com/article/10.1007/BF02194943DOI
  20. [20]A. R. Meyer, M. J. Fischer, Economy of description by automata, grammars, and formal systems. In: 12th Annual Symposium on Switching and Automata Theory (SWAT 1971). IEEE Computer Society, Los Alamitos, CA, USA, 1971, 188–191. https://doi.ieeecomputersociety.org/10.1109/SWAT.1971.11DOI
  21. [21]F. R. Moore, On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Transactions on Computers 100 (1971) 10, 1211–1214.DOI
  22. [22]J.-E. Pin, Syntactic semigroups. Handbook of Formal Languages: Volume 1 Word, Language, Grammar (1997), 679–746. https://link.springer.com/chapter/10.1007/978-3-642-59136-5_10DOI
  23. [23]J. S. Provan, M. O. Ball, The complexity of counting cuts and of computing the probability that a graph is connected. SIAM Journal on Computing 12 (1983) 4, 777–788. https://doi.org/10.1137/0212053
  24. [24]M. O. Rabin, D. Scott, Finite automata and their decision problems. IBM Journal of Research and Development 3 (1959) 2, 114–125. https://ieeexplore.ieee.org/document/5392601DOI
  25. [25]W. J. Savitch, Relationships between nondeterministic and deterministic tape complexities. Journal of Computer and System Sciences 4 (1970) 2, 177–192. https://www.sciencedirect.com/science/article/pii/S002200007080006XDOI
  26. [26]R. Tarjan, Depth-first search and linear graph algorithms. SIAM Journal on Computing 1 (1972) 2, 146–160. https://doi.org/10.1137/0201010
  27. [27]R. van Glabbeek, B. Ploeger, Five determinisation algorithms. In: O. H. Ibarra, B. Ravikumar (eds.), Implementation and Applications of Automata. Springer Berlin Heidelberg, Berlin, Heidelberg, 2008, 161–170. https://link.springer.com/chapter/10.1007/978-3-540-70844-5_17
  28. [28]M. Vatshelle, New width parameters of graphs. Ph.D. thesis, University of Bergen, 2012. https://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf
  29. [29]S. Yu, Q. Zhuang, K. Salomaa, The state complexities of some basic operations on regular languages. Theoretical Computer Science 125 (1994) 2, 315–328. https://www.sciencedirect.com/science/article/pii/030439759200011FDOI

Paper details

vlnc:W_d789kq4s
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents