Computing ϵ-Free NFA from Regular Expressions in O(n log^{2}(n)) Time^{⋆}

Christian Hagenah and Anca Muscholl

Institut für Informatik, Universität Stuttgart, Breitwiesenstr. 20-22, 70565 Stuttgart, Germany

Abstract. The standard procedure to transform a regular expression to an ϵ-free NFA yields a quadratic blow-up of the number of transitions. For a long time this was viewed as an unavoidable fact. Recently Hromkovic̆ et.al. [5] exhibited a construction yielding ϵ-free NFA with O(n log^{2}(n)) transitions. A rough estimation of the time needed for their construction shows a cubic time bound. The known lower bound is Ω(n log(n)). In this paper we present a sequential algorithm for the construction described in [5] which works in time O(n log(n) + size of the output). On a CREW PRAM the construction is possible in time O(log(n)) using O(n + (size of the output)/ log(n)) processors.

1 Introduction

Among various descriptions of regular languages regular expressions are especially interesting because of their succinctness. On the other hand, the high degree of expressiveness leads to algorithmically hard problems, for example testing equivalence is PSPACE-complete. Given a regular expression we are often interested in computing an equivalent nondeterministic finite automaton without ϵ-transitions (NFA). This conversion is of interest due to some operations which can be easily performed on NFA, as for example intersection.

In this paper we present efficient sequential and parallel algorithms for converting regular expressions into small NFA. For a regular expression E we take the number of letters as the size of E, whereas the size of an NFA is measured as the number of transitions. It is known that the translation from NFA to regular expressions can yield an exponential blow-up, [3]. The other direction however can be achieved in polynomial time. One classical method for constructing NFA from regular expressions is based on position automata. This construction yields NFA of quadratic size, see e.g. [1, 2]. A substantial improvement on this construction was achieved in [5], where a refinement of position automata was shown to yield NFA with O(n log^{2}(n)) transitions. This is optimal up to a possible log(n) factor, as shown in [5] by proving a O(n log(n)) lower bound. However, the precise complexity of the conversion proposed in [5] was not investigated. A trivial estimation of the construction of [5] leads to a cubic algorithm.

⋆ Research was partly supported by the French-German project PROCOPE.

Performing the conversion form regular expressions to NFA efficiently is important from a practical viewpoint. The best one can hope for is to perform the construction in time proportional to the output size. In the present paper we propose efficient sequential and parallel algorithms for converting regular expressions to NFA. Our approach is based on the construction proposed in [5], but using a slightly different presentation. This allows us to obtain an algorithm which works in time O(n log(n) + size of the output). Therefore, our algorithm has worst-case complexity of O(n log^{2}(n)). In the parallel setting we are able to perform the construction on a CREW PRAM in O(log(n)) time by using O(n) processors for computing the description of the states of the NFA, resp. O(n log(n)) processors in the worst-case for the output NFA. Previously known was an O(log(n)) time algorithm using O(n/ log(n)) processors, which computes an NFA with ϵ-transitions, see [4]. The paper is organized as follows. The sequential algorithm is presented in Sect. 4. Basic notions on position automata are recalled in Sect. 2, whereas Sect. 3 deals with the common follow sets construction of [5].

2 Preliminaries

Let A denote a finite alphabet. We consider non-empty regular expressions over A, i.e. (bracketed) expressions E built from ϵ and the letters in A, using concatenation ·, union + and Kleene star ∗. The regular language defined by a regular expression E is denoted L(E). Finite automata are denoted as usual as A = (Q, A, q_{0}, δ, F), with Q as set of states, δ ⊆ Q×A×Q as transition relation, q_{0} as initial state and F as set of final states. The language recognized by A is denoted L(A).

For algorithmic purposes a regular expression E over A is given by some syntax tree t_{E}. The syntax tree t_{E} has leaves labelled by ϵ or a ∈ A, and the inner nodes are either binary and labelled by + or ·, or they are unary and labelled by ∗. The inner nodes of a syntax tree will be named F, G, … and we will denote them as subexpressions of E. For two subexpressions F, G of E we write F ≤ G (F < G, resp.) if F is an ancestor (a proper ancestor, resp.) of G. For a subexpression F let firststar(F) denote the largest subexpression G with G ≤ F such that G^{∗} is the parent node of G.

A subtree t of t_{E} is a connected subgraph (i.e. a tree) of t_{E}. A subtree t is called full subtree if it contains all descendants of its root. This means that a full subtree of t_{E} corresponds to a subexpression of E.

