Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2020
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910408013512704 |
|---|---|
| author | Burcsi, Péter Fici, Gabriele Lipták, Zsuzsanna Raman, Rajeev Sawada, Joe |
| author_facet | Burcsi, Péter Fici, Gabriele Lipták, Zsuzsanna Raman, Rajeev Sawada, Joe |
| contents | A prefix normal word is a binary word with the property that no substring has more $1$s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length $n$ as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in $\Oh(\log^2 n)$ amortized time per word, while the best generation algorithm hitherto has $\Oh(n)$ running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2003_03222 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Generating a Gray code for prefix normal words in amortized polylogarithmic time per word Burcsi, Péter Fici, Gabriele Lipták, Zsuzsanna Raman, Rajeev Sawada, Joe Data Structures and Algorithms Formal Languages and Automata Theory A prefix normal word is a binary word with the property that no substring has more $1$s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length $n$ as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in $\Oh(\log^2 n)$ amortized time per word, while the best generation algorithm hitherto has $\Oh(n)$ running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages. |
| title | Generating a Gray code for prefix normal words in amortized polylogarithmic time per word |
| topic | Data Structures and Algorithms Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2003.03222 |