TY - GEN
T1 - Suffix Automata and Standard Sturmian Words
AU - Sciortino, Marinella
AU - Zamboni, Luca Q.
PY - 2007
Y1 - 2007
N2 - 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
AB - 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
UR - http://hdl.handle.net/10447/28768
M3 - Conference contribution
SN - 978-3-540-73207-5; 978-3-540-73208-2
T3 - LECTURE NOTES IN COMPUTER SCIENCE
SP - 382
EP - 398
BT - Developments in Language Theory
ER -