Automata and differentiable words

作者：Fedou Jean Marc; Fici Gabriele^*

来源：Theoretical Computer Science, 2012, 443: 46-62.

DOI：10.1016/j.tcs.2012.03.033

• Kolakoski word
• C-infinity-words
• Forbidden words
• Automata

We exhibit the construction of a deterministic automaton that, given k %26gt; 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 arbitrarily 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 C-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 whose length is polynomially bounded.

• 出版日期2012-7-20