Computer Science – Discrete Mathematics
Scientific paper
2011-02-04
Computer Science
Discrete Mathematics
Accepted for publication
Scientific paper
10.1016/j.tcs.2012.03.033
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.
Fédou Jean-Marc
Fici Gabriele
No associations
LandOfFree
Automata and Differentiable Words does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Automata and Differentiable Words, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Automata and Differentiable Words will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-491808