Neutral and tree sets of arbitrary characteristic

Abstract : We study classes of minimal sets defined by restrictions on the possible extensions of the words. These sets generalize the previously studied classes of neutral and tree sets by relaxing the condition imposed on the empty word and measured by an integer called the characteristic of the set. We present several enumeration results holding in these sets of words. These formulae concern return words and bifix codes. They generalize formulae previously known for Sturmian sets or more generally for tree sets. We also give two geometric examples of this class of sets, namely the natural coding of some interval exchange transformations and the natural coding of some linear involutions.
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01367718
Contributor : Francesco Dolce <>
Submitted on : Friday, September 16, 2016 - 3:37:52 PM
Last modification on : Friday, April 12, 2019 - 10:18:10 AM
Long-term archiving on : Saturday, December 17, 2016 - 2:59:57 PM

File

NeutralAndTreeSetsOfArbitraryC...
Files produced by the author(s)

Identifiers

Citation

Francesco Dolce, Dominique Perrin. Neutral and tree sets of arbitrary characteristic. Theoretical Computer Science, Elsevier, 2017, 658 (part A), pp.159-174. ⟨10.1016/j.tcs.2016.01.008⟩. ⟨hal-01367718⟩

Share

Metrics

Record views

278

Files downloads

168