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...
Saved in:
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/146464 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| id |
sg-ntu-dr.10356-146464 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.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 |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
NTU Library |
| collection |
DR-NTU |
| language |
English |
| topic |
Science::Mathematics de Bruijn Sequences Greedy Algorithm |
| spellingShingle |
Science::Mathematics de Bruijn Sequences Greedy Algorithm Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa On greedy algorithms for binary de Bruijn sequences |
| 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. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa |
| format |
Article |
| author |
Chang, Zuling Ezerman, Martianus Frederic Fahreza, Adamas Aqsa |
| author_sort |
Chang, Zuling |
| title |
On greedy algorithms for binary de Bruijn sequences |
| title_short |
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_sort |
on greedy algorithms for binary de bruijn sequences |
| publishDate |
2021 |
| url |
https://hdl.handle.net/10356/146464 |
| _version_ |
1759856365622263808 |