Rule-based Generation of de Bruijn Sequences: Memory and Learning
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915445716549632 |
|---|---|
| author | Muñoz, Francisco J. Nuño, Juan Carlos |
| author_facet | Muñoz, Francisco J. Nuño, Juan Carlos |
| contents | We investigate binary sequences generated by non-Markovian rules with memory length $μ$, similar to those adopted in Elementary Cellular Automata. This generation procedure is equivalente to a shift register and certain rules produce sequences with maximal periods, known as de Bruijn sequences. We introduce a novel methodology for generating de Bruijn sequences that combines: (i) a set of derived properties that significantly reduce the space of feasible generating rules, and (ii) a neural network-based classifier that identifies which rules produce de Bruijn sequences. Experiments for large values of $μ$ demonstrate the approach's effectiveness and computational efficiency. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_09764 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Rule-based Generation of de Bruijn Sequences: Memory and Learning Muñoz, Francisco J. Nuño, Juan Carlos Formal Languages and Automata Theory Dynamical Systems We investigate binary sequences generated by non-Markovian rules with memory length $μ$, similar to those adopted in Elementary Cellular Automata. This generation procedure is equivalente to a shift register and certain rules produce sequences with maximal periods, known as de Bruijn sequences. We introduce a novel methodology for generating de Bruijn sequences that combines: (i) a set of derived properties that significantly reduce the space of feasible generating rules, and (ii) a neural network-based classifier that identifies which rules produce de Bruijn sequences. Experiments for large values of $μ$ demonstrate the approach's effectiveness and computational efficiency. |
| title | Rule-based Generation of de Bruijn Sequences: Memory and Learning |
| topic | Formal Languages and Automata Theory Dynamical Systems |
| url | https://arxiv.org/abs/2507.09764 |