We present a new framework for dealing with C∞-words, based on their left and right frontiers. This allows us to give a compact representation of them, and to describe the set of C∞-words through an infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers of C∞-words. We show that this map can be defined recursively and with no explicit reference to C∞-words. We then show that some important conjectures on C∞-words follow from analogous statements on the structure of the graph G.
Fédou, J., Fici, G. (2015). Vertical representation of C∞-words. THEORETICAL COMPUTER SCIENCE, 565(C), 90-101 [10.1016/j.tcs.2014.11.011].
Vertical representation of C∞-words
FICI, Gabriele
2015-01-01
Abstract
We present a new framework for dealing with C∞-words, based on their left and right frontiers. This allows us to give a compact representation of them, and to describe the set of C∞-words through an infinite directed acyclic graph G. This graph is defined by a map acting on the frontiers of C∞-words. We show that this map can be defined recursively and with no explicit reference to C∞-words. We then show that some important conjectures on C∞-words follow from analogous statements on the structure of the graph G.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Vertical representation of C-infty words.pdf
Solo gestori archvio
Dimensione
1.19 MB
Formato
Adobe PDF
|
1.19 MB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
