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

作者

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

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

会议/活动

10th International Conference on Mathematical Modeling in Physical Sciences (IC-MSQUARE 2021), September 2021 (虚拟会议)

海报摘要

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.

关键词

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

研究领域

Computer and Information Science , Mathematics

参考文献

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.

基金

暂无数据

补充材料

暂无数据

附加信息

利益冲突

No competing interests were disclosed.

数据可用性声明

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

知识共享许可协议

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.