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 states, where 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 is exponentially smaller than the DFA 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 -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 -state NFA, known as Moore’s automaton, for which the minimal equivalent DFA requires exactly 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 : 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 ) 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 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:
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 . 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:
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 is a finite, non-empty set of symbols. With , we denote the set of all finite strings, also called words, over . The symbol denotes the empty word, i.e., the unique word of length 0. Two words and are placed adjacent to each other, e.g., denotes the concatenation of those words.
Definition 1. A finite automaton (FA) is a quintuple where is an alphabet, is a finite set of states, is a set of the initial states, is a set of accepting states and is a finite multiset of labeled transitions between states.
Note that a transition labeled with can be performed at any point. The size of a finite automaton is its number of states ; we use the cardinality operator to denote the size.
For the remainder of this article, we assume that all automata are -free, i.e., contain no transitions. This assumption is without loss of generality as there exist efficient procedures for removing -transitions [1].
Definition 2. A path in an FA is a labeled sequence of states, where each label is a symbol from the alphabet, and each is a state in , such that for all we have . We will refer to the concatenation of symbols along the path as the path’s yield.
We say that a word is recognized by the FA if there exists a path in from some initial state to some final state with yield . Moreover, we denote with the language (set of all words) recognized by . Two FAs and are called equivalent if they accept the same language, i.e., if . Given two languages and we define their concatenation
as the language accepting all concatenations of word pairs in them. In case is a singleton, we overload the notation and simply write for brevity.
Definition 3. A state is called accessible if there exists a path from to , and co-accessible if there exists a path from to . An automaton where all states are both accessible and co-accessible is called trim.
Similarly to -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 , marked by , is an FA obtained by reversing the direction of all transitions in and swapping the initial and final states.
We denote the subroutine transforming any FA into its reverse as Reverse, and note that , i.e., the set of all reversed words from .
Definition 5. An FA is deterministic if and only if the initial state is unique, i.e., , and for every there is exactly one such that , i.e., the relation corresponds to a total function of type . An FA that is not deterministic is called nondeterministic and an FA whose reverse is deterministic is called co-deterministic.
As a shorthand, for any , we write to denote an iterative application of the transition function to the word . 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 , constructs an equivalent DFA , known as the powerset automaton. Every state , also called the powerstate, satisfies and all transitions between powerstates in satisfy the condition
Furthermore, is a powerstate containing all initial states of and is a set of powerstates containing at least one state from the final states . By construction, is a DFA with and one can easily show that .
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 for each NFA (sometimes this is referred to as canonization, and 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 from PowerConstr, which yields a valid determinization algorithm:
Definition 6. Given an FA , we call the number of states in its minimal equivalent deterministic automaton its state complexity, usually denoted as .
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 ; hence, the states and transitions in the DFA returned by the subset construction are always a subset of the states and transitions of . 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:
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 , it explores all subsets of states accessible from the powerstate (composed of initial states ) by following the labeled transitions from . Each newly found state will be placed on the stack, and for every on the stack, we search for all of its direct neighbors and place them on the stack and then remove . 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 with all possible sequences of transition matrices and terminating as soon as no new states can be produced. We will refer to the DFA obtained by applying Algorithm 1 on 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 is trim and co-deterministic, then Algorithm 1 produces the minimal DFA .
Theorem 7 gave birth to a novel determinization algorithm based on Algorithm 1, which directly produces the minimal DFA given any trim NFA as input. This algorithm is known as Brzozowski’s algorithm, defined as
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 and, for each , define a binary relation over with for all . A transition monoid is a binary relation monoid over generated by and closed under the relation composition operator with the identity relation .
It is often more convenient to think of as a monoid of matrices over the Boolean semifield closed under Boolean matrix multiplication with the identity element , such that:
Notice that the monoid is, by construction, closely related to the regular language .
Definition 9. A language is recognized by a monoid of binary relations over if there exists a surjective morphism and a subset , called an accepting subset, such that .
From the definition above it is immediately visible that recognizes the language . Indeed, if we view and as Boolean vectors we can define the accepting subset as
and a morphism for an arbitrary word
with . As a consequence, the inverse only contains words that are a yield of at least one path from to in . 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 -state Moore automaton [21] and the -state Meyer–Fischer automaton [20], both of which exhibit a state complexity of ; see Figure 1.

Figure 1. An -state Moore automaton (left) and an -state Meyer–Fischer automaton (right). Both of them are nondeterministic with a state complexity of for every .
Example 10. The blow-up occurring in a Meyer–Fischer automaton has a particularly intuitive explanation. Let denote the number of times the symbol appears in a word . Then, the language accepted by an -state can be described as
For every word , the nondeterministic Meyer–Fischer automaton guesses a prefix that ends with (or is empty), such that the number of symbols in the remaining suffix is a multiple of . To accomplish that, any deterministic counterpart of needs to keep track of all parities modulo for all occurrences of in , i.e., exactly 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:
The complexity measure corresponds directly to the determinization difficulty of the underlying automaton.
The complexity measure is algorithmically feasible to compute or estimate.
Due to the famous Myhill–Nerode theorem [14], the minimal deterministic automaton is unique up to isomorphism; hence the most straightforward attempt to assess the complexity of determinization is to consider the state complexity . Unfortunately, this approach immediately clashes with both of our principles. To illustrate the first issue, let us consider the following 1-state deterministic automaton
which is minimal and accepts the universal language , i.e., all words over the binary alphabet .
Theorem 11 (NFA Universality [12]). Given an -state NFA , deciding whether 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 , 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 be any metric, which associates a natural number with every possible FA (for example could count the states, i.e., ).
Definition 12. Let be an arbitrary NFA and let be some function satisfying for all . We say that is an -approximation of metric on if
i.e., is an upper bound with slackness specified by .
Below we focus on the particular choice for the metric—the state complexity, i.e., . 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 , it is PSPACE-hard to compute a -approximation to the state complexity.
Proof. To show PSPACE-hardness, we construct a polynomial reduction from the NFA universality problem. Let be an arbitrary NFA and let . Further, assume that there exists an algorithm that, given any NFA, produces a -approximation to its state complexity. We show that we could use such an algorithm to decide whether accepts the universal language, which is PSPACE-hard by Theorem 11.
Without loss of generality, we assume that . Next, we construct an automaton over the alphabet with states using a copy of , a copy of and two copies of as shown in Figure 2. Specifically, is the union of the following two NFAs:

Figure 2. Construction for automaton consisting of a union of two nondeterministic automata: the upper one is a connection of and using symbol , and the lower one is the connection of and 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.
We construct the first automaton as follows. Let be the 1-state minimal DFA that accepts , and let be the -state Moore automaton. Then, concatenate to by adding a -labeled transition from the unique state in to the initial state of . Then, the initial state of no longer serves as an initial state, and the single state in no longer serves as a final state.
We construct the second automaton as follows. Let be another copy of the 1-state minimal DFA that accepts . Then, concatenate to by adding a -labeled transition from all final states in to the initial state of . The unique state in no longer serves as an initial state, and no longer has any final states.
Clearly, the first automaton accepts the language while the second accepts the language . Thus, accepts . On the one hand, if is universal, then , and the union of these languages is precisely . Consequently, the state complexity of is 3. On the other hand, if is not universal, then there exists a word such that , meaning that
Consider the minimal deterministic automaton for , which we denote with . Let be the state in to which the path with the yield leads. Now, observe that the right language of is . Because has a state complexity , the state complexity of is at least . Thus, depending on whether is universal or not, the state complexity of will be either 3 or at least . Hence, any -approximation to the state complexity of satisfies
in the former case and in the latter; since for all sufficiently large , any algorithm producing a -approximation for the state complexity of would necessarily decide the universality of .
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 -state NFA into a minimal equivalent DFA with space complexity .
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 , the oracle provides access to the adjacency matrices of the powerset automaton by receiving a query and returning a binary response. A query consists of a tuple of powerstates and a symbol , and returns 1 if transition exists in , and 0 otherwise. To check for the oracle simply verifies whether
which can be clearly done in 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 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 memory.
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., RAM)2 individually on every input NFA .
Definition 15. We say that a determinization algorithm improves another determinization algorithm , i.e., , if there exists a constant such that for any FA , the number of steps required to compute using is at most times larger than the number of steps required to compute using .
Definition 15 feels quite intuitive: an algorithm is an improvement over , if and only if for any input automaton it is at least as fast as (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 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 , 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 with an explicit dead state , 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 whose reverse 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 in Figure 4 for more details).

