Review on de Bruijn shapes in 1, 2 and 3 dimensions

Authors

Pedro Juan Roig¹ , Salvador Alcaraz¹ , Katja Gilly¹ , Cristina Bernad¹ , Carlos Juiz²

1. Miguel Hernández University, Spain
2. University of the Balearic Islands, Spain

Conference / event

10th International Conference on Mathematical Modeling in Physical Sciences (IC-MSQUARE 2021), September 2021 (Virtual)

Poster summary

This poster starts reviewing the main features of de Bruijn sequences, defined as strings containing all substrings of a given length in a given alphabet exactly once, along with a range of instances whose length is up to 64 characters. Right below, two methods to obtain those sequences are presented, such as de Bruijn graphs and Wong algorithm. After that, de Bruijn tori are presented as bidimensional extensions of de Bruijn sequences, as well as a set of the smallest representative instances. Additionally, de Bruijn 3D-hypertori are introduced as tridimensional extensions of de Bruijn sequences, along with the smallest instance available.

Keywords

De Bruijn sequence, De Bruijn graph, De Bruijn torus, De Bruijn 3D-hypertorus

Research areas

Computer and Information Science , Mathematics

References

1. Roig, P.J.; Alcaraz, S.; Gilly, K.; Bernad, C.; Juiz, C. Review on de Bruijn shapes in one, two and three dimensions. Journal of Physics: Conference Series, Vol. 2090, article no. 012047, pages 1-10, 2021.
2. Roig, P.J.; Alcaraz, S.; Gilly, K.; Bernad, C.; Juiz, C. De Bruijn Shapes: Theory and Instances. New Trends in Physical Science Research, Vol. 4, pages 33-50, 2022.
3. Casteels, K.; Tinker, T. De Bruijn Sequences of Higher Dimension. Master's Thesis in Computer Science, University of California, USA, 2018.
4. Kapinya, J.B. Evolutionary Computing Solutions for the de Bruijn Torus Problem. Master's Thesis in Computer Science, University of Vrije, The Netherlands, 2004.
5. Wong, C.H. Novel universal cycle constructions for a variety of combinatorial objects. PhD Thesis in Computer Science, University of Gelph, Canada, 2015.

Funding

No data provided

Supplemental files

No data provided

Additional information

Competing interests

No competing interests were disclosed.

Data availability statement

Data sharing not applicable to this poster as no datasets were generated or analyzed during the current study.

Creative Commons license

Copyright © 2023 Roig et al. This is an open access work distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.