Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity

Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entrop...

Full description

Saved in:
Bibliographic Details
Published in:Theory of computing systems 2010-04, Vol.46 (3), p.598-617
Main Author: Bienvenu, Laurent
Format: Article
Language:English
Subjects:
Algorithms
Bias
Binary system
Codes
Computer Science
Mathematical analysis
Random variables
Stochastic models
Studies
Theory of Computation
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-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3
cites cdi_FETCH-LOGICAL-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3
container_end_page 617
container_issue 3
container_start_page 598
container_title Theory of computing systems
container_volume 46
creator Bienvenu, Laurent
description Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least δ . We also prove an analogous result for finite strings.
doi_str_mv 10.1007/s00224-009-9232-4
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_743595144</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>1963694261</sourcerecordid><originalsourceid>FETCH-LOGICAL-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3</originalsourceid><addsrcrecordid>eNp1kMFOwzAMhiMEEmPwANwmLpwCTpw0RJzQxAAxiQNwjtI2HZ3aZSTdxN6elCJNQuJky_782_4JOWdwxQDUdQTgXFAATTVHTsUBGTGBSEFoOPzJUxElHJOTGJcAgDcAI3L77JvWL3zwWzr3W9fYVTl57XzxYWNXF3W3m_SVPTWZ-nbduK_UOSVHlW2iO_uNY_I-u3-bPtL5y8PT9G5OCxSqo06BA5sxoZAJgDLPmUSWM1GizHSeZzyTvHCV1JYzBnkpUaEsbcFV5lBXOCaXg-46-M-Ni51p61i4Jt3q_CYalf7SkgmRyIs_5NJvwiodZzgqnhZplSA2QEXwMQZXmXWoWxt2hoHpzTSDmSaZaXozTS_Mh5mY2NXChb3w_0Pf09B1zg</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>237226597</pqid></control><display><type>article</type><title>Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity</title><source>ABI/INFORM Global</source><source>Springer Link</source><source>BSC - Ebsco (Business Source Ultimate)</source><creator>Bienvenu, Laurent</creator><creatorcontrib>Bienvenu, Laurent</creatorcontrib><description>Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least δ . We also prove an analogous result for finite strings.</description><identifier>ISSN: 1432-4350</identifier><identifier>EISSN: 1433-0490</identifier><identifier>DOI: 10.1007/s00224-009-9232-4</identifier><identifier>CODEN: TCSYFI</identifier><language>eng</language><publisher>New York: Springer-Verlag</publisher><subject>Algorithms ; Bias ; Binary system ; Codes ; Computer Science ; Mathematical analysis ; Random variables ; Stochastic models ; Studies ; Theory of Computation</subject><ispartof>Theory of computing systems, 2010-04, Vol.46 (3), p.598-617</ispartof><rights>Springer Science+Business Media, LLC 2009</rights><rights>Springer Science+Business Media, LLC 2010</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3</citedby><cites>FETCH-LOGICAL-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.proquest.com/docview/237226597/fulltextPDF?pq-origsite=primo$$EPDF$$P50$$Gproquest$$H</linktopdf><linktohtml>$$Uhttps://www.proquest.com/docview/237226597?pq-origsite=primo$$EHTML$$P50$$Gproquest$$H</linktohtml><link.rule.ids>314,780,784,11688,27924,27925,36060,36061,44363,74767</link.rule.ids></links><search><creatorcontrib>Bienvenu, Laurent</creatorcontrib><title>Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity</title><title>Theory of computing systems</title><addtitle>Theory Comput Syst</addtitle><description>Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least δ . We also prove an analogous result for finite strings.</description><subject>Algorithms</subject><subject>Bias</subject><subject>Binary system</subject><subject>Codes</subject><subject>Computer Science</subject><subject>Mathematical analysis</subject><subject>Random variables</subject><subject>Stochastic models</subject><subject>Studies</subject><subject>Theory of Computation</subject><issn>1432-4350</issn><issn>1433-0490</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><sourceid>M0C</sourceid><recordid>eNp1kMFOwzAMhiMEEmPwANwmLpwCTpw0RJzQxAAxiQNwjtI2HZ3aZSTdxN6elCJNQuJky_782_4JOWdwxQDUdQTgXFAATTVHTsUBGTGBSEFoOPzJUxElHJOTGJcAgDcAI3L77JvWL3zwWzr3W9fYVTl57XzxYWNXF3W3m_SVPTWZ-nbduK_UOSVHlW2iO_uNY_I-u3-bPtL5y8PT9G5OCxSqo06BA5sxoZAJgDLPmUSWM1GizHSeZzyTvHCV1JYzBnkpUaEsbcFV5lBXOCaXg-46-M-Ni51p61i4Jt3q_CYalf7SkgmRyIs_5NJvwiodZzgqnhZplSA2QEXwMQZXmXWoWxt2hoHpzTSDmSaZaXozTS_Mh5mY2NXChb3w_0Pf09B1zg</recordid><startdate>20100401</startdate><enddate>20100401</enddate><creator>Bienvenu, Laurent</creator><general>Springer-Verlag</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope><scope>0U~</scope><scope>1-H</scope><scope>3V.</scope><scope>7SC</scope><scope>7WY</scope><scope>7WZ</scope><scope>7XB</scope><scope>87Z</scope><scope>88I</scope><scope>8AL</scope><scope>8AO</scope><scope>8FD</scope><scope>8FE</scope><scope>8FG</scope><scope>8FK</scope><scope>8FL</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>ARAPS</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BEZIV</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>FRNLG</scope><scope>F~G</scope><scope>GNUQQ</scope><scope>HCIFZ</scope><scope>JQ2</scope><scope>K60</scope><scope>K6~</scope><scope>K7-</scope><scope>L.-</scope><scope>L.0</scope><scope>L6V</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>M0C</scope><scope>M0N</scope><scope>M2P</scope><scope>M7S</scope><scope>P5Z</scope><scope>P62</scope><scope>PQBIZ</scope><scope>PQBZA</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PTHSS</scope><scope>PYYUZ</scope><scope>Q9U</scope></search><sort><creationdate>20100401</creationdate><title>Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity</title><author>Bienvenu, Laurent</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Algorithms</topic><topic>Bias</topic><topic>Binary system</topic><topic>Codes</topic><topic>Computer Science</topic><topic>Mathematical analysis</topic><topic>Random variables</topic><topic>Stochastic models</topic><topic>Studies</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Bienvenu, Laurent</creatorcontrib><collection>CrossRef</collection><collection>Global News &amp; ABI/Inform Professional</collection><collection>Trade PRO</collection><collection>ProQuest Central (Corporate)</collection><collection>Computer and Information Systems Abstracts</collection><collection>ABI/INFORM Collection (ProQuest)</collection><collection>ABI/INFORM Global (PDF only)</collection><collection>ProQuest Central (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection</collection><collection>Science Database (Alumni Edition)</collection><collection>Computing Database (Alumni Edition)</collection><collection>ProQuest Pharma Collection</collection><collection>Technology Research Database</collection><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>ProQuest Central (Alumni) (purchase pre-March 2016)</collection><collection>ABI/INFORM Collection (Alumni Edition)</collection><collection>Materials Science &amp; Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central UK/Ireland</collection><collection>Advanced Technologies &amp; Aerospace Database‎ (1962 - current)</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Business Premium Collection</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>Business Premium Collection (Alumni)</collection><collection>ABI/INFORM Global (Corporate)</collection><collection>ProQuest Central Student</collection><collection>SciTech Premium Collection (Proquest) (PQ_SDU_P3)</collection><collection>ProQuest Computer Science Collection</collection><collection>ProQuest Business Collection (Alumni Edition)</collection><collection>ProQuest Business Collection</collection><collection>Computer Science Database</collection><collection>ABI/INFORM Professional Advanced</collection><collection>ABI/INFORM Professional Standard</collection><collection>ProQuest Engineering Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>ABI/INFORM Global</collection><collection>Computing Database</collection><collection>Science Database (ProQuest)</collection><collection>ProQuest Engineering Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Database</collection><collection>ProQuest Advanced Technologies &amp; Aerospace Collection</collection><collection>One Business (ProQuest)</collection><collection>ProQuest One Business (Alumni)</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>Engineering Collection</collection><collection>ABI/INFORM Collection China</collection><collection>ProQuest Central Basic</collection><jtitle>Theory of computing systems</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Bienvenu, Laurent</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity</atitle><jtitle>Theory of computing systems</jtitle><stitle>Theory Comput Syst</stitle><date>2010-04-01</date><risdate>2010</risdate><volume>46</volume><issue>3</issue><spage>598</spage><epage>617</epage><pages>598-617</pages><issn>1432-4350</issn><eissn>1433-0490</eissn><coden>TCSYFI</coden><abstract>Merkle et al. (Ann. Pure Appl. Logic 138(1–3):183–210, 2006 ) showed that all Kolmogorov-Loveland stochastic infinite binary sequences have constructive Hausdorff dimension 1. In this paper, we go even further, showing that from an infinite sequence of dimension less than (ℋ being the Shannon entropy function) one can extract by an effective selection rule a biased subsequence with bias at least δ . We also prove an analogous result for finite strings.</abstract><cop>New York</cop><pub>Springer-Verlag</pub><doi>10.1007/s00224-009-9232-4</doi><tpages>20</tpages></addata></record>
fulltext fulltext
identifier ISSN: 1432-4350
ispartof Theory of computing systems, 2010-04, Vol.46 (3), p.598-617
issn 1432-4350
1433-0490
language eng
recordid cdi_proquest_miscellaneous_743595144
source ABI/INFORM Global; Springer Link; BSC - Ebsco (Business Source Ultimate)
subjects Algorithms
Bias
Binary system
Codes
Computer Science
Mathematical analysis
Random variables
Stochastic models
Studies
Theory of Computation
title Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T17%3A58%3A31IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Kolmogorov-Loveland%20Stochasticity%20and%20Kolmogorov%20Complexity&rft.jtitle=Theory%20of%20computing%20systems&rft.au=Bienvenu,%20Laurent&rft.date=2010-04-01&rft.volume=46&rft.issue=3&rft.spage=598&rft.epage=617&rft.pages=598-617&rft.issn=1432-4350&rft.eissn=1433-0490&rft.coden=TCSYFI&rft_id=info:doi/10.1007/s00224-009-9232-4&rft_dat=%3Cproquest_cross%3E1963694261%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c347t-e70e0a614731400dbb1531b14d3569bb62652cef59a2110bd53735dac276e39f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=237226597&rft_id=info:pmid/&rfr_iscdi=true