文章基本信息

标题：Transfinite Lyndon words
本地全文：下载
作者：Boasson, Luc ; Carton, Olivier
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2020
卷号：16
期号：4
页码：1-38
语种：English
出版社：Technical University of Braunschweig
摘要：In this paper, we extend the notion of Lyndon word to transfinite words. Weprove two main results. We first show that, given a transfinite word, thereexists 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 aspecial form and that it can be computed from a rational expression describingthe word.
关键词：Computer Science ; Formal Languages and Automata Theory