Lyndon-like and V-order factorizations of strings

David E. Daykin, Jacqueline W. Daykin

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

We say a family W of strings is an UMFF if every string has a unique maximal factorization over W. Then W is an UMFF iff xy, yz ∈ W and y non-empty imply xyz ∈ W. 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.
Original languageEnglish
Pages (from-to)357-365
Number of pages9
JournalJournal of Discrete Algorithms
Volume1
Issue number3-4
DOIs
Publication statusPublished - 01 Jun 2003
Externally publishedYes

Keywords

  • chen
  • duval
  • fox
  • lyndon
  • factorization
  • maximal
  • string
  • word
  • orderings
  • lexicographic
  • v-order
  • b-order
  • t-order

Fingerprint

Dive into the research topics of 'Lyndon-like and V-order factorizations of strings'. Together they form a unique fingerprint.

Cite this