The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n2) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log2(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed by Hromkovič et al. yields a cubic algorithm. In this paper we present a sequential algorithm for the CFS construction which works in time O(n log(n) + size of the output). On a CREW PRAM the CFS construction can be performed in time O(log(n)) using O(n + (size of the output)/log(n)) processors. We also present a simpler proof of the lower bound on the number of transitions.

In this paper we investigate the average Horton-Strahler number of all possible tree-structures of binary tries. For that purpose we consider a generalization of extended binary trees where leaves are distinguished in order to represent the location of keys within a corresponding trie. Assuming a uniform distribution for those trees we prove that the expected Horton-Strahler number of a tree with α internal nodes and β leaves that correspond to a key is asymptotically given by $$\frac{4^{2\beta-\alpha}\log(\alpha)(2\beta-1)(\alpha+1)(\alpha+2){2\alpha+1\choose \alpha-1}}{8\sqrt{\pi}\alpha^{3/2}\log(2)(\beta-1)\beta{2\beta\choose \beta}^2}$$ provided that α and β grow in some fixed proportion ρ when α → ∞ . A similar result is shown for trees with α internal nodes but with an arbitrary number of keys.

We define L rational and L recognizable power series, and establish a Kleene-Schützenberger theorem for Lindenmayerian power series by showing that a power series is L rational if and only if it is L recognizable.

The aim of this paper is to show that a semi-commutation function can be expressed as the compound of a sequential transformation, a partial commutation function, and the reverse transformation. Moreover, we give a necessary and sufficient condition for the image of a regular language to be computed by the compound of two sequential functions and a partial commutation function.