Scholarlink

The Nyldon factorization is a string factorization that is a non-decreasing product of Nyldon words. Nyldon words and Nyldon factorizations are recently defined combinatorial objects inspired by the well-known Lyndon words and Lyndon factorizations. In this paper, we investigate the Nyldon factorization of several words. First, we fully characterize the Nyldon factorizations of the (finite) Fibonacci and the (finite) Thue-Morse words. Moreover, we show that there exists a non-decreasing product of Nyldon words that is a factorization of the infinite Thue-Morse word.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Nyldon Factorization of Thue-Morse Words and Fibonacci Words

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Kaisei Kishi,
  • Kazuki Kai,
  • Yuto Nakashima,
  • Shunsuke Inenaga,
  • Hideo Bannai

摘要

The Nyldon factorization is a string factorization that is a non-decreasing product of Nyldon words. Nyldon words and Nyldon factorizations are recently defined combinatorial objects inspired by the well-known Lyndon words and Lyndon factorizations. In this paper, we investigate the Nyldon factorization of several words. First, we fully characterize the Nyldon factorizations of the (finite) Fibonacci and the (finite) Thue-Morse words. Moreover, we show that there exists a non-decreasing product of Nyldon words that is a factorization of the infinite Thue-Morse word.