Suffix Automata and Standard Sturmian Words

Marinella Sciortino, Luca Q. Zamboni

Risultato della ricerca: Other chapter contribution

16 Citazioni (Scopus)

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.
Lingua originaleEnglish
Titolo della pubblicazione ospiteSuffix Automata and Standard Sturmian Words
Pagine382-398
Numero di pagine17
Volume4588
Stato di pubblicazionePublished - 2007

Fingerprint

Sturmian Words
Suffix
Automata
Prefix
Standards
Binary
Necessary Conditions
Sufficient Conditions

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cita questo

Sciortino, M., & Zamboni, L. Q. (2007). Suffix Automata and Standard Sturmian Words. In Suffix Automata and Standard Sturmian Words (Vol. 4588, pagg. 382-398)

Suffix Automata and Standard Sturmian Words. / Sciortino, Marinella; Zamboni, Luca Q.

Suffix Automata and Standard Sturmian Words. Vol. 4588 2007. pag. 382-398.

Risultato della ricerca: Other chapter contribution

Sciortino, M & Zamboni, LQ 2007, Suffix Automata and Standard Sturmian Words. in Suffix Automata and Standard Sturmian Words. vol. 4588, pagg. 382-398.
Sciortino M, Zamboni LQ. Suffix Automata and Standard Sturmian Words. In Suffix Automata and Standard Sturmian Words. Vol. 4588. 2007. pag. 382-398
Sciortino, Marinella ; Zamboni, Luca Q. / Suffix Automata and Standard Sturmian Words. Suffix Automata and Standard Sturmian Words. Vol. 4588 2007. pagg. 382-398
@inbook{5c9e135cab64455c9f3d193d814d313f,
title = "Suffix Automata and Standard Sturmian Words",
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.",
keywords = "Suffix Automata",
author = "Marinella Sciortino and Zamboni, {Luca Q.}",
year = "2007",
language = "English",
volume = "4588",
pages = "382--398",
booktitle = "Suffix Automata and Standard Sturmian Words",

}

TY - CHAP

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.

KW - Suffix Automata

UR - http://hdl.handle.net/10447/28768

M3 - Other chapter contribution

VL - 4588

SP - 382

EP - 398

BT - Suffix Automata and Standard Sturmian Words

ER -

Accesso al documento