A polynomial-time algorithm for computing absolutely normal numbers

dc.creatorBecher, Veronica Andrea
dc.creatorHeiber, Pablo Ariel
dc.creatorSlaman, Theodore A.
dc.date.accessioned2017-04-24T15:42:45Z
dc.date.accessioned2018-11-06T12:09:24Z
dc.date.available2017-04-24T15:42:45Z
dc.date.available2018-11-06T12:09:24Z
dc.date.created2017-04-24T15:42:45Z
dc.date.issued2013-11
dc.identifierBecher, Veronica Andrea; Heiber, Pablo Ariel; Slaman, Theodore A.; A polynomial-time algorithm for computing absolutely normal numbers; Elsevier Inc; Information And Computation; 232; 11-2013; 1-9
dc.identifier0890-5401
dc.identifierhttp://hdl.handle.net/11336/15636
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1863734
dc.description.abstractWe give an algorithm to compute an absolutely normal number so that the first n digits in its binary expansion are obtained in time polynomial in n; in fact, just above quadratic. The algorithm uses combinatorial tools to control divergence from normality. Speed of computation is achieved at the sacrifice of speed of convergence to normality.
dc.languageeng
dc.publisherElsevier Inc
dc.relationinfo:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.ic.2013.08.013
dc.relationinfo:eu-repo/semantics/altIdentifier/url/http://www.sciencedirect.com/science/article/pii/S0890540113000904
dc.rightshttps://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.rightsinfo:eu-repo/semantics/restrictedAccess
dc.subjectNormal Numbers
dc.subjectAbsolutely Normal Numbers
dc.subjectComputable Normal Numbers
dc.titleA polynomial-time algorithm for computing absolutely normal numbers
dc.typeArtículos de revistas
dc.typeArtículos de revistas
dc.typeArtículos de revistas


Este ítem pertenece a la siguiente institución