一句话:将 Lyndon 词推广到超限词,证明在稠密非增条件下存在唯一 Lyndon 分解,并刻画有理词的分解形式。
本文把经典 Lyndon 词的概念推广到超限词(transfinite words),研究此类词的 Lyndon 分解问题。作者证明两个主要结果:第一,给定任意超限词,在将通常的递减条件放宽为“稠密非增”(densely non-increasing)后,存在唯一的 Lyndon 词分解;第二,附录中进一步证明有理词的这种分解具有特殊形式,并且可由描述该词的有理表达式计算得到。该工作属于形式语言与自动机理论中的组合词理论,结果均为数学证明,未涉及实验评估。
In this paper, we extend the notion of Lyndon word to transfinite words. We prove two main results. We first show that, given a transfinite word, there exists a unique factorization in Lyndon words that are densely non-increasing, a relaxation of the condition used in the case of finite words. In the annex, we prove that the factorization of a rational word has a special form and that it can be computed from a rational expression describing the word.