Epichristoffel Words and Minimization of Moore Automata

Risultato della ricerca: Articlepeer review

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.
Lingua originaleEnglish
pagine (da-a)319-333
Numero di pagine15
RivistaFundamenta Informaticae
Volume134
Stato di pubblicazionePublished - 2014

All Science Journal Classification (ASJC) codes

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.2600.2602???
  • ???subjectarea.asjc.1700.1710???
  • ???subjectarea.asjc.1700.1703???

Fingerprint

Entra nei temi di ricerca di 'Epichristoffel Words and Minimization of Moore Automata'. Insieme formano una fingerprint unica.

Cita questo