Document Open Access Logo

Arbitrary-Length Analogs to de Bruijn Sequences

Authors Abhinav Nellore , Rachel Ward

PDF
Thumbnail PDF

File

LIPIcs.CPM.2022.9.pdf
  • Filesize: 0.95 MB
  • 20 pages

Document Identifiers

Author Details

Abhinav Nellore
  • Oregon Health & Science University, Portland, OR, USA
Rachel Ward
  • The University of Texas at Austin, Austin, TX, USA

Acknowledgements

We thank Arie Israel, Štěp{á}n Holub, Joe Sawada, Jeffrey Shallit, and the anonymous reviewers for the 33rd Annual Symposium on Combinatorial Pattern Matching for their helpful feedback on various iterations of this manuscript. AN thanks the Oden Institute for Computational Engineering & Sciences at the University of Texas at Austin for hosting him as a visiting scholar as part of the J. Tinsley Oden Faculty Fellowship Research Program when the work contained here was initiated.

Cite As Get BibTex

Abhinav Nellore and Rachel Ward. Arbitrary-Length Analogs to de Bruijn Sequences. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CPM.2022.9

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.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial algorithms
  • Mathematics of computing → Combinatorics on words
Keywords
  • de Bruijn sequence
  • de Bruijn word
  • Lempel’s D-morphism
  • Lempel’s homomorphism

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

Supplementary Materials

