6533b831fe1ef96bd12998a9
RESEARCH PRODUCT
Combinatorics of Finite Words and Suffix Automata
Gabriele Ficisubject
Discrete mathematicsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)special factorNonlinear Sciences::Cellular Automata and Lattice GasesCombinatorics on WordAutomatonCombinatoricsCombinatorics on wordsDeterministic automatonSuffix automatonEquivalence relationQuantum finite automataSuffix automatonSuffixComputer Science::Data Structures and AlgorithmsComputer Science::Formal Languages and Automata TheoryWord (computer architecture)Mathematicsdescription
The suffix automaton of a finite word is the minimal deterministic automaton accepting the language of its suffixes. The states of the suffix automaton are the classes of an equivalence relation defined on the set of factors. We explore the relationship between the combinatorial properties of a finite word and the structural properties of its suffix automaton. We give formulas for expressing the total number of states and the total number of edges of the suffix automaton in terms of special factors of the word.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-01-01 |