Figure 4. Modified Meyer–Fischer automaton with an additional state (left) satisfying for with . Its reverse, (right), is deterministic.
Remark 17. Note that the ordering behaves like a lattice. Indeed, for any two determinization algorithms and one can construct an algorithm (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 by always waiting for and 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 lies within . The addition of Minimize adds a logarithmic factor (which can be bounded by ), hence the final number of steps that the subset construction uses on is within
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 and, in the second stage, it produces another subset automaton, which, by Theorem 7, coincides with the minimal DFA . Denote by the subset automaton for , then the number of steps that Brzozowski’s algorithm uses on lies within
Definition 18. A determinization algorithm is said to admit an -approximation if the metric measuring the number of steps (i.e., time complexity) of on a given input admits an -approximation (as in Definition 12).
As observed earlier, the metric 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 is universal if and only if every state in the subset automaton (produced by Algorithm 1) contains a final state from .
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 are accepting by design of Algorithm 1; hence, accepts a universal language. To show the right implication, observe that if there does exist a state generated by Algorithm 1 that does not contain a final state, then, since all states in are accessible, there exists a path with yield from to , which means that .
Lemma 20. Let be an -state Meyer–Fischer automaton. Consider the powerstate in its powerset automaton . Then, all transitions leaving in are self-loops.
Proof. Because being in the state corresponds to simultaneously being in all the states of ,3 the claim follows by observing that every state in has at least one incoming transition with label and one with . Thus, once one lands in , one will always transition back to all states in .
Equipped with these lemmas, we are now ready to discuss the main results of this section.
Theorem 21. For any polynomial , it is PSPACE-hard to compute a -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 -approximation, we again construct a polynomial reduction from the NFA universality problem. Assume that we have access to an algorithm which, given any , computes a -approximation to the size of ’s subset automaton. Let and let be the degree of the polynomial and without loss of generality assume that . Given a fixed positive integer consider an -state Meyer–Fischer automaton over . As with the -state Moore automaton, the -state Meyer–Fischer has a state complexity of . In addition, the Meyer–Fischer automaton has a unique initial state which is also the unique accepting state, as shown in the top part of Figure 3.

Figure 3. The construction of the automaton from an arbitrary NFA with an explicit dead state and the -state Meyer–Fischer automaton . All nonfinal states of are connected to the initial state of using symbol and all final states ( is the only one in ) are connected to all states of using the same symbol . In the diagram, .
Without loss of generality assume that has an explicit dead state , i.e., if some state is missing an explicit transition for some symbol , we augment with transition . In other words, ’s transition function is total.
Next, we create an automaton over the alphabet by conjoining and as follows (see Figure 3):
We add -labeled transitions from all nonfinal states of to ’s initial state . The state is no longer initial in .
We add -labeled transitions from all final states in to all states of . The final states from are no longer final in .
Next, we analyze an application of the subset construction to by breaking its computation into two stages. In the first stage, we only traverse transitions with symbols and . This corresponds exactly to running Algorithm 1 on . After the first stage is completed, i.e., after no new states can be generated, we allow Algorithm 1 to consider other symbols from . 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 —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 .
Let us observe the (incomplete) subset automaton after the first stage. We first consider the case where is universal. Due to Lemma 19, all states in the (incomplete) subset automaton contain at least one final state from . Hence, in the second stage of the subset construction, any -labeled transition leads to the powerstate , where, due to Lemma 20, we either remain forever (for -labeled transitions) or transition into the powerstate (for -labeled transitions). This means that exactly 2 additional states are produced in the second stage.
Next, we consider the case where is not universal and let be an arbitrary word not in the language. Observe that in this case
since every path with yield ends in a non-final state of , meaning that leads exclusively to in . Now consider the minimal deterministic automaton for , which we denote with and let be the state in to which the path with the yield leads. Observe that the right language of is , meaning that the number of states in satisfies .
In summary, if is universal, then the subset automaton will have exactly 2 more states than , while if is not universal, it will require at least states. Moreover, since has only states, the size of will be at most . Thus, if is universal, we have . And, if is not universal, we have . It follows that if is universal, any -approximation for will satisfy
And, if is not universal, . We choose , the degree of . If we assume that is sufficiently large then, by comparing and , we can decide the universality of .
Due to Eq. (15), the number of steps in the subset construction is proportional to by a factor of , hence a polynomial approximation for the number of steps can be converted into a polynomial approximation for .
We conclude that it is PSPACE-hard to compute a -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 in case is universal, but has to be at least in case is not. Thus, any -approximation decides universality of for any improvement of the subset construction.
Theorem 22. For any polynomial , it is PSPACE-hard to compute a -approximation for Brzozowski’s algorithm or any improvement thereof.
Proof. Let be an FA with , an arbitrary polynomial of degree , and let be some positive integer. We will construct similarly to Theorem 21, but instead of adjoining the -state Meyer–Fischer automaton we will adjoin the modified Meyer–Fischer automaton, denoted with , as presented in Figure 4. We designed in such a way that but, in contrast to the original, is co-deterministic (its reverse is given explicitly in Figure 4).
Notice that Lemma 20 also holds for , thus, analogously to Theorem 21, if is universal, no matter when we take a transition with label , we will stay forever in , which is accepting. Thus, the underlying language satisfies
Similarly, if is not universal, then the state complexity is at least due to Eq. (17).
Our goal is to show that for any universal , Brzozowski’s algorithm will not produce too many states on . To achieve that we will analyze its execution using two stages: first reversing , 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 is at most .
The first stage of Brzozowski’s algorithm corresponds to running Algorithm 1 on which is, effectively, the concatenation of with using (recall that the copy of within has no final states).
First, Algorithm 1 is launched on initial states from , but, while exploring only -labeled transitions, no new states will be created because is already deterministic. As soon as -labeled transitions are encountered, the situation changes: all -labeled transitions from lead either into the powerstate or in . In the spirit of Theorem 21 we enforce the following ordering on the execution of Algorithm 1:
Take any -transition from into and find all reachable powerstates
Take any -transition from into 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 , hence it has to terminate. Furthermore, the number of states discovered in 1. is at most , 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 -state NFA . Hence, after the first stage on we obtain some automaton satisfying
which concludes the claim.
In the second stage, Brzozowski’s algorithm executes the subset construction on , but this time the subset automaton for is the minimal DFA with exactly 3 states. Thus, if is universal, then, due to Eq. (16), the total number of steps will be proportional to at most
On the other hand, if is not universal, any algorithm will require at least many steps. Following the argument from Theorem 21, by choosing , any -approximation for Brzozowski’s algorithm (or any improvement thereof) on can be used to decide universality of .
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 , it remains PSPACE-hard to compute a -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 denote the union automaton of and from Eq. (10), made universal over the alphabet , and denote the unique state of by . Since , the state complexity of is known and is 1; the same holds for its reverse . It is easy to see that the execution path of both subset construction is equivalent between and , and the same holds for and in case of Brzozowski’s algorithm.
:::
Corollary 24. Any -approximation for the overhead of the subset construction on a given NFA , i.e., the difference , 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 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 , 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 .
Theorem 25 (Semigroup Complexity). Given an NFA , its subset automaton satisfies .
Proof. Following Algorithm 1 we conclude that since every element of is the image of at least one relation in , we have .
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 -state deterministic FAs over a binary alphabet, the syntactic monoid recognizing the same language can have size up to (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 let be its unique transition matrix. Then the bound on relies solely on the precedence graph , i.e., a directed graph with vertices and edges defined by the transition matrix .
Definition 26. Given a directed graph the cyclicity of , denoted with , is the least common multiple of cyclicities of all maximal strongly connected components of , where the cyclicity of a strongly connected component is the greatest common divisor of the lengths of all cycles in .
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 be an -state unary automaton with transition matrix . Then
Permutation Automata
An NFA is a permutation automaton if for every letter the transition relation defines a permutation of the set of states . Note that in this case 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 is commutative if all transition matrices in commute with each other. Its underlying language is closed under letter permutations, i.e., for any word and any permutation , we have . The following result follows immediately.
Proposition 28. Given a commutative automaton , define for any the transition monoid generated by as . Then:
In particular, this implies that any bound from § 6.1 can be applied individually to each unary subautomaton of .
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 is large compared to ), the semigroup complexity (and hence the determinization) will likely stay sub-exponential.
Definition 29. An Boolean matrix is -indecomposable if and only if for any non-zero Boolean (row) vector with non-zero entries it holds:
This property has a direct relation to semigroup complexity: indeed, it is easy to see that any product of arbitrary -indecomposable Boolean matrices results in a 1-block matrix. We will use the notation to denote the probability which becomes arbitrarily close to 1 as the parameter . The subsequent result highlights the key fact linking indecomposable matrices to NFAs with many transitions.
Lemma 30 (Dense Matrices) [16]. An Boolean matrix picked uniformly at random from the set of matrices with exactly non-zero entries will be -indecomposable with probability for an arbitrary .
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 be a constant, some fixed alphabet and an NFA over sampled uniformly at random from the set of all NFAs where for every the transition matrix contains at least transitions. Then, with probability it holds:
Proof. Assume that all transition matrices in are -indecomposable for some , and consider a product of arbitrary matrices from . Due to Definition 29, each row of the resulting product will have at least entries, thus we will get a 1-block matrix. Thus, all elements of with at least one zero entry will be the products of at most transition matrices. This means that the cardinality of is bounded by the number of words over the alphabet with length of at most , i.e.
By Lemma 30, with probability all randomly sampled transition matrices of will be -indecomposable with (note that our matrices have at least non-zero entries, hence we are sampling with of at least ). Thus, by performing the substitution we get
with probability . □
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 for Boolean transition matrices in . Since every state in the subset automaton corresponds to a characteristic vector over , it has to be in the image of some transition matrix for . Hence, the size of their combined images is an upper bound on the size of the subset automaton.
Lemma 32 (Range Complexity). Let be an NFA with a set of transition matrices . Then its subset automaton satisfies
where is the range of the matrix over the Boolean semifield .
Proof. Let . Consider any and let be a word such that . Then, 's characteristic vector is given by
Moreover, because this holds for any , we have
Note that the row space and the column space of a Boolean matrix have the same cardinality, i.e., for every . Applying the union bound and adding 1 to account for the initial state 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 , we define the subset complexity as
where is an arbitrary subset of the alphabet and denotes the submonoid generated by the transitions .
Essentially, subset complexity allows us to split into subautomata according to whether the symbols on the transitions are in or , 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 be an NFA and let be the DFA output by the subset construction with as input. Then, we have .
Proof. Let be arbitrary. We first show that
For any word , let be the unique decomposition where and is maximal. Furthermore, let . Similarly to the proof of Proposition 32, we consider a characteristic vector for . For clarity, we will denote transition matrices corresponding to symbols with and transition matrices which correspond to symbols with . Then, the characteristic vector can be written as
where is either the initial characteristic vector (in case , i.e., ) or an element of , since the last symbol of lies outside of . Because , there are at most choices for a vector and choices for the matrix . Thus, the total number of choices for 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 -state Moore automaton from Figure 1 with state complexity of . We define a modified -state Moore automaton as follows. Take the -state Moore automaton and replace the labels on the transitions and with a new symbol . The new automaton operates over the alphabet ; it is still nondeterministic, as shown in Figure 5 (left).

Figure 5. An -state modified Moore automaton over extended alphabet (left) and an -state modified Meyer–Fischer automaton where some labels on self loops with were swapped for (right).
Claim 1. For an -state modified Moore automaton , the following inequality holds .
Indeed, let and observe that , which means that all matrices in the transition monoid can be obtained from a product sequence of the following form
Moreover, we have that , i.e., the zero matrix and , meaning that there are at most distinct powers of and distinct powers of (counting the empty set). Hence, . Moreover, we have that because is a rank-1 matrix. Applying Theorem 34 concludes the claim.
Example 36
Let us consider the modified Meyer–Fischer automaton where we replace the labels on all but of the -labeled self-loop transitions with , as shown in Figure 5 (right).
Claim 1. For an -state modified Meyer–Fischer automaton it holds: .
To demonstrate the claim we choose and observe that the cyclicity of is 1 because it is strongly connected and has a self-loop. By applying Proposition 27 we therefore obtain . Finally, we notice that is at most since consists precisely of non-zero columns. Applying Theorem 34 concludes the claim.
We note that in Examples 35 and 36 both the initial states and the final states 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 Boolean matrix , let be the rank of over the Galois field . Then the range of satisfies
Remark 38. The rank over can be calculated using Gaussian elimination over . 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 and monoid size on the remaining symbols we get a simple upper bound on the subset complexity for any automaton .
Proposition 39 (All-but-one). Given an -state NFA , an arbitrary target symbol and any , the following holds
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 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]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]I. Baburin, R. Cotterell, An Analysis of On-the-fly Determinization of Finite-state Automata. 2023. https://arxiv.org/abs/2308.14077
- [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]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]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]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]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]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]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]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]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]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]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]J. E. Hopcroft, R. Motwani, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation. 2nd edition, Addison-Wesley, Boston, MA, USA, 2001.
- [15]S. Kiefer, Complexity of NFA to DFA minimization with binary threshold. Theoretical Computer Science Stack Exchange. https://cstheory.stackexchange.com/q/50706
- [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]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]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]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]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]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]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]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]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]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]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]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]M. Vatshelle, New width parameters of graphs. Ph.D. thesis, University of Bergen, 2012. https://www.ii.uib.no/~martinv/Papers/MartinThesis.pdf
- [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