Onion De Bruijn Sequences: Fixed-Window Counting by Growing the Alphabet
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2019
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916005042716672 |
|---|---|
| author | Genosar, Dor Svoray, Yotam Weiss, Gera |
| author_facet | Genosar, Dor Svoray, Yotam Weiss, Gera |
| contents | We study a fixed-window counting system in which integers are represented by words of constant length while the alphabet grows as needed. This viewpoint arises from De Bruijn sequences: for fixed order $n$, the reverse prefer-max sequence is compatible with alphabet growth, since for each $k$ its restriction to $[k]^n$ is a De Bruijn sequence, yielding an infinite sequence over $\mathbb{N}$. We formalize this through the notion of an onion De Bruijn sequence, prove the resulting structural properties, and count compatible finite onion prefixes by an explicit product formula. For orders $n=2,3$, we give explicit rank and unrank formulas and describe addition and multiplication via finite normalization, with exact carry counts and linear carry complexity in the input layers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1906_06157 |
| institution | arXiv |
| publishDate | 2019 |
| record_format | arxiv |
| spellingShingle | Onion De Bruijn Sequences: Fixed-Window Counting by Growing the Alphabet Genosar, Dor Svoray, Yotam Weiss, Gera Discrete Mathematics Combinatorics We study a fixed-window counting system in which integers are represented by words of constant length while the alphabet grows as needed. This viewpoint arises from De Bruijn sequences: for fixed order $n$, the reverse prefer-max sequence is compatible with alphabet growth, since for each $k$ its restriction to $[k]^n$ is a De Bruijn sequence, yielding an infinite sequence over $\mathbb{N}$. We formalize this through the notion of an onion De Bruijn sequence, prove the resulting structural properties, and count compatible finite onion prefixes by an explicit product formula. For orders $n=2,3$, we give explicit rank and unrank formulas and describe addition and multiplication via finite normalization, with exact carry counts and linear carry complexity in the input layers. |
| title | Onion De Bruijn Sequences: Fixed-Window Counting by Growing the Alphabet |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/1906.06157 |