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

DOI10.1016/j.tcs.2020.07.035zbMath1460.68135arXiv2003.03222OpenAlexW3046970181MaRDI QIDQ2006779

Joe Sawada, Gabriele Fici, Péter Burcsi, Zsuzsanna Lipták, Rajeev Raman

Publication date: 12 October 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2003.03222

zbMATH Keywords

jumbled pattern matchingbinary languagesprefix normal wordscombinatorial Gray codecombinatorial generation

Mathematics Subject Classification ID

Combinatorics on words (68R15) Formal languages and automata (68Q45) Algorithms on strings (68W32)

Related Items (3)

Weighted prefix normal words: mind the gap ⋮ Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions ⋮ On infinite prefix normal words

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Sub-quadratic time and linear space data structures for permutation matching in binary strings
• Efficient oracles for generating binary bubble languages
• Algorithms for jumbled indexing, jumbled border and jumbled square on run-length encoded strings
• Efficient indexes for jumbled pattern matching with constant-sized alphabet
• Binary bubble languages and cool-lex order
• On approximate jumbled pattern matching in strings
• On prefix normal words and prefix normal forms
• On collapsing prefix normal words
• Binary jumbled pattern matching on trees and tree-like structures
• Leaf realization problem, caterpillar graphs and prefix normal words
• The asymptotic number of prefix normal words
• Approximating the maximum consecutive subsums of a sequence
• New algorithms for binary jumbled pattern matching
• ALGORITHMS FOR JUMBLED PATTERN MATCHING IN STRINGS
• Clustered Integer 3SUM via Additive Combinatorics
• On the relationship between histogram indexing and block-mass indexing
• Fast and Simple Jumbled Indexing for Binary Run-Length Encoded Strings
• A Lower Bound for Jumbled Indexing
• On Combinatorial Generation of Prefix Normal Words
• On Hardness of Jumbled Indexing
• On Prefix Normal Words
• On infinite prefix normal words
• Bubble-flip -- a new generation algorithm for prefix normal words

This page was built for publication: Generating a Gray code for prefix normal words in amortized polylogarithmic time per word