• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Combinatorics on words >Which Arnoux-Rauzy Words Are 2-Balanced?
【24h】

Which Arnoux-Rauzy Words Are 2-Balanced?

机译：哪些Arnoux-Rauzy单词是2平衡的？

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Arnoux-Rauzy words are one possible generalization of Stur-mian words. They are infinite words with exactly one left special factor and one right special factor of each length, those special factors being extendable with any letter in the alphabet. Sturmian words are exactly binary Arnoux-Rauzy words. We are interested here in the language of an Arnoux-Rauzy word, not in the word itself. Just as the language of a Sturmian word depends only on the associated slope, or equivalently on its continued fraction expansion, the language of an Arnoux-Rauzy word is defined by the associated directive sequence. A classical property of Sturmian words is that they are 1-balanced: any two factors u and v of the same length of a given Sturmian word contain almost the same number of occurrences of any given letter, the difference being at most 1. Actually, this turns out to be a characterization of Sturmian words: an aperiodic infinite binary word is Sturmian if and only if it is balanced. For Arnoux-Rauzy words, the situation is quite different. It was expected however that they would be C-balanced for some constant C (the maximum allowed difference in the number of occurrences), but we proved that it is not the case, constructing an Arnoux-Rauzy word which is not C-balanced for any C. This was further improved in , where a large class of such words is given. On the other hand, it is easy to construct 2-balanced infinite words that are not Arnoux-Rauzy. The question of characterizing Arnoux-Rauzy words with a given balance arises then naturally. We restrict here to 2-balance and a ternary alphabet, but even so it does not seem an easy problem. In we obtained a sufficient condition, as well as a necessary condition, both of the type: the set of prefixes of the directive sequence is in a certain rational language. We were able to obtain a characterization , at the expense of replacing C-balance with a stronger notion, strong C-balance. Also, we proved that the set of prefixes of directive sequences of 2-balanced ternary Arnoux-Rauzy words does not form a rational language. Therefore, a characterization of 2-balanced ternary Arnoux-Rauzy in terms of rational languages only is not possible.
机译：Arnoux-Rauzy单词是Stur-mian单词的一种可能概括。它们是无限长的单词，每个长度恰好有一个左特殊因子和一个右特殊因子，这些特殊因子可以与字母表中的任何字母一起扩展。 Sturmian单词恰好是二进制Arnoux-Rauzy单词。在这里，我们对Arnoux-Rauzy单词的语言感兴趣，而不对单词本身感兴趣。正如Sturmian单词的语言仅取决于关联的斜率，或等效地取决于其连续的分数扩展一样，Arnoux-Rauzy单词的语言也由关联的指令序列定义。 Sturmian单词的经典特征是它们是1平衡的：给定Sturmian单词的相同长度的任意两个因子u和v包含几乎相同数量的给定字母，出现的次数最多为1。事实证明这是Sturmian单词的一个特征：非周期无穷二值单词是Sturmian且仅当它是平衡的。用Arnoux-Rauzy的话来说，情况大不相同。但是，可以预料的是，对于某个常数C（出现次数的最大允许差异），它们将达到C平衡，但是我们证明并非如此，构造了一个Arnoux-Rauzy词，该词对于C而言不是C平衡的任何C。这在中得到了进一步改进，其中给出了大量此类单词。另一方面，构造不是Arnoux-Rauzy的2平衡无限词很容易。自然地出现了以给定的平衡来表征Arnoux-Rauzy单词的问题。我们在这里限制为2平衡和三进制字母，但是即使如此，这似乎也不是一个容易的问题。在我们获得的充分条件和必要条件中，这两种类型都是：指令序列的前缀集使用某种有理语言。我们能够获得一个特征，但以一个更强的概念C平衡代替C平衡为代价。此外，我们证明了2平衡三元Arnoux-Rauzy单词的指令序列的前缀集不构成一种有理语言。因此，不可能仅用有理语言来描述2平衡三元Arnoux-Rauzy。

著录项

  • 来源
    《Combinatorics on words》|2013年|1-2|共2页
  • 会议地点 Turku(FI)
  • 作者

    Julien Cassaigne;

  • 作者单位

    Institut de mathematiques de Luminy, case 907, 13288 Marseille Cedex 9, France;

  • 会议组织
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号