De Bruijn Sequences with Minimum Discrepancy
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916335224619008 |
|---|---|
| author | Álvarez, Nicolás Becher, Verónica Mereb, Martín Pajor, Ivo Soto, Carlos Miguel |
| author_facet | Álvarez, Nicolás Becher, Verónica Mereb, Martín Pajor, Ivo Soto, Carlos Miguel |
| contents | The discrepancy of a binary string is the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary string. In this note we determine the minimal discrepancy that a binary de Bruijn sequence of order $n$ can achieve, which is $n$. This was an open problem until now. We give an algorithm that constructs a binary de Bruijn sequence with minimal discrepancy. A slight modification of this algorithm deals with arbitrary alphabets and yields de Bruijn sequences of order $n$ with discrepancy at most $1$ above the trivial lower bound $n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_17367 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | De Bruijn Sequences with Minimum Discrepancy Álvarez, Nicolás Becher, Verónica Mereb, Martín Pajor, Ivo Soto, Carlos Miguel Discrete Mathematics 68R01 G.2.0 The discrepancy of a binary string is the maximum (absolute) difference between the number of ones and the number of zeroes over all possible substrings of the given binary string. In this note we determine the minimal discrepancy that a binary de Bruijn sequence of order $n$ can achieve, which is $n$. This was an open problem until now. We give an algorithm that constructs a binary de Bruijn sequence with minimal discrepancy. A slight modification of this algorithm deals with arbitrary alphabets and yields de Bruijn sequences of order $n$ with discrepancy at most $1$ above the trivial lower bound $n$. |
| title | De Bruijn Sequences with Minimum Discrepancy |
| topic | Discrete Mathematics 68R01 G.2.0 |
| url | https://arxiv.org/abs/2407.17367 |