We may suppose without loss of generality that the leaves of t_{E} are labelled with pairwise distinct letters. This allows to identify the leaves of t_{E} labelled by A uniquely by their labelling. For example, for E = (a^{∗} + b)^{∗}ab^{∗} we replace A by {a_{1}, a_{2}, b_{1}, b_{2}} and E by (a_{1}^{∗} + b_{1})^{∗}a_{2}b_{2}^{∗}.

3 Position Automata

In this section we recall some basic notions related to the construction of position automata from regular expressions. We follow the definitions from [2, 5].

3.1 Positions and sets of positions

Given a regular expression E, the set pos(E) comprises all positions of E which are labelled by letters from A. According to our convention, pos(E) ⊆ A. Positions of E will be named x, y, . . ..

Lemma 1. Let E be a regular expression, n = |pos(E)|. Then we can compute in linear time an equivalent expression E′, L(E) = L(E′), such that E′ has length O(n).

The size |E| of the expression E is defined as |pos(E)|. Moreover, pos(t) and |t| are defined analogously for a subtree t of t_{E}. Throughout the paper we denote by n the size |E| of E. The lemma above says that we may assume that the size of the syntax tree t_{E} satisfies |t_{E}| ∈ O(n) = O(|pos(t_{E})|).

For a regular expression E we consider two distinguished subsets of positions, first(E) and last(E). The set first(E) ⊆ pos(E) contains all positions which can occur as first letter in some word in L(E). Similarly, last(E) contains all positions which can occur as last letter in some word in L(E). Formally:

first(E) = {x ∈ pos(E) | xA^{∗} ∩ L(E) ≠ ∅} ,
last(E) = {x ∈ pos(E) | A^{∗}x ∩ L(E) ≠ ∅} .

The sets first(E), last(E) can be computed inductively by noting that e.g. first(F + G) = first(F) ∪ first(G), first(F^{∗}) = first(F) and first(F · G) = first(F) if ϵ ∉ L(F), resp. first(F · G) = first(F) ∪ first(G) if ϵ ∈ L(F). For a given position x ∈ pos(E) let follow(x) ⊆ pos(E) contain all positions y which are immediate successors of x in some word of L(E):

follow(x) = {y ∈ pos(E) | A^{∗}xyA^{∗} ∩ L(E) ≠ ∅} .

As above, follow(x) can be defined recursively by means of follow(x, F) = follow(x) ∩ pos(F). We omit the definition here, since anyway we will not compute the sets follow(x) globally.

3.2 Automata

First, last and follow sets are the basic components of an NFA A_{E} recognizing L(E), called position automaton in [5]. Let A_{E} = (Q, A, δ, q_{0}, F) be defined by

Q = pos(E) ˙∪{q_{0}}
δ = {(q_{0}, x, x) | x ∈ first(E)} ∪ {(x, y, y) | y ∈ follow(x)}
F = \{ \begin{matrix}last(E) & if ϵ ∉ L(E) \\ last(E) ∪ \{q_{0}\} & otherwise \end{matrix}

Recall for the above definition that pos(E) ⊆ A. The following equivalence is easy to check:

Proposition 2. For every regular expression E we have L(A_{E}) = L(E).

The construction above yields ϵ-free automata with n + 1 states and O(n^{2}) transitions. In [5] a refined construction was presented, based on the idea of a system of common follow sets (CFS system), which is defined as follows:

Definition 3 ([5]). Let E be a regular expression. A CFS system S for E is given as S = (dec(x))_{x∈pos(E)}, where dec(x) ⊆ P(pos(E)) is a decomposition of follow(x):

follow(x) = ⋃_{C∈dec(x)} C .

Let C_{S} = {first(E)} ∪ ⋃_{x∈pos(E)} dec(x). The CFS automaton A_{S} associated with S is defined as A_{S} = (Q, A, q_{0}, δ, F) where

Q = C_{S} × {0, 1}
q_{0} = \{ \begin{matrix}(first(E), 1) & if ϵ ∈ L(E) \\ (first(E), 0) & otherwise \end{matrix}
δ = {(C, f), x, (C′, f′)) | x ∈ C, C′ ∈ dec(x) and f′ = 1 ⇔ x ∈ last(E)}
F = C_{S} × {1}

Lemma 4. Let E be a regular expression and let S be a CFS system for E. Then the CFS automaton A_{S} recognizes L(E).

It is shown in [5] how to obtain a CFS system S for a given regular expression E such that |C_{S}| ∈ O(n), ∑_{C∈C_{S}} |C| ∈ O(n log n) and |dec(x)| ∈ O(log n) for all x ∈ pos(E). This yields a CFS automaton with O(n) states and O(n log^{2}(n)) transitions.

4 Computing a Common Follow Sets System

4.1 Properties of follow sets

The running time of our algorithm relies heavily on some structural properties of follow sets which are discussed in the following.

Lemma 5. Let E be a regular expression and let F, G be subexpressions with E ≤ F ≤ G. Then we have:

1. first(F) ∩ first(G) ≠ ∅ implies first(G) ⊆ first(F).

2. F ≤ H ≤ G and ∅ ≠ first(G) ⊆ first(F) implies first(G) ⊆ first(H) ⊆ first(F).

3. x ∈ pos(G) \ first(G) implies x ∉ first(F).

The proof of the lemma is a straightforward application of the inductive definition. An analogous lemma can be also stated for last sets.

The next lemma deals with the relation between follow sets and a decomposition of the syntax tree, which will be used recursively in the definition of the CFS system. For simplifying the notation we will denote for x ∈ pos(E), E ≤ F, the set follow(x) ∩ pos(F) by follow_{F} (x). Analogously, follow_{t}(x) denotes the set follow(x) ∩ pos(t) for a subtree t.

Lemma 6. Given a regular expression E, a syntax tree t_{E} and subexpressions F, G with E < F < G. Let t, t′ be subtrees of t_{E} such that pos(t) ⊆ pos(F)\pos(G) and pos(t′) ⊆ pos(G). Then we have for all x, x′, y ∈ pos(E):

1. follow_{F} (x) = ∅ for all x ∈ pos(t′) \ last(G);

2. follow_{F} (x) = follow_{F} (x′) for all x, x′ ∈ pos(t′) ∩ last(G);

3. follow_{t′}(y) = first(G) ∩ pos(t′) for all y ∈ pos(t) with follow_{t′}(y) ≠ ∅.

4.2 Recursive definition of CFS systems

The CFS system defined in [5] is based on a divide-and-conquer construction. Consider a subtree t of t_{E} and let F denote the root of t. Let x ∈ pos(t). If |t| = 1 then we define

C_{0} = follow_{t}(x) = follow(x) ∩ {x}, dec(x, t) = {C_{0}} .

Suppose now that |t| > 1. Then let t_{1} be a subtree of t such that 1/3|t| ≤ |t_{1}| ≤ 2/3|t| and let t_{2} = t \ t_{1}. Let F_{1} denote the root of t_{1}. Clearly, for every position x ∈ pos(t) we have follow_{t}(x) = follow_{t_{1}}(x) ˙∪ follow_{t_{2}}(x). We distinguish two cases, depending on x ∈ pos(t_{1}) or x ∈ pos(t_{2}).

i) Let x ∈ pos(t_{1}). If x ∉ last(F_{1}) then by Lem. 6 we have follow_{t_{2}}(x) = ∅. Otherwise, for x ∈ last(F_{1}) then again by Lem. 6 we have follow_{t_{2}}(x) = follow_{t_{2}}(x′) for all x′ ∈ last(F_{1}) ∩ pos(t_{1}). Let C_{1} = follow_{t_{2}}(x′) for some x′ ∈ pos(t_{1}) ∩ last(F_{1}) and define dec(x, t) as

dec(x, t) = \{ \begin{matrix}dec(x, t_{1}) & if x ∉ last(F_{1}) \\ dec(x, t_{1}) ∪ \{C_{1}\} & otherwise \end{matrix}

ii) Let x ∈ pos(t_{2}). If follow_{t_{1}}(x) ≠ ∅ then we have follow_{t_{1}}(x) = first(F_{1}) ∩ pos(t_{1}) by Lem. 6. Let C_{2} = first(F_{1}) ∩ pos(t_{1}) and define dec(x, t) as

