Projekt: Analytic Combinatorics: Digits, Automat...
Stammdaten
Analytic Combinatorics: Digits, Automata and Trees | |
Beschreibung: | Digit expansions, automata and trees are the objects, as well as the tools, of this research proposal. Digit expansions to various bases with redundant digit sets act as key ingredients for efficient arithmetic operations in abelian groups. Automata can frequently be used to describe and analyze these digit representations. The Our motivation for studying redundant digit expansions comes from public-key cryptography: It relies on efficient scalar multiplication in abelian groups such as the point group of an elliptic curve. The redundancy can be used for minimizing the Hamming weight of the expansion and thus the number of expensive curve operations. Choosing efficient endomorphisms instead of the classical doubling operation requires digit expansions with complex bases. Comparing different algorithms requires a precise asymptotic analysis of these expansions. Many sequences occurring in the analysis of digit expansions are special q-regular sequences. While many can even be defined as the output of a transducer and thus can be analyzed completely, some questions, such as the number of minimal expansions, display a different asymptotic behavior. It is one aim of this project to find suitable conditions on q-regular sequences to extend the analysis from the case of transducers. Seeing digit expansions as partitions provides a different point of view. The summands of these partitions are powers of the base, and additional restrictions on the number of equal summands model the digit set. Lifting this restriction leads to partitions which can be analyzed by a related class of trees. The quasi-power theorem is an invaluable tool when proving asymptotic normality of some of the occurring random variables. We intend to prove higher dimensional analogues of this theorem as well as to thoroughly discuss its variability condition. Other limiting distributions are expected to appear in the analysis of word problems. These problems, e.g., certain types of runs, come from various digit problems such as addition. We plan to use methods from analytic combinatorics such as singularity analysis, saddle point method and Mellin transform as well as tools from probability theory such as limit theorems and mixing theorems. |
Schlagworte: | Analytic Combinatorics, Digit Expansion, Sequence, Automaton, Tree, Limit Theorem |
Kurztitel: | Analytic Combinatorics: DAT |
Zeitraum: | 01.06.2016 - 31.05.2021 |
Kontakt-Email: | - |
Homepage: | https://www.math.aau.at/P28466/ |
MitarbeiterInnen
MitarbeiterInnen | Funktion | Zeitraum |
---|---|---|
Clemens Heuberger (intern) |
|
|
Andrei Asinowski (intern) |
|
|
Benjamin Hackl (intern) |
|
|
Daniel Krenn (intern) |
|
|
Sarah Jane Selkirk (intern) |
|
|
Dunja Pucher (intern) |
|
|
Jutta Astrid Rath (intern) |
|
|
Zuordnung
Organisationseinheit | ||||
---|---|---|---|---|
Fakultät für Technische Wissenschaften
Institut für Mathematik
|
Kategorisierung
Projekttyp | Forschungsförderung (auf Antrag oder Ausschreibung) |
Förderungstyp | §26 |
Forschungstyp |
|
Sachgebiete | |
Forschungscluster | Kein Forschungscluster ausgewählt |
Genderrelevanz | Genderrelevanz nicht ausgewählt |
Projektfokus |
Klassifikationsraster der zugeordneten Organisationseinheiten:
|
Arbeitsgruppen |
|
Kooperationen
Organisation | Adresse | ||||||
---|---|---|---|---|---|---|---|
American University of Sharjah
|
AE
|
||||||
Uppsala Universitet
|
SE - 75105 Uppsala |
||||||
University of Stellenbosch
|
ZA
7602 Stellenbosch |
||||||
Academia Sinica
|
TW
115 Taipei |
||||||
Technische Universität Graz
|
AT - 8010 Graz |
Forschungsaktivitäten
(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)
Projekte | Keine verknüpften Projekte vorhanden |
Publikationen |
|
Veranstaltungen | Keine verknüpften Veranstaltung vorhanden |
Vorträge |
|