Ranking and Unranking k-Subsequence Universal Words

DOI10.1007/978-3-031-33180-0_4arXiv2304.04583OpenAlexW4381303907MaRDI QIDQ6134861FDOQ6134861

Authors: Duncan Adamson 

Publication date: 25 July 2023

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

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.

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

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

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

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

Cited In (2)

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

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)