Loading…
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...
Saved in:
| Published in: | Problems of information transmission 2010-12, Vol.46 (4), p.390-399 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| 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!
|
| cited_by | cdi_FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3 |
| container_end_page | 399 |
| container_issue | 4 |
| container_start_page | 390 |
| container_title | Problems of information transmission |
| container_volume | 46 |
| creator | Medvedeva, Yu. S. Ryabko, B. Ya |
| description | 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. |
| doi_str_mv | 10.1134/S0032946010040095 |
| format | article |
| fullrecord | <record><control><sourceid>crossref_sprin</sourceid><recordid>TN_cdi_crossref_primary_10_1134_S0032946010040095</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>10_1134_S0032946010040095</sourcerecordid><originalsourceid>FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3</originalsourceid><addsrcrecordid>eNp9kN1KAzEQhYMoWKsP4F1eYDWTbHezl1KsCgXBn-tlmp1st2wTSVKLb29qvRO8Gs6c7wzDYewaxA2AKm9fhVCyKSsBQpRCNLMTNoFK6ELJmTplk4NdHPxzdhHjRvxwasJeFhgTJ7fbUsA0eMdx7H0Y0nrLrQ9870MX-T5r3g-f5LjxLqaAg0uRZzrsHB_J9Wmdpc0bipfszOIY6ep3Ttn74v5t_lgsnx-e5nfLwkitUyE1lWjsihCskaW2GmVjZogAQFgLrLVRnW2oosqsGtVpqk1pwELTEVlSUwbHuyb4GAPZ9iMMWwxfLYj2UEr7p5SckcdMzKzrKbQbvwsuv_lP6Bvhq2ZA</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>Fast enumeration algorithm for words with given constraints on run lengths of ones</title><source>Springer Nature</source><creator>Medvedeva, Yu. S. ; Ryabko, B. Ya</creator><creatorcontrib>Medvedeva, Yu. S. ; Ryabko, B. Ya</creatorcontrib><description>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.</description><identifier>ISSN: 0032-9460</identifier><identifier>EISSN: 1608-3253</identifier><identifier>DOI: 10.1134/S0032946010040095</identifier><language>eng</language><publisher>Dordrecht: SP MAIK Nauka/Interperiodica</publisher><subject>Communications Engineering ; Control ; Electrical Engineering ; Engineering ; Information Storage and Retrieval ; Networks ; Source Coding ; Systems Theory</subject><ispartof>Problems of information transmission, 2010-12, Vol.46 (4), p.390-399</ispartof><rights>Pleiades Publishing, Ltd. 2010</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3</citedby><cites>FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,776,780,27901,27902</link.rule.ids></links><search><creatorcontrib>Medvedeva, Yu. S.</creatorcontrib><creatorcontrib>Ryabko, B. Ya</creatorcontrib><title>Fast enumeration algorithm for words with given constraints on run lengths of ones</title><title>Problems of information transmission</title><addtitle>Probl Inf Transm</addtitle><description>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.</description><subject>Communications Engineering</subject><subject>Control</subject><subject>Electrical Engineering</subject><subject>Engineering</subject><subject>Information Storage and Retrieval</subject><subject>Networks</subject><subject>Source Coding</subject><subject>Systems Theory</subject><issn>0032-9460</issn><issn>1608-3253</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><recordid>eNp9kN1KAzEQhYMoWKsP4F1eYDWTbHezl1KsCgXBn-tlmp1st2wTSVKLb29qvRO8Gs6c7wzDYewaxA2AKm9fhVCyKSsBQpRCNLMTNoFK6ELJmTplk4NdHPxzdhHjRvxwasJeFhgTJ7fbUsA0eMdx7H0Y0nrLrQ9870MX-T5r3g-f5LjxLqaAg0uRZzrsHB_J9Wmdpc0bipfszOIY6ep3Ttn74v5t_lgsnx-e5nfLwkitUyE1lWjsihCskaW2GmVjZogAQFgLrLVRnW2oosqsGtVpqk1pwELTEVlSUwbHuyb4GAPZ9iMMWwxfLYj2UEr7p5SckcdMzKzrKbQbvwsuv_lP6Bvhq2ZA</recordid><startdate>20101201</startdate><enddate>20101201</enddate><creator>Medvedeva, Yu. S.</creator><creator>Ryabko, B. Ya</creator><general>SP MAIK Nauka/Interperiodica</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20101201</creationdate><title>Fast enumeration algorithm for words with given constraints on run lengths of ones</title><author>Medvedeva, Yu. S. ; Ryabko, B. Ya</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Communications Engineering</topic><topic>Control</topic><topic>Electrical Engineering</topic><topic>Engineering</topic><topic>Information Storage and Retrieval</topic><topic>Networks</topic><topic>Source Coding</topic><topic>Systems Theory</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Medvedeva, Yu. S.</creatorcontrib><creatorcontrib>Ryabko, B. Ya</creatorcontrib><collection>CrossRef</collection><jtitle>Problems of information transmission</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Medvedeva, Yu. S.</au><au>Ryabko, B. Ya</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Fast enumeration algorithm for words with given constraints on run lengths of ones</atitle><jtitle>Problems of information transmission</jtitle><stitle>Probl Inf Transm</stitle><date>2010-12-01</date><risdate>2010</risdate><volume>46</volume><issue>4</issue><spage>390</spage><epage>399</epage><pages>390-399</pages><issn>0032-9460</issn><eissn>1608-3253</eissn><abstract>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.</abstract><cop>Dordrecht</cop><pub>SP MAIK Nauka/Interperiodica</pub><doi>10.1134/S0032946010040095</doi><tpages>10</tpages></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0032-9460 |
| ispartof | Problems of information transmission, 2010-12, Vol.46 (4), p.390-399 |
| issn | 0032-9460 1608-3253 |
| language | eng |
| recordid | cdi_crossref_primary_10_1134_S0032946010040095 |
| source | Springer Nature |
| subjects | Communications Engineering Control Electrical Engineering Engineering Information Storage and Retrieval Networks Source Coding Systems Theory |
| title | Fast enumeration algorithm for words with given constraints on run lengths of ones |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-09T21%3A43%3A53IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-crossref_sprin&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Fast%20enumeration%20algorithm%20for%20words%20with%20given%20constraints%20on%20run%20lengths%20of%20ones&rft.jtitle=Problems%20of%20information%20transmission&rft.au=Medvedeva,%20Yu.%20S.&rft.date=2010-12-01&rft.volume=46&rft.issue=4&rft.spage=390&rft.epage=399&rft.pages=390-399&rft.issn=0032-9460&rft.eissn=1608-3253&rft_id=info:doi/10.1134/S0032946010040095&rft_dat=%3Ccrossref_sprin%3E10_1134_S0032946010040095%3C/crossref_sprin%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c288t-28e4acfbea1fc248f8a29c5aa111ea70a78c3df9e6e6cb93d8e7c4c1f19deefe3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true |