Minimisation of acyclic deterministic automata in linear time (Q1190464)

A deterministic automaton is acyclic if the underlying graph is acyclic. Two automata are said to be equivalent if and only if they recognise the same language. If \(A\) is an automaton there exists an unique automaton \(M\) minimal by the number of states, recognizing the same language. An automaton with no pair of equivalent states is minimal. The minimal automaton for a given language \(L\) is the unique automaton with the smallest number of states among those recognizing \(L\). The author presents a linear algorithm for the minimization of acyclic automata. This algorithm can be used, in particular, on automaton representing lexicons.