Lyndon-like and V-order factorizations of strings

详细信息    查看全文

• 作者：David E. Daykin ; Jacqueline W. Daykin
• 关键词：Chen ; Duval ; Fox ; Lyndon ; Factorization ; Maximal ; String ; Word ; orderings ; lexicographic ; V-order ; B-order ; T-order
• 刊名：Journal of Discrete Algorithms
• 出版年：2003
• 出版时间：June 2003
• 年：2003
• 卷：1
• 期：3-4
• 页码：357-365
• 全文大小：186 K

文摘

We say a family of strings is an UMFF if every string has a unique maximal factorization over . Then is an UMFF iff and y non-empty imply . Let L-order denote lexicographic order. Danh and Daykin discovered V-order, B-order and T-order. Let R be L, V, B or T. Then we call r an R-word if it is strictly first in R-order among the cyclic permutations of r. The set of R-words form an UMFF. We show a large class of B-like UMFF. The well-known Lyndon factorization of Chen, Fox and Lyndon is the L case, and it motivated our work.