Words, Trees and Automata Minimization

Abstract

In this paper we explore some connections between some combinatorial properties of words and the study of extremal cases of the automata minimization process. An intermediate role is played by the notion od word trees for which some properties of words are generalized. In particular, we describe an infinite family of binary automata, called word automata and constructed by using standard sturmian words and more specifically Fibonacci words, that represent the extremal case of some well known automata minimization algorithms, such as Moore’s and Hopcroft’s methods. As well as giving an overview of the main results in this context, the main purpose of this paper is to prove that, even if a recently introduced polynomial variants of Brzozowski’s algorithm is considered, such family of word automata represent the worst case for the number of steps and for its overall time complexity. This fact suggests that the standard sturmian words, and consequently the associated word automata, are able to capture some properties for which the minimization process becomes inherently more complex.