Fast enumeration algorithm for words with given constraints on run lengths of ones

We propose an algorithm for enumeration and denumeration of words with given constraints on run lengths of ones ( dklr -sequences). For large n , operation time of the algorithm (per symbol of a sequence) is at most O (log 3 n log log n ), where n is the length of enumerated words, whereas for the b...

Full description

Saved in:
Bibliographic Details
Published in:Problems of information transmission 2010-12, Vol.46 (4), p.390-399
Main Authors: Medvedeva, Yu. S., Ryabko, B. Ya
Format: Article
Language:English
Subjects:
Communications Engineering
Control
Electrical Engineering
Engineering
Information Storage and Retrieval
Networks
Source Coding
Systems Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose an algorithm for enumeration and denumeration of words with given constraints on run lengths of ones ( dklr -sequences). For large n , operation time of the algorithm (per symbol of a sequence) is at most O (log 3 n log log n ), where n is the length of enumerated words, whereas for the best known methods it is at least cn , c > 0.
ISSN:0032-9460
1608-3253
DOI:10.1134/S0032946010040095