Neutral and tree sets of arbitrary characteristic

详细信息    查看全文

• 作者：Francesco Dolce<sup> ; sup><sup>francesco.dolce@u-pem.frsup> ; Dominique Perrin
• 关键词：Neutral sets ; Tree sets ; Bifix codes ; Interval exchanges ; Linear involutions
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：7 January 2017
• 年：2017
• 卷：658
• 期：part_PA
• 页码：159-174
• 全文大小：564 K
• 卷排序：658

文摘

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.