Publisher DOI: 10.1016/j.jcta.2025.106030
10.48550/arXiv.2405.03309
Title: On de Bruijn Rings and families of almost perfect maps
Other Titles: Über de Bruijn Ringe und fast perfekte Karten
Language: English
Authors: Stelldinger, Peer  
Keywords: De Bruijn torus; De Bruijn ring; Perfect map; Sub-perfect map
Issue Date: 27-Feb-2025
Publisher: Elsevier
Journal or Series Name: Journal of combinatorial theory : JCTA. Series A 
Volume: 214
Abstract: 
De Bruijn tori, also called perfect maps, are two-dimensional periodic arrays of letters drawn from a given finite alphabet, such that each possible pattern of a given shape (m,n) appears exactly once within one period of the torus. It is still unknown if de Bruijn tori of some certain size exist, like e.g. square shaped de Bruijn Tori with odd m=n in {3,5,7} and an even alphabet size k. However, in certain applications like positional coding, sub-perfect maps are sufficient, i.e. one does not need every possible (m,n)-pattern to appear, as long as a sufficient large number of such patterns is captured and every pattern occurs at most once. We show, that given any m=n and a square alphabet size k², one can efficiently construct a sub-perfect map which is almost perfect, i.e. of almost maximal size. We do this by introducing de Bruijn rings, i.e. sub-perfect maps of minimal height, and providing an efficient construction method for them. We extend our results to non-square torus shapes and arbitrary non-prime alphabet sizes.
URI: https://hdl.handle.net/20.500.12738/16530
ISSN: 0097-3165
Review status: This version was peer reviewed (peer review)
Institute: Forschungs- und Transferzentrum Smart Systems 
Department Informatik 
Fakultät Technik und Informatik 
Type: Article
Additional note: Preprint: https://doi.org/10.48550/arXiv.2405.03309. Verlagsversion: https://doi.org/10.1016/j.jcta.2025.106030.
Appears in Collections:Publications without full text

Show full item record

Page view(s)

59
checked on Apr 2, 2025

Google ScholarTM

Check

HAW Katalog

Check

Add Files to Item

Note about this record


This item is licensed under a Creative Commons License Creative Commons