License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2022.9
URN: urn:nbn:de:0030-drops-161361
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16136/
Go to the corresponding LIPIcs Volume Portal


Nellore, Abhinav ; Ward, Rachel

Arbitrary-Length Analogs to de Bruijn Sequences

pdf-format:
LIPIcs-CPM-2022-9.pdf (1.0 MB)


Abstract

Let α̃ be a length-L cyclic sequence of characters from a size-K alphabet ? such that for every positive integer m ≤ L, the number of occurrences of any length-m string on ? as a substring of α̃ is ⌊ L / K^m ⌋ or ⌈ L / K^m ⌉. When L = K^N for any positive integer N, α̃ is a de Bruijn sequence of order N, and when L ≠ K^N, α̃ shares many properties with de Bruijn sequences. We describe an algorithm that outputs some α̃ for any combination of K ≥ 2 and L ≥ 1 in O(L) time using O(L log K) space. This algorithm extends Lempel’s recursive construction of a binary de Bruijn sequence. An implementation written in Python is available at https://github.com/nelloreward/pkl.

BibTeX - Entry

@InProceedings{nellore_et_al:LIPIcs.CPM.2022.9,
  author =	{Nellore, Abhinav and Ward, Rachel},
  title =	{{Arbitrary-Length Analogs to de Bruijn Sequences}},
  booktitle =	{33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)},
  pages =	{9:1--9:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-234-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{223},
  editor =	{Bannai, Hideo and Holub, Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16136},
  URN =		{urn:nbn:de:0030-drops-161361},
  doi =		{10.4230/LIPIcs.CPM.2022.9},
  annote =	{Keywords: de Bruijn sequence, de Bruijn word, Lempel’s D-morphism, Lempel’s homomorphism}
}

Keywords: de Bruijn sequence, de Bruijn word, Lempel’s D-morphism, Lempel’s homomorphism
Collection: 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Issue Date: 2022
Date of publication: 22.06.2022
Supplementary Material: Software (Source Code): https://github.com/nelloreward/pkl archived at: https://archive.softwareheritage.org/swh:1:dir:28da4be18d03945d95e62f4acfc34f10e56b1772


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI