paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Transfinite Lyndon words

超限 Lyndon 词
LMCS vol.Volume 16, Issue 42020匹配度 1/10 · 该论文研究超限 Lyndon 词及其分解,属于形式语言与组合词理论,与用户关注的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析没有直接交叉;仅标签“逻辑与自动机”存在边缘理论关联。引用 6 inbox
Olivier Carton, Luc Boasson
dblp: 2026-09-10crossref: 2026-09-10arxiv: 2026-09-10

AI 速览

一句话:将 Lyndon 词推广到超限词,证明在稠密非增条件下存在唯一 Lyndon 分解,并刻画有理词的分解形式。

本文把经典 Lyndon 词的概念推广到超限词(transfinite words),研究此类词的 Lyndon 分解问题。作者证明两个主要结果:第一,给定任意超限词,在将通常的递减条件放宽为“稠密非增”(densely non-increasing)后,存在唯一的 Lyndon 词分解;第二,附录中进一步证明有理词的这种分解具有特殊形式,并且可由描述该词的有理表达式计算得到。该工作属于形式语言与自动机理论中的组合词理论,结果均为数学证明,未涉及实验评估。

问题
如何将有限词上的 Lyndon 词及其唯一分解定理推广到超限词(具有超限序型的词)。
方法
通过引入稠密非增条件,证明超限词的 Lyndon 分解存在且唯一;并对有理词给出分解的特殊形式及基于有理表达式的计算方式。
评估
理论证明;附录给出有理词分解形式的可计算性论证。
原文摘要(Abstract)

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.

链接与引用

DOI 原文 · arXiv · PDF(开放获取) · DBLP

BibTeX
@article{abs-1809-09033,
  title = {Transfinite Lyndon words},
  author = {Olivier Carton and Luc Boasson},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 16, Issue 4},
  year = {2020},
  doi = {10.23638/lmcs-16(4:9)2020}
}