Ranking and Unranking k-Subsequence Universal Words

Duncan Adamson*

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

A subsequence of a word w is a word u such that u= w[ i1] w[ i2], ⋯ w[ i|u|], for some set of indices 1 ≤ i1< i2< ⋯ < ik≤ | w|. A word w is k-subsequence universal over an alphabet Σ if every word in Σ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 Σ= { 1, 2, ⋯, σ}. Letting U(n, k, σ) denote the set of n-length k-subsequence universal words over Σ, we provide: an O(nkσ) time algorithm for counting the size of U(n, k, σ) ;an O(nkσ) time algorithm for ranking words in the set U(n, k, σ) ;an O(nkσ) time algorithm for unranking words from the set U(n, k, σ) ;an algorithm for enumerating the set U(n, k, σ) with O(nσ) delay after O(nkσ) preprocessing.

Original languageEnglish
Title of host publicationCombinatorics on Words - 14th International Conference, WORDS 2023, Proceedings
EditorsAnna Frid, Robert Mercaş
PublisherSpringer Science and Business Media
Pages47-59
Number of pages13
ISBN (Print)9783031331794
DOIs
Publication statusPublished - 2023
Event14th International Conference on Combinatorics on Words, WORDS 2023 - Umeå, Sweden
Duration: 12 Jun 202316 Jun 2023

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume13899 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Conference on Combinatorics on Words, WORDS 2023
Country/TerritorySweden
CityUmeå
Period12/06/2316/06/23

Fingerprint

Dive into the research topics of 'Ranking and Unranking k-Subsequence Universal Words'. Together they form a unique fingerprint.

Cite this