Two Arithmetical Sources and Their Associated Tries | ||
| dc.conicet.organizacion | Universite de Paris | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas | |
| dc.conicet.organizacion | Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano | |
| dc.conicet.organizacion | Université de Picardie Jules Verne | |
| dc.conicet.organizacion | Université de Rouen | |
| dc.conicet.organizacion | Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Matemática Bahía Blanca. Universidad Nacional del Sur. Departamento de Matemática. Instituto de Matemática Bahía Blanca | |
| dc.conicet.organizacion | Universite de Caen Basse Normandie | |
| dc.conicet.organizacion | Centre National de la Recherche Scientifique | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.conicet.rol | Autor | |
| dc.contributor.author | Berthé, Valérie | |
| dc.contributor.author | Cesaratto, Eda | |
| dc.contributor.author | Paccaut, Frédéric | |
| dc.contributor.author | Rotondo, Pablo | |
| dc.contributor.author | Safe, Martin Dario | |
| dc.contributor.author | Vallée, Brigitte | |
| dc.coverage | Internacional | |
| dc.date.evento | 2020-06-15 | |
| dc.date.eventoHasta | 2020-06-19 | |
| dc.date.issued | 2020 | es |
| dc.description.abstract | This article is devoted to the study of two arithmetical sources associated with classical partitions, that are both defined through the mediant of two fractions. The Stern-Brocot source is associated with the sequence of all the mediants, while the Sturm source only keeps mediants whose denominator is “not too large”. Even though these sources are both of zero Shannon entropy, with very similar Renyi entropies, their probabilistic features yet appear to be quite different. We then study how they influence the behaviour of tries built on words they emit, and we notably focus on the trie depth. The paper deals with Analytic Combinatorics methods, and Dirichlet generating functions, that are usually used and studied in the case of good sources with positive entropy. To the best of our knowledge, the present study is the first one where these powerful methods are applied to a zero-entropy context. In our context, the generating function associated with each source is explicit and related to classical functions in Number Theory, as the ζ function, the double ζ function or the transfer operator associated with the Gauss map. We obtain precise asymptotic estimates for the mean value of the trie depth that prove moreover to be quite different for each source. Then, these sources provide explicit and natural instances which lead to two unusual and different trie behaviours. | es |
| dc.description.fil | Fil: Berthé, Valérie. Universite de Paris; Francia | |
| dc.description.fil | Fil: Cesaratto, Eda. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad Nacional de General Sarmiento. Instituto del Desarrollo Humano; Argentina | |
| dc.description.fil | Fil: Paccaut, Frédéric. Université de Picardie Jules Verne; Francia | |
| dc.description.fil | Fil: Rotondo, Pablo. Université de Rouen; Francia | |
| dc.description.fil | Fil: Safe, Martin Dario. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Bahía Blanca. Instituto de Matemática Bahía Blanca. Universidad Nacional del Sur. Departamento de Matemática. Instituto de Matemática Bahía Blanca; Argentina | |
| dc.description.fil | Fil: Vallée, Brigitte. Universite de Caen Basse Normandie; Francia. Centre National de la Recherche Scientifique; Francia | |
| dc.description.institucionOrganizadora | Committee and the Steering Committee | es |
| dc.description.nombreEvento | 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms | es |
| dc.description.paisEvento | Austria | es |
| dc.format | application/pdf | es |
| dc.identifier.citation | Two Arithmetical Sources and Their Associated Tries; 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms; Austria; 2020; 2-19 | es |
| dc.identifier.eissn | 1868-8969 | es |
| dc.identifier.institucional | CONICET | |
| dc.identifier.repo | CONICET Digital | |
| dc.identifier.uri | http://hdl.handle.net/11336/137893 | |
| dc.journal.ciudad | Dagstuhl | es |
| dc.journal.pagination | 2-19 | es |
| dc.journal.pais | Alemania | es |
| dc.language.iso | eng | es |
| dc.publisher | Schloss Dagstuhl. Zentrum für Informatik | es |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.math.aau.at/AofA2020/ | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/url/https://www.dagstuhl.de/en/publications/lipics | |
| dc.relation.alternativeid | info:eu-repo/semantics/altIdentifier/doi/http://dx.doi.org/ 10.4230/LIPIcs.AofA.2020.4 | |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | https://creativecommons.org/licenses/by/2.5/ar/ | * |
| dc.source.revista | Leibniz International Proceedings in Informatics | es |
| dc.subject | COMBINATORICS OF WORDS | es |
| dc.subject | INFORMATION THEORY | es |
| dc.subject | PROBABILISTIC ANALYSIS | es |
| dc.subject | ANALYTIC COMBINATORICS | es |
| dc.subject | DIRICHLET GENERATING FUNCTIONS | es |
| dc.subject | SOURCES | es |
| dc.subject | PARTITIONS | es |
| dc.subject | TRIE STRUCTURE | es |
| dc.subject | CONTINUED FRACTION EXPASION | es |
| dc.subject | FAREY MAP | es |
| dc.subject | STURM WORDS | es |
| dc.subject | TRANSFER OPERATOR | es |
| dc.subject.classification | Matemática Aplicada | es |
| dc.subject.classification | Matemáticas | es |
| dc.subject.classification | CIENCIAS NATURALES Y EXACTAS | es |
| dc.title | Two Arithmetical Sources and Their Associated Tries | es |
| dc.type | info:eu-repo/semantics/publishedVersion | |
| dc.type | info:eu-repo/semantics/conferenceObject | |
| dc.type | info:ar-repo/semantics/documento de conferencia | |
| dc.type.publicacion | Journal | es |
| dc.type.subtype | Conferencia | es |
Archivos
Bloque original
Cargando...
- Nombre:
- CONICET_Digital_Nro.4057151c-4ec7-4a52-b371-be7cd36401bd_A.pdf
- Tamaño:
- 583.49 KB
- Formato:
- Adobe Portable Document Format