Ranking and Unranking k-Subsequence Universal Words

DOI10.1007/978-3-031-33180-0_4MaRDI QIDQ6134861zbMATH OpenOpenAlexFDO

Authors Duncan Adamson

Publication date 25 July 2023

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: A subsequence of a word $w$ is a word $u$ such that $u=w[i_1]w[i_2],dotsw[i_{|u|}]$, for some set of indices $1leq{i}_1<i_2<dots<i_{k}leq|w|$. A word $w$ is $k$-subsequence universal over an alphabet $Sigma$ if every word in $Sigm{a}^k$ appears in $w$ as a subsequence. In this paper, we provide new algorithms for $k$-subsequence universal words of fixed length $n$ over the alphabet $Sigma=1,2,dots,sigma$. Letting $mathcalU(n,k,sigma)$ denote the set of $n$-length $k$-subsequence universal words over $Sigma$, we provide: * an $O(nksigma)$ time algorithm for counting the size of $mathcalU(n,k,sigma)$; * an $O(nksigma)$ time algorithm for ranking words in the set $mathcalU(n,k,sigma)$; * an $O(nksigma)$ time algorithm for unranking words from the set $mathcalU(n,k,sigma)$; * an algorithm for enumerating the set $mathcalU(n,k,sigma)$ with $O(nsigma)$ delay after $O(nksigma)$ preprocessing.

Recommendations

• Ranking and unranking fixed-density necklaces and Lyndon words
• Longest alternating subsequences of \(k\)-ary words
• Longest alternating subsequences in pattern-restricted \(k\)-ary words
• Weinbaum's Conjecture on Unique Subwords of Nonperiodic Words
• Partially ordered generalized patterns and k-ary words
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• COMBINATORIAL PROPERTIES OF UNIFORMLY RECURRENT WORDS AND AN APPLICATION TO SEMIGROUPS
• Maximal Words in Sequence Comparisons Based on Subword Composition
• On the optimal asymptotic performance of universal ordering and of discrimination of individual sequences

Cites work

• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1962790 (Why is no real title available?)
• scientific article; zbMATH DE number 2051146 (Why is no real title available?)
• scientific article; zbMATH DE number 7297889 (Why is no real title available?)
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• A Survey of Combinatorial Gray Codes
• Absent subsequences in words
• An algorithm for distinguishing efficiently bit-strings by their subsequences
• Computing \(k\)-th Lyndon word and decoding lexicographically minimal de Bruijn sequence
• Nearly \(k\)-universal words -- investigating a part of Simon's congruence
• Necklaces of beads in k colors and k-ary de Bruijn sequences
• Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences
• Ranking Bracelets in Polynomial Time.
• Ranking binary unlabelled necklaces in polynomial time
• Scattered Factor-Universality of Words
• Software Descriptions with Flow Expressions
• Subword histories and Parikh matrices
• Symmetry types of periodic sequences
• Testing Simon's congruence
• The complexity of downward closure comparisons
• The height of piecewise-testable languages with applications in logical complexity

Cited in

(2)

• Ranking and unranking fixed-density necklaces and Lyndon words
• Matching patterns with variables under Simon's congruence

This page was built for publication: Ranking and Unranking k-Subsequence Universal Words

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