6533b86dfe1ef96bd12c9d1f
RESEARCH PRODUCT
Vertical Representation of C∞-words
J. FédouGabriele Ficisubject
Kolakoski wordC∞-wordsComputer Science (all)[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]directed acyclic graphComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)directed setrecursive function[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Computer Science::Formal Languages and Automata Theory[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]C∞-wordTheoretical Computer Sciencedescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2015-02-02 |