Ranking and unranking k-subsequence universal words

Duncan Adamson

doi:10.1007/978-3-031-33180-0_4

Ranking and unranking k-subsequence universal words

Duncan Adamson^*

^*Corresponding author for this work

School of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

A subsequence of a word w is a word u such that u= w[ i₁] w[ i₂], ⋯ w[ i_|_u_|], for some set of indices 1 ≤ i₁< i₂< ⋯ < i_k≤ | 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 language	English
Title of host publication	Combinatorics on words
Subtitle of host publication	14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings
Editors	Anna Frid, Robert Mercaş
Place of Publication	Cham
Publisher	Springer Nature Switzerland AG
Pages	47-59
Number of pages	13
ISBN (Electronic)	9783031331800
ISBN (Print)	9783031331794
DOIs	https://doi.org/10.1007/978-3-031-33180-0_4
Publication status	Published - 2023
Event	14th International Conference on Combinatorics on Words, WORDS 2023 - Umeå, Sweden Duration: 12 Jun 2023 → 16 Jun 2023 Conference number: 14 https://dltwords2023.cs.umu.se/index.html

Publication series

Name	Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)
Publisher	Springer
Volume	13899 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	14th International Conference on Combinatorics on Words, WORDS 2023
Abbreviated title	WORDS 2023
Country/Territory	Sweden
City	Umeå
Period	12/06/23 → 16/06/23
Internet address	https://dltwords2023.cs.umu.se/index.html

Access to Document

10.1007/978-3-031-33180-0_4

https://livrepository.liverpool.ac.uk/id/eprint/3170915Licence: CC BY

Cite this

Adamson, D. (2023). Ranking and unranking k-subsequence universal words. In A. Frid, & R. Mercaş (Eds.), Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings (pp. 47-59). (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 13899 LNCS). Springer Nature Switzerland AG. https://doi.org/10.1007/978-3-031-33180-0_4

Adamson, Duncan. / Ranking and unranking k-subsequence universal words. Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. editor / Anna Frid ; Robert Mercaş. Cham : Springer Nature Switzerland AG, 2023. pp. 47-59 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)).

@inproceedings{458669e76685407f9c989325081608ee,

title = "Ranking and unranking k-subsequence universal words",

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.",

author = "Duncan Adamson",

note = "Funding: This work was completed at, and partially funded by the University of G{\"o}ttingen.; 14th International Conference on Combinatorics on Words, WORDS 2023, WORDS 2023 ; Conference date: 12-06-2023 Through 16-06-2023",

year = "2023",

doi = "10.1007/978-3-031-33180-0_4",

language = "English",

isbn = "9783031331794",

series = "Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)",

publisher = "Springer Nature Switzerland AG",

pages = "47--59",

editor = "Anna Frid and Robert Merca{\c s}",

booktitle = "Combinatorics on words",

address = "Switzerland",

url = "https://dltwords2023.cs.umu.se/index.html",

}

Adamson, D 2023, Ranking and unranking k-subsequence universal words. in A Frid & R Mercaş (eds), Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics), vol. 13899 LNCS, Springer Nature Switzerland AG, Cham, pp. 47-59, 14th International Conference on Combinatorics on Words, WORDS 2023, Umeå, Sweden, 12/06/23. https://doi.org/10.1007/978-3-031-33180-0_4

Ranking and unranking k-subsequence universal words. / Adamson, Duncan.
Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. ed. / Anna Frid; Robert Mercaş. Cham: Springer Nature Switzerland AG, 2023. p. 47-59 (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics); Vol. 13899 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Ranking and unranking k-subsequence universal words

AU - Adamson, Duncan

N1 - Conference code: 14

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-031-33180-0_4

DO - 10.1007/978-3-031-33180-0_4

M3 - Conference contribution

AN - SCOPUS:85165605376

SN - 9783031331794

T3 - Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)

SP - 47

EP - 59

BT - Combinatorics on words

A2 - Frid, Anna

A2 - Mercaş, Robert

PB - Springer Nature Switzerland AG

CY - Cham

T2 - 14th International Conference on Combinatorics on Words, WORDS 2023

Y2 - 12 June 2023 through 16 June 2023

ER -

Adamson D. Ranking and unranking k-subsequence universal words. In Frid A, Mercaş R, editors, Combinatorics on words: 14th international conference, WORDS 2023, Umeå, Sweden, June 12–16, 2023, proceedings. Cham: Springer Nature Switzerland AG. 2023. p. 47-59. (Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and Lecture notes in bioinformatics)). Epub 2023 May 31. doi: 10.1007/978-3-031-33180-0_4