Special factors and the combinatorics of suffix and factor automata |
| |
Authors: | Gabriele Fici |
| |
Affiliation: | Laboratoire I3S, CNRS & Université de Nice-Sophia Antipolis, 2000 route des Lucioles - 06903 Sophia Antipolis cedex, France |
| |
Abstract: | The suffix automaton (resp. factor automaton) of a finite word w is the minimal deterministic automaton recognizing the set of suffixes (resp. factors) of w. We study the relationships between the structure of the suffix and factor automata and classical combinatorial parameters related to the special factors of w. We derive formulae for the number of states of these automata. We also characterize the languages LSA and LFA of words having respectively suffix automaton and factor automaton with the minimal possible number of states. |
| |
Keywords: | Combinatorics on words Suffix automaton Factor automaton DAWG Special factors Standard Sturmian words |
本文献已被 ScienceDirect 等数据库收录! |