On greedy algorithms for binary de Bruijn sequences
We propose a general greedy algorithm for binary de Bruijn sequences, called Generalized Prefer-Opposite Algorithm, and its modifications. By identifying specific feedback functions and initial states, we demonstrate that most previously-known greedy algorithms that generate binary de Bruijn sequenc...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/146464 |
| _version_ | 1826124684301697024 |
|---|---|
| author | Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa |
| author_sort | Chang, Zuling |
| collection | NTU |
| description | We propose a general greedy algorithm for binary de Bruijn sequences, called Generalized Prefer-Opposite Algorithm, and its modifications. By identifying specific feedback functions and initial states, we demonstrate that most previously-known greedy algorithms that generate binary de Bruijn sequences are particular cases of our algorithm. |
| first_indexed | 2024-10-01T06:24:23Z |
| format | Journal Article |
| id | ntu-10356/146464 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:24:23Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1464642023-02-28T19:54:24Z On greedy algorithms for binary de Bruijn sequences Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa School of Physical and Mathematical Sciences Science::Mathematics de Bruijn Sequences Greedy Algorithm We propose a general greedy algorithm for binary de Bruijn sequences, called Generalized Prefer-Opposite Algorithm, and its modifications. By identifying specific feedback functions and initial states, we demonstrate that most previously-known greedy algorithms that generate binary de Bruijn sequences are particular cases of our algorithm. Nanyang Technological University Accepted version Nanyang Technological University Grant M4080456 supports the research carried out by M. F. Ezerman and A. A. Fahreza. 2021-02-18T02:13:15Z 2021-02-18T02:13:15Z 2020 Journal Article Chang, Z., Ezerman, M. F., & Fahreza, A. A. (2020). On greedy algorithms for binary de Bruijn sequences. Applicable Algebra in Engineering, Communication and Computing. doi:10.1007/s00200-020-00459-3 1432-0622 https://hdl.handle.net/10356/146464 10.1007/s00200-020-00459-3 2-s2.0-85092648185 en Applicable Algebra in Engineering, Communication and Computing © 2020 Springer. This is a post-peer-review, pre-copyedit version of an article published in Applicable Algebra in Engineering, Communication and Computing. The final authenticated version is available online at: http://dx.doi.org/10.1007/s00200-020-00459-3 application/pdf |
| spellingShingle | Science::Mathematics de Bruijn Sequences Greedy Algorithm Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa On greedy algorithms for binary de Bruijn sequences |
| title | On greedy algorithms for binary de Bruijn sequences |
| title_full | On greedy algorithms for binary de Bruijn sequences |
| title_fullStr | On greedy algorithms for binary de Bruijn sequences |
| title_full_unstemmed | On greedy algorithms for binary de Bruijn sequences |
| title_short | On greedy algorithms for binary de Bruijn sequences |
| title_sort | on greedy algorithms for binary de bruijn sequences |
| topic | Science::Mathematics de Bruijn Sequences Greedy Algorithm |
| url | https://hdl.handle.net/10356/146464 |
| work_keys_str_mv | AT changzuling ongreedyalgorithmsforbinarydebruijnsequences AT ezermanmartianusfrederic ongreedyalgorithmsforbinarydebruijnsequences AT fahrezaadamasaqsa ongreedyalgorithmsforbinarydebruijnsequences |