A prefix normal word is a binary word with the property that no substring has more 1s 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 O(log2⁡n) amortized time per word, while the best generation algorithm hitherto has O(n) running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages.

Burcsi P., Fici G., Liptak Z., Raman R., & Sawada J. (2020). Generating a Gray code for prefix normal words in amortized polylogarithmic time per word. THEORETICAL COMPUTER SCIENCE, 842, 86-99 [10.1016/j.tcs.2020.07.035].

Generating a Gray code for prefix normal words in amortized polylogarithmic time per word

Fici G.;
2020

Abstract

A prefix normal word is a binary word with the property that no substring has more 1s 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 O(log2⁡n) amortized time per word, while the best generation algorithm hitherto has O(n) running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages.
Settore INF/01 - Informatica
Burcsi P., Fici G., Liptak Z., Raman R., & Sawada J. (2020). Generating a Gray code for prefix normal words in amortized polylogarithmic time per word. THEORETICAL COMPUTER SCIENCE, 842, 86-99 [10.1016/j.tcs.2020.07.035].
File in questo prodotto:
File Dimensione Formato  
Generating a Gray code for prefix normal words in amortized polylogarithmic time per word.pdf

Solo gestori archvio

Descrizione: articolo principale
Tipologia: Versione Editoriale
Dimensione 459.94 kB
Formato Adobe PDF
459.94 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10447/456112
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact