6533b820fe1ef96bd1279b53

RESEARCH PRODUCT

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

Péter BurcsiJoe SawadaRajeev RamanZsuzsanna LiptákGabriele Fici

subject

FOS: Computer and information sciencesGeneral Computer ScienceFormal Languages and Automata Theory (cs.FL)Property (programming)combinatorial Gray codeComputer Science - Formal Languages and Automata TheoryData_CODINGANDINFORMATIONTHEORY0102 computer and information sciences02 engineering and technologyCharacterization (mathematics)01 natural sciencesTheoretical Computer ScienceCombinatoricsSet (abstract data type)Gray codeComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)MathematicsAmortized analysisSettore INF/01 - Informaticaprefix normal wordsSubstringcombinatorial generationPrefixjumbled pattern matching010201 computation theory & mathematics020201 artificial intelligence & image processingbinary languagesprefix normal words binary languages combinatorial Gray code combinatorial generation jumbled pattern matchingWord (computer architecture)

description

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.

yearjournalcountryeditionlanguage
2020-03-05Theoretical Computer Science
https://doi.org/10.1016/j.tcs.2020.07.035