dec(x, t) = \{ \begin{matrix}dec(x, t_{2}) & if follow_{t_{1}}(x) = ∅ \\ dec(x, t_{2}) ∪ \{C_{2}\} & otherwise \end{matrix}

It can be easily verified that dec(x, t) is a decomposition^{1} of follow_{t}(x), i.e. follow_{t}(x) = ⋃_{C∈dec(x,t)} C. Hence, we obtain a CFS system C(t) restricted to t, where

C(t) = ⋃{dec(x, t) | x ∈ pos(t)} = {C | C ∈ dec(x, t) for some x ∈ pos(t)} .

Note that |C(t)| ≤ |C(t_{1})| + |C(t_{2})| + 2. This yields |C(t)| ≤ 3|t| − 2. Similarly, the following estimations can be easily verified (see also Lem. 4 of [5]):

∑_{C∈C(t)} |C| ≤ 2|t| log(|t|) + 1 and
|dec(x, t)| ≤ 2 log(|t|) + 1, for all x ∈ pos(t) .

1 In [5] the corresponding set ⋃_{C∈dec(x,t)} C is just a subset of follow_{t}(x). Having equality here simplifies the recursive definition and the correctness proof of the decomposition.

5 A Sequential O(n log(n)) Algorithm for Computing a Common Follow Sets System

We consider now the computation of the sets defined in the previous section. For C_{0} = follow(x) ∩ {x} we can determine whether x ∈ follow(x) by checking whether x ∈ last(S) ∩ first(S) for S = firststar(x). For the recursion step we have to determine C_{1}, C_{2} with

C_{1} = follow_{t_{2}}(x) and C_{2} = first(F_{1}) ∩ pos(t_{1}) .

We want to compute both C_{1}, C_{2} and the positions x ∈ pos(t) to which C_{1} or C_{2} is added in linear time, i.e. in time O(|t|). As shown below, the computation of C_{1} reduces to computing a union of first sets restricted to pos(t_{2}). This yields two problems: First we need an efficient way to compute intersections of first sets with a given set of positions. Second, the union of restricted first sets has to be disjoint. The solution to both problems will rely on a suitable data structure for first sets. Before discussing the data structure let us consider the set C_{1} in more detail^{2}.

Definition 7. Let E ≤ F be regular expressions. We define fnext(F) ⊆ pos(E) as

fnext(F) = \{ \begin{matrix}first(G) & if F · G is the parent node of F \\ first(F) & if F^{∗} is the parent node of F \\ ∅ & otherwise \end{matrix}

Analogously, lprev(F) is defined by replacing first by last and by requiring that G · F is the parent node of F.

Using the fnext operator we are able to express follow sets as unions of first sets. Compared with Lem. 3 in [5] we need for expressing follow_{t_{2}}(x) at most one first set which is not contained in F. Of course, this is necessary in order to be able to determine C_{1} in time O(|t|):

Proposition 8. Let E be a regular expression with E ≤ F < F_{1} and let t_{E} be a syntax tree of E. Let t_{2} be a subtree with root F and pos(t_{2}) ∩ pos(F_{1}) = ∅ and consider a position x ∈ last(F_{1}). Then we have

follow_{t_{2}}(x) = ⋃_{G∈G}(fnext(G) ∩ pos(t_{2}))

where the union is taken over

G = {G | last(G) ⊇ last(F_{1}) and (F < G ≤ F_{1} or G = firststar(F))} .

2 In the definition below fnext(F) corresponds to first(fnext(F)) in [5].

Proof: Note that for every G ≤ F_{1} with last(F_{1}) ⊆ last(G) we have fnext(G) ∩ pos(t_{2}) ⊆ follow_{t_{2}}(x). Conversely, consider a position y ∈ follow_{t_{2}}(x) with y ∉ fnext(G), for all F < G ≤ F_{1} with last(F_{1}) ⊆ last(G). Hence, there exists some node G, E ≤ G ≤ F, with y ∈ fnext(G) and last(F_{1}) ⊆ last(G). Clearly, the parent node of G is G^{∗} (otherwise, fnext(G) ∩ pos(t_{2}) = ∅), thus y ∈ first(G) ∩ pos(t_{2}). If G = firststar(F) then we are done. Otherwise G < H = firststar(F). In this case it is not difficult to verify using Lem. 5 that for all G < H with first(G) ∩ pos(t_{2}) ≠ ∅ we also have first(G) ∩ pos(t_{2}) = first(H) ∩ pos(t_{2}). Therefore, y ∈ first(H) ∩ pos(t_{2}). □

Our algorithm is based on a suitable order on positions of E, which allows manipulating first sets efficiently. We use an array called firstdata such that for each subexpression F of E the set first(F) is a subinterval of firstdata.The crucial point is the order of positions within firstdata. Consider a fixed syntax tree t_{E} of E. We first define a forest F by deleting all edges from nodes labelled F · G to the child labelled G, whenever ϵ ∉ L(F). Let F = {T_{1}, …, T_{k}} be the forest thus obtained, then we denote the trees T_{i} as first-trees. Note that each first(F) is the union of all first(F′) with F < F′ where F′ belongs to the same first-tree as F.

We define a total order on F as follows. For 1 ≤ i ≠ j ≤ k let T_{i} ≺ T_{j} whenever the roots F_{i}, F_{j} of T_{i}, resp. T_{j} satisfy

– either F_{j} < F_{i}, i.e. F_{j} is an ancestor of F_{i},

– or F_{i} and F_{j} are incomparable w.r.t. < and F_{i} lies to the right of F_{j}.

The order ≺ corresponds thus to a reversed preorder traversal of t_{E}, i.e. right child—left child—parent node.

Suppose that after renaming F = {T_{1}, …, T_{k}} with T_{i} ≺ T_{j} for all i < j. The array firstdata is given as fdata(T_{1}) ⋯ fdata(T_{k}), with fdata(T_{i}) being the list of positions corresponding to the yield of T_{i}. Moreover, by a preorder traversal of each T_{i} we can determine for each subexpression F of T_{i} the subinterval of fdata(T_{i}) corresponding to first(F). The set first(F) is described by its starting position fstart(F) within fdata(T_{i}) and its length flength(F) = |first(F)|.

Remark 9. (i) Let F, G be subexpressions of E. Then we have ∅ ≠ first(F) ⊆ first(G) if and only if fstart(G) ≤ fstart(F) and fstart(G)+flength(G) ≥ fstart(F)+ flength(F), i.e. if the subinterval corresponding to first(G) includes the subinterval corresponding to first(F). Moreover, firstdata allows to determine the intersection first(F) ∩ pos(t) in O(|t|) time, where F is a subexpression and t is subtree of t_{E} (described as set of positions in increasing order).

(ii) A similar data structure lastdata can be defined for the last sets.

We are now ready to describe an algorithm UnionFirst for the following problem. Given subexpressions F, F_{1} of E with F < F_{1} and subtrees t, t_{2} of F, resp. a subtree t_{1} of F_{1}, where t = t_{1} ˙∪ t_{2}, pos(F_{1}) ∩ pos(t_{2}) = ∅, and a position x ∈ last(t_{1}). We want to compute the set C = follow_{t_{2}}(x). Recall from Prop. 8 that

C = ⋃_{G∈G}(fnext(G) ∩ pos(t_{2})) ,

with G ∈ G if and only if last(F_{1}) ⊆ last(G), and either F < G ≤ F_{1} or G = firststar(F).

function UnionFirst (node F_{1}, tree t_{2}) : nodelist; var rootlist, tocheck: nodelist; G: node; begin rootlist := nil; tocheck := nil; G := F_{1}; while (G ≠ root(t_{2}) and last(F_{1}) ⊆ last(G)) do

begin

A := parent expression of G; if A = G^{∗} then

rootlist := rootlist \ {H | H ∈ tocheck and first(H) ⊆ first(G)}; rootlist := rootlist ∘ G; tocheck := {G}; else if A = G · H then

if ϵ ∈ L(G) then rootlist := rootlist ∘H; else rootlist := H∘ rootlist endif; tocheck := tocheck ∪ {H};

endif; G := A; endwhile; return(rootlist); end

The proof of the next proposition is omitted for lack of space.

Proposition 10. Let F, F_{1} be subexpressions of E, E ≤ F < F_{1}, and let t_{E} be a syntax tree. Let t_{1} be a subtree with root F_{1} and let t_{2} be a subtree with root F and pos(F_{1}) ∩ pos(t_{2}) = ∅. Let x ∈ last(t_{1}) be a position and let G be defined as above. Then UnionFirst(F_{1}, t_{2}) yields a list rootlist = (H_{1}, …, H_{l}) of (names of) subexpressions of E satisfying the following:

1. ⋃_{i=1}^{l} first(H_{i}) = ⋃_{G∈G,G≠firststar(F)} fnext(G).

Moreover, first(H_{i})∩ first(H_{j}) = ∅ for all i ≠ j.

2. Let T (H_{i}) denote the first-tree in the forest F containing H_{i}. Then T (H_{i}) ⪯ T (H_{j}) for all 1 ≤ i < j ≤ k. Moreover, if T (H_{i}) = T (H_{j}) then H_{i} precedes H_{j} w.r.t. preorder (in t_{E}).

3. UnionFirst(F_{1}, t_{2}) runs in O(|t_{2}|) steps.

Remark 11. Given the assertion of Prop. 10 it is not hard to verify that the set ⋃_{G∈G}(fnext(G) ∩ pos(t_{2})) can be computed in O(|t_{2}|) steps using rootlist and firstdata. More precisely, we can precompute in time O(|t_{2}|) a list fdata(t_{2}) corresponding to pos(t_{2}) sorted as firstdata. Next, we scan rootlist and fdata(t_{2}) in parallel, building the intersection. Hereby we use Rem. 9 in order to determine in constant time whether a position belongs to a set first(G). Note that rootlist has at most |t_{2}| elements, since the while loop in UnionFirst is executed at most |t_{2}| times. Finally, if S = firststar(F) is defined we can check whether last(F_{1}) ⊆ last(S) in O(1) time and compute first(S) ∩ pos(t_{2}) in time O(|t_{2}|).

Theorem 12. Given a regular expression E and a syntax tree t_{E} for E of size O(|E|) = O(n). We can compute a CFS system S for E in time O(n log(n)). Therefore, we can compute an NFA A_{S} for E of size |A_{S}| in time O(n log(n) + |A_{S}|). The worst-case complexity of the algorithm is thus O(n log^{2}(n)).

Proof: Recall the recursive definition of dec(x, t) given in Sect. 4.2. For a position x ∈ pos(t_{1}) we test whether x ∈ last(F_{1}) in constant time (using lastdata), whereas C_{1} = follow_{t_{2}}(x) can be computed in time O(|t_{2}|). The case where x ∈ pos(t_{2}) is dual. Here, the set C_{2} = first(F_{1})∩pos(t_{1}) can be determined in constant time, whereas determining which x ∈ pos(t_{2}) satisfy follow_{t_{1}}(x) ≠ ∅ requires O(|t_{1}|) steps. To see this, note that for a position y ∈ C_{2} we have {x ∈ pos(t_{2}) | follow_{t_{1}}(x) ≠ ∅} = precede(y) ∩ pos(t_{2}), where precede(y) is defined as the dual of follow(y), i.e., precede(y) = {x | A^{∗}xyA^{∗} ∩ L(E) ≠ ∅}. Moreover, by duality we have precede(y) ∩ pos(t_{2}) = ⋃_{G∈G}(lprev(G) ∩ pos(t_{2})), with G ∈ G if first(F_{1}) ⊆ first(G), and either F < G ≤ F_{1} or G = firststar(F).

Therefore, we can compute in time O(|t|) the sets dec(x, t) from dec(x, t_{1}) and dec(x, t_{2}) for all positions x of t. Hence, our algorithm runs in time O(n log(n)). Finally, outputting the transitions of the NFA A_{S} is possible in time O(|A_{S}|).

□

In the parallel setting we have again an output-size optimal algorithm on a CREW PRAM, as stated below. For lack of space we omit the proofs.

Theorem 13. Given a regular expression E and a syntax tree t_{E} for E of size O(|E|) = O(n). We can compute a CFS system S for E on a CREW PRAM in time O(log(n)) using O(n) processors. Therefore, we can compute an NFA A_{S} for E of size |A_{S}| in time O(log(n)) using O(n + |A_{S}|/ log(n)) processors (i.e., O(n log(n)) processors in the worst case).

Acknowledgment: We thank Volker Diekert for many comments and contributions and to the anonymous referees for suggestions which helped improving the presentation.

References

1. G. Berry and R. Sethi. From regular expressions to deterministic automata. Theoretical Computer Science, 48:117–126, 1986.

2. A. Brüggemann-Klein. Regular expressions into finite automata. Theoretical Computer Science, 120:197–213, 1993.

3. A. Ehrenfeucht and P. Zeiger. Complexity measures for regular expressions. Journal of Computer and System Sciences, 12:134–146, 1976.

4. A. Gibbons and W. Rytter. Efficient Parallel Algorithms. Cambridge University Press, 1989.

5. J. Hromkovic̆, S. Seibert, and T. Wilke. Translating regular expressions into small ϵfree nondeterministic finite automata. In Proc. of the 14th Ann. Symp. on Theor. Aspects of Comp. Sci. (STACS’97), no. 1200 in LNCS, p. 55–66, 1997. Springer.