On de Bruijn Rings and families of almost perfect maps,Über de Bruijn Ringe und fast perfekte Karten

Link:
Autor/in:
Verlag/Körperschaft:
Elsevier
Erscheinungsjahr:
2025
Medientyp:
Text
Schlagworte:
  • De Bruijn torus
  • De Bruijn ring
  • Perfect map
  • Sub-perfect map
  • 004: Informatik
  • ddc:004
Beschreibung:
  • 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.
  • PeerReviewed
Lizenz:
  • https://creativecommons.org/licenses/by/4.0/
Quellsystem:
ReposIt

Interne Metadaten
Quelldatensatz
oai:reposit.haw-hamburg.de:20.500.12738/16530