Search Results

Documents authored by Gabrić, Daniel

Document
DOI: 10.4230/LIPIcs.CPM.2024.15
Efficient Construction of Long Orientable Sequences

Authors: Daniel Gabrić and Joe Sawada

Published in: LIPIcs, Volume 296, 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)

Abstract
An orientable sequence of order n is a cyclic binary sequence such that each length-n substring appears at most once in either direction. Maximal length orientable sequences are known only for n ≤ 7, and a trivial upper bound on their length is 2^{n-1} - 2^{⌊(n-1)/2⌋}. This paper presents the first efficient algorithm to construct orientable sequences with asymptotically optimal length; more specifically, our algorithm constructs orientable sequences via cycle-joining and a successor-rule approach requiring O(n) time per bit and O(n) space. This answers a longstanding open question from Dai, Martin, Robshaw, Wild [Cryptography and Coding III (1993)]. Our sequences are applied to find new longest-known orientable sequences for n ≤ 20.
Cite as

Daniel Gabrić and Joe Sawada. Efficient Construction of Long Orientable Sequences. In 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 296, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gabric_et_al:LIPIcs.CPM.2024.15,
  author =	{Gabri\'{c}, Daniel and Sawada, Joe},
  title =	{{Efficient Construction of Long Orientable Sequences}},
  booktitle =	{35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)},
  pages =	{15:1--15:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-326-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{296},
  editor =	{Inenaga, Shunsuke and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2024.15},
  URN =		{urn:nbn:de:0030-drops-201255},
  doi =		{10.4230/LIPIcs.CPM.2024.15},
  annote =	{Keywords: orientable sequence, de Bruijn sequence, concatenation tree, cycle-joining, universal cycle}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact