Epichristoffel Words and Minimization of Moore Automata

Issue title: Theoretical Computer Science

Article type: Research Article

Authors: Castiglione, Giusi | Sciortino, Marinella

Affiliations: Dipartimento di Matematica e Informatica, Università di Palermo, via Archirafi, 34 - 90123 Palermo, Italy. {giusi, mari}@math.unipa.it

Note: [] Address for correspondence: Dipartimento di Matematica e Informatica, Università di Palermo, via Archirafi, 34 - 90123 Palermo, Italy

Abstract: This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft's algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft's minimization algorithm. The use of this variant makes simpler the computation of the running time and consequently the study of families of automata that represent the extremal cases of the minimization process. Indeed, such a variant allows to use the above mentioned factorization property of the epichristoffel words and their reduction trees in order to find an infinite family of Moore automata such that the execution of the algorithm is uniquely determined and tight.

DOI: 10.3233/FI-2014-1104

Journal: Fundamenta Informaticae, vol. 134, no. 3-4, pp. 319-333, 2014