Words, Trees and Automata Minimization

Risultato della ricerca: Otherpeer review

1 Citazioni (Scopus)

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.
Lingua originaleEnglish
Pagine18-33
Numero di pagine16
Stato di pubblicazionePublished - 2013

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • ???subjectarea.asjc.1700.1700???

Fingerprint Entra nei temi di ricerca di 'Words, Trees and Automata Minimization'. Insieme formano una fingerprint unica.

Cita questo