Space-optimal quasi-Gray codes with logarithmic read complexity

DOI10.4230/LIPICS.ESA.2018.12MaRDI QIDQ5009569zbMATH OpenOpenAlexFDO

Authors Diptarka Chakraborty, Debarati Das, Michal Koucký, Nitin Saurabh

Publication date 4 August 2021

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2018/9475/pdf/LIPIcs-ESA-2018-12.pdf/

zbMATH Keywords

cell probe modeldecision assignment treegray codespace-optimal counter

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Improved methods for generating quasi-Gray codes
• Linear time construction of a compressed Gray code
• Balancing cyclic \(R\)-ary Gray codes. II.
• Gray code compression
• Binary Gray codes with long bit runs

Cites work

• A constant-time algorithm for middle levels Gray codes
• A linear lower bound for incrementing a space-optimal integer representation in the bit-probe model
• A Survey of Combinatorial Gray Codes
• A Survey of Data Structures in the Bitprobe Model
• Affine m-ary gray codes
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Combinatorial Gray Codes
• Computing Algebraic Formulas Using a Constant Number of Registers
• Computing with a full memory: catalytic space
• Constant-Weight Gray Codes for Local Rank Modulation
• Counting sequences
• Data compression and Gray-code sorting
• Dynamic word problems
• Efficient Computation of Middle Levels Gray Codes
• Efficient generation of the binary reflected gray code and its applications
• Generalized Gray codes with prescribed ends
• Generators for Certain Alternating Groups with Applications to Cryptography
• scientific article; zbMATH DE number 4018948 (Why is no real title available?)
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 1122449 (Why is no real title available?)
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 922674 (Why is no real title available?)
• Improved methods for generating quasi-Gray codes
• Integer representation and counting in the bit probe model
• Integer representations towards efficient counting in the bit probe model
• Loopless Algorithms for Generating Permutations, Combinations, and Other Combinatorial Configurations
• Loopless Gray code enumeration and the Tower of Bucharest
• Proof of the middle levels conjecture
• Rank Modulation for Flash Memories
• Should Tables Be Sorted?
• Snake-in-the-Box Codes for Rank Modulation
• Symbolic Gray Code As A Data Allocation Scheme For Two-disc Systems
• The art of computer programming. Volume 4A. Combinatorial algorithms. Part 1.
• Trimming and gluing Gray codes

Cited in

(2)

• Improved methods for generating quasi-Gray codes
• Near optimal single-track Gray codes

This page was built for publication: Space-optimal quasi-Gray codes with logarithmic read complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5009569)