Epichristoffel Words and Minimization of Moore Automata

• Autorzy: Castiglione G. , Sciortino M.

Identyfikatory

DOI

10.3233/FI-2014-1104

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

automation; combinatorics; existence theorems; tree graphs; infinity; factorization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 134, nr 3/4
• Strony: 319--333
• Opis fizyczny: Bibliogr. 17 poz., rys.

Twórcy

autor

Castiglione G.

• Dipartimento di Matematica e Informatica, Università di Palermo, via Archirafi, 34 - 90123 Palermo, Italy

autor

Sciortino M.

• Dipartimento di Matematica e Informatica, Università di Palermo, via Archirafi, 34 - 90123 Palermo, Italy

Bibliografia

• [1] J. Berstel, L. Boasson, and O. Carton. Continuant polynomials and worst-case behavior of Hopcroft’s minimization algorithm. Theor. Comput. Sci., 410:2811–2822, 2009.
• [2] J. Berstel and O. Carton. On the complexity of Hopcroft’s state minimization algorithm. In CIAA, pages 35–44, 2004.
• [3] Valérie Berthé. Fréquences des facteurs des suites sturmiennes. Theor. Comput. Sci., 165(2):295–309, 1996.
• [4] J.-P. Borel and C. Reutenauer. On christoffel classes. ITA, 40(1):15–27, 2006.
• [5] E. Calude and M. Lipponen. Minimal deterministic incomplete automata. Journal of Universal Computer Science, 3(11):1180–1193, 1997.
• [6] G. Castiglione, C. Nicaud, and M. Sciortino. A challenging family of automata for classical minimization algorithms. In M. Domaratzki and K. Salomaa, editors, CIAA, volume 6482 of Lecture Notes in Computer Science, pages 251–260. Springer, 2010.
• [7] G. Castiglione, A. Restivo, and M. Sciortino. Circular sturmian words and Hopcroft’s algorithm. Theor. Comput. Sci., 410(43):4372–4381, 2009.
• [8] G. Castiglione, A. Restivo, and M. Sciortino. On extremal cases of Hopcroft’s algorithm. Theor. Comput. Sci., 411(38-39):3414–3422, 2010.
• [9] R.L. Graham, D.E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, Reading, MA, 1989.
• [10] J.E. Hopcroft. An n log n algorithm for mimimizing the states in a finite automaton. In Theory of machines and computations (Proc. Internat. Sympos. Technion, Haifa, 1971), pages 189–196. Academic Press, New York, 1971.
• [11] J. Justin and G. Pirillo. Fractional powers in sturmian words. Theor. Comput. Sci., 255(1-2):363–376, 2001.
• [12] M. Lothaire. Algebraic Combinatorics on Words, volume 90 of Encyclopedia of Mathematics and its Applications, chapter 2. Addison-Wesley, Reading, Mass., 2002. Chapter title : SturmianWords.
• [13] E.F.Moore. Gedaken experiments on sequential machines, pages 129–153. Princeton University Press, 1956.
• [14] G. Paquin. On a generalization of christoffel words: epichristoffel words. Theor. Comput. Sci., 410(38-40):3782–3791, 2009.
• [15] N.J.A. Sloane. The On-Line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org/.
• [16] M. A. Spivak. Minimization of a Moore automaton. Cybernetics and Systems Analysis, 3:4–5, 1967.
• [17] N. Wozny and L.Q. Zamboni. Frequencies of factors in Arnoux-Rauzy sequences. Acta Arith., 96:261–278, 2001.