Search results for "C∞-words"
showing 2 items of 2 documents
Automata and differentiable words
2011
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 ev…
Vertical Representation of C∞-words
2015
International audience; We present a new framework for dealing with C∞-words, based on their left and right frontiers. Thisallows us to give a compact representation of them, and to describe the set of C∞-words throughan infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers ofC∞-words. We show that this map can be defined recursively and with no explicit reference toC∞-words. We then show that some important conjectures on C∞-words follow from analogousstatements on the structure of the graph G.