References

  1. Abbas Alhakim and Mufutau Akinwande. A recursive construction of nonbinary de Bruijn sequences. Designs, Codes and Cryptography, 60(2):155-169, 2011. Google Scholar
  2. Abbas Alhakim and Maher Nouiehed. Stretching de Bruijn sequences. Designs, Codes and Cryptography, 85(2):381-394, 2017. Google Scholar
  3. Abbas Alhakim, Evan Sala, and Joe Sawada. Revisiting the prefer-same and prefer-opposite de Bruijn sequence constructions. Theoretical Computer Science, 852:73-77, 2021. Google Scholar
  4. Abbas M Alhakim. A simple combinatorial algorithm for de Bruijn sequences. The American Mathematical Monthly, 117(8):728-732, 2010. Google Scholar
  5. Gal Amram, Yair Ashlagi, Amir Rubin, Yotam Svoray, Moshe Schwartz, and Gera Weiss. An efficient shift rule for the prefer-max de Bruijn sequence. Discrete Mathematics, 342(1):226-232, 2019. Google Scholar
  6. Fred S. Annexstein. Generating de Bruijn sequences: An efficient implementation. IEEE Transactions on Computers, 46(2):198-200, 1997. Google Scholar
  7. Charles Philip Brown. Sanskrit Prosody and Numerical Symbols Explained. Trübner & Company, 1869. Google Scholar
  8. PR Bryant, FG Heath, and RD Killick. Counting with feedback shift registers by means of a jump technique. IRE Transactions on Electronic Computers, pages 285-286, 1962. Google Scholar
  9. John Burns and Chris J Mitchell. Coding Schemes for Two-Dimensional Position Sensing. Hewlett-Packard Laboratories, Technical Publications Department, 1992. Google Scholar
  10. Michael Burrows and David J Wheeler. A block-sorting lossless data compression algorithm. Technical report, Systems Research Center, 1994. Google Scholar
  11. Camille Flye Sainte-Marie. http://henripoincare.fr/s/correspondance/item/14609. Accessed: 2021-07-23.
  12. Taejoo Chang, Bongjoo Park, Yun Hee Kim, and Iickho Song. An efficient implementation of the D-homomorphism for generation of de Bruijn sequences. IEEE Transactions on Information Theory, 45(4):1280-1283, 1999. Google Scholar
  13. Zuling Chang, Martianus Frederic Ezerman, Pinhui Ke, and Qiang Wang. General criteria for successor rules to efficiently generate binary de Bruijn sequences. arXiv preprint, 2019. URL: http://arxiv.org/abs/1911.06670.
  14. Fan Chung, Persi Diaconis, and Ron Graham. Universal cycles for combinatorial structures. Discrete Mathematics, 110(1-3):43-59, 1992. Google Scholar
  15. ZD Dai, KM Martin, MJB Robshaw, and PR Wild. Orientable sequences. In Institute of Mathematics and Its Applications Conference Series, volume 45, pages 97-97. Oxford University Press, 1993. Google Scholar
  16. NG de Bruijn. In memoriam T. van Aardenne-Ehrenfest, 1905-1984. Nieuw Archief voor Wiskunde, 4(2):235-236, 1985. Google Scholar
  17. Nicolaas Govert De Bruijn. A combinatorial problem. In Proc. Koninklijke Nederlandse Academie van Wetenschappen, volume 49, pages 758-764, 1946. Google Scholar
  18. Nicolaas Govert de Bruijn. Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2ⁿ zeros and ones that show each n-letter word exactly once. EUT report. WSK, Dept. of Mathematics and Computing Science, 75, 1975. Google Scholar
  19. Nicolaas Govert de Bruijn and Tanja van Aardenne-Ehrenfest. Circuits and trees in oriented linear graphs. Simon Stevin, 28:203-217, 1951. Google Scholar
  20. De Bruijn sequence and universal cycle constructions. https://debruijnsequence.org/. Accessed: 2021-07-24.
  21. Patrick Baxter Dragon, Oscar I Hernandez, Joe Sawada, Aaron Williams, and Dennis Wong. Constructing de Bruijn sequences with co-lexicographic order: The k-ary grandmama sequence. European Journal of Combinatorics, 72:1-11, 2018. Google Scholar
  22. Patrick Baxter Dragon, Oscar I Hernandez, and Aaron Williams. The grandmama de Bruijn sequence for binary strings. In LATIN 2016: Theoretical Informatics, pages 347-361. Springer, 2016. Google Scholar
  23. Cornelius Eldert, HM Gurk, HJ Gray, and Morris Rubinoff. Shifting counters. Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics, 77(1):70-74, 1958. Google Scholar
  24. Tuvi Etzion. An algorithm for constructing m-ary de Bruijn sequences. Journal of algorithms, 7(3):331-340, 1986. Google Scholar
  25. Tuvi Etzion. An algorithm for generating shift-register cycles. Theoretical computer science, 44:209-224, 1986. Google Scholar
  26. Tuvi Etzion and Abraham Lempel. Algorithms for the generation of full-length shift-register sequences. IEEE Transactions on Information Theory, 30(3):480-484, 1984. Google Scholar
  27. LR Ford Jr. A cyclic arrangement of m-tuples. Report No. P-1071, RAND Corp, 1957. Google Scholar
  28. Harold Fredricksen. A class of nonlinear de Bruijn cycles. Journal of Combinatorial Theory, Series A, 19(2):192-199, 1975. Google Scholar
  29. Harold Fredricksen. A survey of full length nonlinear shift register cycle algorithms. SIAM review, 24(2):195-221, 1982. Google Scholar
  30. Harold Fredricksen and Irving J Kessler. An algorithm for generating necklaces of beads in two colors. Discrete mathematics, 61(2-3):181-188, 1986. Google Scholar
  31. Harold Fredricksen and James Maiorana. Necklaces of beads in k colors and k-ary de Bruijn sequences. Discrete Mathematics, 23(3):207-210, 1978. Google Scholar
  32. Daniel Gabric, Štěpán Holub, and Jeffrey Shallit. Generalized de Bruijn words and the state complexity of conjugate sets. In International Conference on Descriptional Complexity of Formal Systems, pages 137-146. Springer, 2019. Google Scholar
  33. Daniel Gabric and Joe Sawada. A de Bruijn sequence construction by concatenating cycles of the complemented cycling register. In International Conference on Combinatorics on Words, pages 49-58. Springer, 2017. Google Scholar
  34. Daniel Gabric and Joe Sawada. Constructing de Bruijn sequences by concatenating smaller universal cycles. Theoretical Computer Science, 743:12-22, 2018. Google Scholar
  35. Daniel Gabric, Joe Sawada, Aaron Williams, and Dennis Wong. A framework for constructing de Bruijn sequences via simple successor rules. Discrete Mathematics, 341(11):2977-2987, 2018. Google Scholar
  36. Daniel Gabric, Joe Sawada, Aaron Williams, and Dennis Wong. A successor rule framework for constructing k-ary de Bruijn sequences and universal cycles. IEEE Transactions on Information Theory, 66(1):679-687, 2019. Google Scholar
  37. Daniel Gabric, Štěpán Holub, and Jeffrey Shallit. Maximal state complexity and generalized de Bruijn words. Information and Computation, page 104689, 2021. URL: https://doi.org/10.1016/j.ic.2021.104689.
  38. R Games. A generalized recursive construction for de Bruijn sequences. IEEE transactions on information theory, 29(6):843-850, 1983. Google Scholar
  39. Solomon W Golomb. Shift Register Sequences: Secure and Limited-Access Code Generators, Efficiency Code Generators, Prescribed Property Generators, Mathematical Models. World Scientific, 2017. Google Scholar
  40. Solomon W Golomb, Lloyd R Welch, and Richard M Goldstein. Cycles from nonlinear shift registers. Technical report, Jet Propulsion Lab, Pasadena, CA, 1959. Google Scholar
  41. Aysu Gündoǧan, Ben Cameron, and Joe Sawada. Cut-down de Bruijn sequences, 2021. Unpublished manuscript. Google Scholar
  42. FG Heath and MW Gribble. Chain codes and their electronic applications. Proceedings of the IEE-Part C: Monographs, 108(13):50-57, 1961. Google Scholar
  43. Farhad Hemmati and Daniel J Costello. An algebraic construction for q-ary shift register sequences. IEEE Transactions on Computers, 100(12):1192-1195, 1978. Google Scholar
  44. Patricia Hersh, Thomas Lam, Pavlo Pylyavskyy, and Victor Reiner. The Mathematical Legacy of Richard P. Stanley, volume 100. American Mathematical Soc., 2016. Google Scholar
  45. Yuejiang Huang. A new algorithm for the generation of binary de Bruijn sequences. Journal of Algorithms, 11(1):44-51, 1990. Google Scholar
  46. Glenn Hurlbert and Garth Isaak. Equivalence class universal cycles for permutations. Discrete Mathematics, 149(1-3):123-129, 1996. Google Scholar
  47. Cees JA Jansen, Wouter G Franx, and Dick E Boekee. An efficient algorithm for the generation of DeBruijn cycles. IEEE Transactions on Information Theory, 37(5):1475-1478, 1991. Google Scholar
  48. J Robert Johnson. Universal cycles for permutations. Discrete Mathematics, 309(17):5264-5270, 2009. Google Scholar
  49. Subhash Kak. Yamatarajabhanasalagam: An interesting combinatoric sutra. Indian Journal of History of Science, 35(2):123-128, 2000. Google Scholar
  50. Tomasz Kociumaka, Jakub Radoszewski, and Wojciech Rytter. Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence. SIAM Journal on Discrete Mathematics, 30(4):2027-2046, 2016. Google Scholar
  51. Nikolai Mikhailovich Korobov. Trigonometric sums with exponential functions and the distribution of signs in repeating decimals. Mathematical notes of the Academy of Sciences of the USSR, 8(5):831-837, 1970. Google Scholar
  52. Nikolai Mikhailovich Korobov. On the distribution of digits in periodic fractions. Mathematics of the USSR-Sbornik, 18(4):659, 1972. Google Scholar
  53. Charles-Ange Laisant and Emile Michel Hyacinthe Lemoine. L'Intermédiaire des Mathematiciens, volume 1. Gauthier-Villars et Fils, 1894. Google Scholar
  54. Max Landsberg. Feedback functions for generating cycles over a finite alphabet. Discrete Mathematics, 219(1-3):187-194, 2000. Google Scholar
  55. Abraham Lempel. On a homomorphism of the de Bruijn graph and its applications to the design of feedback shift registers. IEEE Transactions on Computers, 100(12):1204-1209, 1970. Google Scholar
  56. Abraham Lempel. m-ary closed sequences. Journal of Combinatorial Theory, Series A, 10(3):253-258, 1971. Google Scholar
  57. Willem Mantel. Resten van wederkerige reeksen. Niew Archief voor Wiskunde, 1:172-184, 1897. Google Scholar
  58. Monroe H Martin. A problem in arrangements. Bulletin of the American Mathematical Society, 40(12):859-864, 1934. Google Scholar
  59. Chris J Mitchell, Tuvi Etzion, and Kenneth G Paterson. A method for constructing decodable de Bruijn sequences. IEEE Transactions on Information Theory, 42(5):1472-1478, 1996. Google Scholar
  60. Chris J. Mitchell and Peter B. Wild. Constructing orientable sequences. arXiv preprint, 2021. URL: http://arxiv.org/abs/2108.03069.
  61. Johannes Mykkeltveit, Man-Keung Siu, and Po Tong. On the cycle structure of some nonlinear shift register sequences. Information and control, 43(2):202-215, 1979. Google Scholar
  62. Abhinav Nellore, Austin Nguyen, and Reid F. Thompson. An invertible transform for efficient string matching in labeled digraphs. In Paweł Gawrychowski and Tatiana Starikovskaya, editors, 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021), volume 191 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:14, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.CPM.2021.20.
  63. Nicolaas de Bruijn - biography. https://mathshistory.st-andrews.ac.uk/Biographies/De_Bruijn/. Accessed: 2021-07-23.
  64. Kenneth G Paterson and Matthew JB Robshaw. Storage efficient decoding for a class of binary de Bruijn sequences. Discrete mathematics, 138(1-3):327-341, 1995. Google Scholar
  65. AN Radchenko. Code Rings and Their Use in Contactless Coding Devices. PhD thesis, University of Leningrad, USSR, 1958. Google Scholar
  66. AN Radchenko and VI Filippov. Shifting registers with logical feedback and their use as counting and coding devices. Automation and Remote Control (English translation of Soviet Journal Automatika i Telemekhanika), 20:1467-1473, November 1959. Google Scholar
  67. Christian Ronse. Feedback shift registers. Lecture Notes in Computer Science, 169, 1984. Google Scholar
  68. Frank Ruskey, Carla Savage, and Terry Min Yih Wang. Generating necklaces. Journal of Algorithms, 13(3):414-430, 1992. Google Scholar
  69. C Flye Saint-Marie. Solution to question nr. 48. L'Intermédiaire des Mathématiciens, 1894. Google Scholar
  70. Joe Sawada and Aaron Williams. Practical algorithms to rank necklaces, Lyndon words, and de Bruijn sequences. Journal of Discrete Algorithms, 43:95-110, 2017. Google Scholar
  71. Joe Sawada, Aaron Williams, and Dennis Wong. The lexicographically smallest universal cycle for binary strings with minimum specified weight. Journal of Discrete Algorithms, 28:31-40, 2014. Google Scholar
  72. Joe Sawada, Aaron Williams, and Dennis Wong. Generalizing the classic greedy and necklace constructions of de Bruijn sequences and universal cycles. the electronic journal of combinatorics, pages P1-24, 2016. Google Scholar
  73. Joe Sawada, Aaron Williams, and Dennis Wong. A surprisingly simple de Bruijn sequence construction. Discrete Mathematics, 339(1):127-131, 2016. Google Scholar
  74. Joe Sawada, Aaron Williams, and Dennis Wong. A simple shift rule for k-ary de Bruijn sequences. Discrete Mathematics, 340(3):524-531, 2017. Google Scholar
  75. Joe Sawada and Dennis Wong. Efficient universal cycle constructions for weak orders. Discrete Mathematics, 343(10):112022, 2020. Google Scholar
  76. Man-Keung Siu and Po Tong. Generation of some de Bruijn sequences. Discrete Mathematics, 31(1):97-100, 1980. Google Scholar
  77. R Stoneham. On (j, ε)-normality in the rational fractions. Acta Arithmetica, 16:221-238, 1970. Google Scholar
  78. R Stoneham. On absolute (j, ε)-normality in the rational fractions with applications to normal numbers. Acta Arithmetica, 22:277-286, 1973. Google Scholar
  79. R Stoneham. Normal recurring decimals, normal periodic systems,(j, ε)-normality, and normal numbers. Acta Arithmetica, 28(4):349-361, 1976. Google Scholar
  80. RG Stoneham. The reciprocals of integral powers of primes and normal numbers. Proceedings of the American Mathematical Society, 15(2):200-208, 1964. Google Scholar
  81. Jonathan Tuliani. De Bruijn sequences with efficient decoding algorithms. Discrete Mathematics, 226(1-3):313-336, 2001. Google Scholar
  82. Srisa Chandra Vasu et al. The Ashtadhyayi of Panini, volume 6. Satyajnan Chaterji, 1897. Google Scholar
  83. Dennis Wong. A new universal cycle for permutations. Graphs and Combinatorics, 33(6):1393-1399, 2017. Google Scholar
  84. Jun-Hui Yang and Zong-Duo Dai. Construction of m-ary de Bruijn sequences. In International Workshop on the Theory and Application of Cryptographic Techniques, pages 357-363. Springer, 1992. Google Scholar
  85. Michael Yoeli. Nonlinear Feedback Shift Registers. International Business Machines Corporation, Development Laboratories, Data Systems Division, 1961. Google Scholar
  86. Michael Yoeli. Binary ring sequences. The American Mathematical Monthly, 69(9):852-855, 1962. Google Scholar
  87. Michael Yoeli. Counting with nonlinear binary feedback shift registers. IEEE Transactions on Electronic Computers, pages 357-361, 1963. Google Scholar
  88. Yunlong Zhu, Zuling Chang, Martianus Frederic Ezerman, and Qiang Wang. An efficiently generated family of binary de Bruijn sequences. Discrete Mathematics, 344(6):112368, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact