wasn't at all practical, being of non-elementary complexity. To illustrate the immense resource consumptions of that algorithm, Lombardy and Sakarovitch (2002) give some actual numbers: Notice that alone the number has 10 billion zeros when written down in decimal notation, and is already by far larger than the number of atoms in the observable universe. A much more efficient algorithm than Hashiguchi's procedure was devised by Kirsten in 2005. This algorithm runs, for a given nondeterministic finite automaton as input, within double-exponential space. Yet the resource requirements of this algorithm still greatly exceed the margins of what is considered practically feasible. This algorithm has been optimized and generalized to trees by Colcombet and Löding in 2008 , as part of the theory of regular cost functions. It has been implemented in 2017 in the tool suite Stamina. See also Generalized star height problem Kleene's algorithm — computes a regular expression (usually of non-minimal star height) for a language given by a deterministic finite automaton References Works cited (technical report version) Further reading Automata (computation) Formal languages Theorems in discrete mathematics