6533b826fe1ef96bd1283e86
RESEARCH PRODUCT
Automata and differentiable words
Gabriele FiciJean-marc Fédousubject
Discrete mathematicsKolakoski wordGeneral Computer ScienceC∞-wordsPowerset constructionTimed automatonPushdown automatonBüchi automatonComputer Science - Formal Languages and Automata TheoryComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)68R15AutomataTheoretical Computer ScienceCombinatoricsForbidden wordsDeterministic automatonProbabilistic automatonTwo-way deterministic finite automatonNondeterministic finite automatonC∞ -wordForbidden wordComputer Science::Formal Languages and Automata TheoryComputer Science(all)Computer Science - Discrete MathematicsMathematicsdescription
We exhibit the construction of a deterministic automaton that, given k > 0, recognizes the (regular) language of k-differentiable words. Our approach follows a scheme of Crochemore et al. based on minimal forbidden words. We extend this construction to the case of C\infinity-words, i.e., words differentiable arbitrary many times. We thus obtain an infinite automaton for representing the set of C\infinity-words. We derive a classification of C\infinity-words induced by the structure of the automaton. Then, we introduce a new framework for dealing with \infinity-words, based on a three letter alphabet. This allows us to define a compacted version of the automaton, that we use to prove that every C\infinity-word admits a repetition in C\infinity whose length is polynomially bounded.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2011-02-04 | Theoretical Computer Science |