DROPS

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}
}

Document

DOI: 10.4230/LIPIcs.ICALP.2018.66

Gray Codes and Symmetric Chains

Authors: Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract

We consider the problem of constructing a cyclic listing of all bitstrings of length 2n+1 with Hamming weights in the interval [n+1-l,n+l], where 1 <= l <= n+1, by flipping a single bit in each step. This is a far-ranging generalization of the well-known middle two levels problem (l=1). We provide a solution for the case l=2 and solve a relaxed version of the problem for general values of l, by constructing cycle factors for those instances. Our proof uses symmetric chain decompositions of the hypercube, a concept known from the theory of posets, and we present several new constructions of such decompositions. In particular, we construct four pairwise edge-disjoint symmetric chain decompositions of the n-dimensional hypercube for any n >= 12.

Cite as

Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, and Kaja Wille. Gray Codes and Symmetric Chains. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 66:1-66:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ICALP.2018.66,
  author =	{Gregor, Petr and J\"{a}ger, Sven and M\"{u}tze, Torsten and Sawada, Joe and Wille, Kaja},
  title =	{{Gray Codes and Symmetric Chains}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{66:1--66:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.66},
  URN =		{urn:nbn:de:0030-drops-90703},
  doi =		{10.4230/LIPIcs.ICALP.2018.66},
  annote =	{Keywords: Gray code, Hamilton cycle, hypercube, poset, symmetric chain}
}

Search Results

Documents authored by Sawada, Joe

Efficient Construction of Long Orientable Sequences

Abstract

Cite as

Gray Codes and Symmetric Chains

Abstract

Cite as

Thanks for your feedback!

Could not send message