String rearrangement inequalities and a total order between primitive words

DOI10.1007/978-3-031-20796-9_15MaRDI QIDQ6111479zbMATH OpenOpenAlexFDO

Authors Ruixi Luo, Taikun Zhu, Kai Jin

Publication date 3 August 2023

Published in Frontiers of Algorithmic Wisdom (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2204.11213

zbMATH Keywords

combinatorics on wordsgreedy algorithmprimitive wordsstring orderingstring rearrangement inequalities

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Abstract: We study the following rearrangement problem: Given $n$ words, rearrange and concatenate them so that the obtained string is lexicographically smallest (or largest, respectively). We show that this problem reduces to sorting the given words so that their repeating strings are non-decreasing (or non-increasing, respectively), where the repeating string of a word $A$ refers to the infinite string $AAAldots$. Moreover, for fixed size alphabet $Sigma$, we design an $O(L)$ time sorting algorithm of the words (in the mentioned orders), where $L$ denotes the total length of the input words. Hence we obtain an $O(L)$ time algorithm for the rearrangement problem. Finally, we point out that comparing primitive words via comparing their repeating strings leads to a total order, which can further be extended to a total order on the finite words (or all words).

Recommendations

• Prefix and Suffix Reversals on Strings
• Prefix and suffix reversals on strings
• On the rearrangement conjecture for generalized factor order over \(\mathbb P\)
• Suffixes, conjugates and Lyndon words
• Words over an ordered alphabet and suffix permutations

Cites work

• Cartesian and Lyndon trees
• Computing regularities in strings: a survey
• Context-free languages and primitive words
• Factorizing words over an ordered alphabet
• Fast Pattern Matching in Strings
• Free differential calculus. IV: The quotient groups of the lower central series
• Generalized de Bruijn words for primitive words and powers
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1091111 (Why is no real title available?)
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• On generalized Lyndon words
• On the language of primitive words
• Primitive words and roots of words
• Simple linear comparison of strings in V-order (extended abstract)
• String comparison and Lyndon-like factorization using V-order in linear time
• The ``runs theorem
• The equation \(a_ M=b^ Nc^ P\) in a free group

Cited in

(3)

• Permuting operations on strings and their relation to prime numbers
• scientific article; zbMATH DE number 1751384 (Why is no real title available?)
• On the Cost of Interchange Rearrangement in Strings

This page was built for publication: String rearrangement inequalities and a total order between primitive words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6111479)