Mostrar el registro sencillo del ítem
dc.contributor.author
Almarza, Javier Ignacio
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.contributor.author
Figueira, Santiago
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.date.available
2018-04-23T21:18:51Z
dc.date.issued
2015-04
dc.identifier.citation
Almarza, Javier Ignacio; Figueira, Santiago; Normality in non-integer bases and polynomial time randomness; Academic Press Inc Elsevier Science; Journal of Computer and System Sciences; 81; 7; 4-2015; 1059-1087
dc.identifier.issn
0022-0000
dc.identifier.uri
http://hdl.handle.net/11336/43163
dc.description.abstract
It is known that if x ∈ [0, 1] is polynomial time random (i.e. no polynomial time computable martingale succeeds on the binary fractional expansion of x) then x is normal in any integer base greater than one. We show that if x is polynomial time random and β > 1 is Pisot, then x is “normal in base β”, in the sense that the sequence (xβn)n∈N is uniformly distributed modulo one. We work with the notion of P-martingale, a generalization of martingales to non-uniform distributions, and show that a sequence over a finite alphabet is distributed according to an irreducible, invariant Markov measure P if an only if no P-martingale whose betting factors are computed by a deterministic finite automaton succeeds on it. This is a generalization of Schnorr and Stimm’s characterization of normal sequences in integer bases. Our results use tools and techniques from symbolic dynamics, together with automata theory and algorithmic randomness.
dc.format
application/pdf
dc.language.iso
eng
dc.publisher
Academic Press Inc Elsevier Science
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.rights
info:eu-repo/semantics/openAccess
dc.rights.uri
https://creativecommons.org/licenses/by-nc-nd/2.5/ar/
dc.subject
Algorithmic Randomness
dc.subject
Deterministic Finite Automaton
dc.subject
Subshift
dc.subject
Pisot Number
dc.subject
Normality
dc.subject
Polynomial Randomness
dc.subject
Martingale
dc.subject.classification
Matemática Pura
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
Matemáticas
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.subject.classification
CIENCIAS NATURALES Y EXACTAS
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.title
Normality in non-integer bases and polynomial time randomness
dc.type
info:eu-repo/semantics/article
dc.type
info:ar-repo/semantics/artículo
dc.type
info:eu-repo/semantics/publishedVersion
dc.date.updated
2018-04-16T14:55:54Z
dc.identifier.eissn
1090-2724
dc.journal.volume
81
dc.journal.number
7
dc.journal.pagination
1059-1087
dc.journal.pais
Países Bajos
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.journal.ciudad
Amsterdam
dc.description.fil
Fil: Almarza, Javier Ignacio. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina
dc.description.fil
Fil: Figueira, Santiago. Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina
dc.journal.title
Journal of Computer and System Sciences
![Se ha confirmado la validez de este valor de autoridad por un usuario](/themes/CONICETDigital/images/authority_control/invisible.gif)
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/10.1016/j.jcss.2015.04.005
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://www.sciencedirect.com/science/article/pii/S0022000015000434
dc.relation.alternativeid
info:eu-repo/semantics/altIdentifier/url/https://arxiv.org/abs/1410.8594
Archivos asociados