Blumer et al. showed (cf. [3,2]) that the suffix automaton of a word w must have at least |w|+1 states and at most 2|w|-1 states. In this paper we characterize the language L of all binary words w whose minimal suffix automaton S(w) has exactly |w| + 1 states; they are precisely all prefixes of standard Sturmian words. In particular, we give an explicit construction of suffix automaton of words that are palindromic prefixes of standard words. Moreover, we establish a necessary and sufficient condition on S(w) which ensures that if w ∈ L and a ∈ {0, 1} then wa ∈ L. By using such a condition, we show how to construct the automaton S(wa) from S(w). More generally, we provide a simple construction that by starting from an automaton recognizing all suffixes of a word w over a finite alphabet A, allows to obtain an automaton that recognizes the suffixes of wa, a ∈ A

SCIORTINO, M., ZAMBONI, L.Q. (2007). Suffix Automata and Standard Sturmian Words. In T. Harju, J. Karhumäki, A. Lepistö (a cura di), Developments in Language Theory (pp. 382-398). Springer [10.1007/978-3-540-73208-2_36].

Suffix Automata and Standard Sturmian Words

SCIORTINO, Marinella;
2007

Abstract

Blumer et al. showed (cf. [3,2]) that the suffix automaton of a word w must have at least |w|+1 states and at most 2|w|-1 states. In this paper we characterize the language L of all binary words w whose minimal suffix automaton S(w) has exactly |w| + 1 states; they are precisely all prefixes of standard Sturmian words. In particular, we give an explicit construction of suffix automaton of words that are palindromic prefixes of standard words. Moreover, we establish a necessary and sufficient condition on S(w) which ensures that if w ∈ L and a ∈ {0, 1} then wa ∈ L. By using such a condition, we show how to construct the automaton S(wa) from S(w). More generally, we provide a simple construction that by starting from an automaton recognizing all suffixes of a word w over a finite alphabet A, allows to obtain an automaton that recognizes the suffixes of wa, a ∈ A
Settore INF/01 - Informatica
978-3-540-73207-5
978-3-540-73208-2
SCIORTINO, M., ZAMBONI, L.Q. (2007). Suffix Automata and Standard Sturmian Words. In T. Harju, J. Karhumäki, A. Lepistö (a cura di), Developments in Language Theory (pp. 382-398). Springer [10.1007/978-3-540-73208-2_36].
File in questo prodotto:
File Dimensione Formato  
LNCS2007_DLT.pdf

Solo gestori archvio

Tipologia: Versione Editoriale
Dimensione 533.03 kB
Formato Adobe PDF
533.03 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10447/28768
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 17
social impact