Normality in non-integer bases and polynomial time randomness | ||
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Matemática | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Oficina de Coordinación Administrativa Ciudad Universitaria | |
| dc.conicet.organizacion | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación | |
| dc.contributor.author | Almarza, Javier Ignacio | |
| dc.contributor.author | Figueira, Santiago | |
| dc.date.issued | 2015-04 | |
| 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. | es |
| 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.format | application/pdf | es |
| 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 | es |
| dc.identifier.eissn | 1090-2724 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.issn | 0022-0000 | es |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/43163 | |
| dc.journal.ciudad | Amsterdam | es |
| dc.journal.number | 7 | es |
| dc.journal.pagination | 1059-1087 | es |
| dc.journal.pais | Países Bajos | es |
| dc.journal.title | Journal of Computer and System Sciences | es |
| dc.journal.volume | 81 | es |
| dc.language.iso | eng | es |
| dc.publisher | Academic Press Inc Elsevier Science | es |
| 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 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/2.5/ar/ | * |
| dc.subject | Algorithmic Randomness | es |
| dc.subject | Deterministic Finite Automaton | es |
| dc.subject | Subshift | es |
| dc.subject | Pisot Number | es |
| dc.subject | Normality | es |
| dc.subject | Polynomial Randomness | es |
| dc.subject | Martingale | es |
| dc.subject.classification | Matemática Pura | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Normality in non-integer bases and polynomial time randomness | es |
| dc.type | info:eu-repo/semantics/article | |
| dc.type | info:ar-repo/semantics/artículo | |
| dc.type | info:eu-repo/semantics/publishedVersion | |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.cf3b7e81-e143-43be-9863-56dd88d68448_A.pdf
- Tamaño:
- 723.96 KB
- Formato:
- Adobe Portable Document Format