Search results for "Sturmian words"

showing 1 items of 11 documents

Special factors and the combinatorics of suffix and factor automata

2011

AbstractThe 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.

Special factorGeneral Computer ScienceSpecial factorsFactor automatonBüchi automatonω-automatonTheoretical Computer ScienceCombinatoricsDeterministic automatonTwo-way deterministic finite automatonNondeterministic finite automatonComputer Science::Data Structures and AlgorithmsCombinatorics on wordStandard Sturmian wordsMathematicsDiscrete mathematicsCombinatorics on wordsDAWGPushdown automatonComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesSuffix automatonProbabilistic automatonSuffix automatonComputer Science::Formal Languages and Automata TheoryComputer Science(all)Theoretical Computer Science
researchProduct