Forschung | AAU Campus

Projekt: Analytic Combinatorics: Digits, Automat...

Stammdaten

Englisch

Titel:	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 asymptotic and probabilistic behavior of a sequence defined by an automaton depends on certain properties of the underlying graph, in particular, on connectivity properties. Considering digit expansions as special partitions leads to an interpretation as certain trees. The analysis of parameters of these trees leads to results on the corresponding partitions. This project proposes to investigate questions on those topics from the viewpoint of analytic combinatorics, emphasizing connections between these areas. 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

Funktion

Zeitraum

(intern)

Projektleiter/in

01.06.2016 - 31.05.2021

(intern)

wiss. Mitarbeiter/in

01.11.2018 - 31.05.2021

(intern)

wiss. Mitarbeiter/in
Dissertant/in
Kooperationspartner/in

01.06.2018 - 31.08.2018
15.01.2018 - 31.05.2018
01.06.2018 - 31.05.2021

(intern)

Kooperationspartner/in

01.06.2016 - 31.05.2021

(intern)

Dissertant/in

07.01.2019 - 31.05.2021

Zuordnung

Organisationseinheit

Fakultät für Technische Wissenschaften

Kategorisierung

Projekttyp	Forschungsförderung (auf Antrag oder Ausschreibung)
Förderungstyp	§26
Forschungstyp	Grundlagenforschung
Sachgebiete	101002 - Analysis 101012 - Kombinatorik 101024 - Wahrscheinlichkeitstheorie 101025 - Zahlentheorie
Forschungscluster	Kein Forschungscluster ausgewählt
Genderrelevanz	Genderrelevanz nicht ausgewählt
Projektfokus	Science to Science (Qualitätsindikator: I) Klassifikationsraster der zugeordneten Organisationseinheiten: Institut für Mathematik
Arbeitsgruppen	Diskrete Mathematik und Optimierung

Finanzierung

Förderprogramm

Kooperationen

Organisation

Adresse

S:t Olofsgatan 10B
SE - 75105 Uppsala

ZA 7602 Stellenbosch

TW 115 Taipei

Rechbauerstraße 12
AT - 8020 Graz

Forschungsaktivitäten

Hier werden alle mit diesem Projekt in Zusammenhang stehenden Forschungsaktivitäten angezeigt. Mit dem untenstehenden Link können sie sich diese Forschungsaktivitäten in der Suche anzeigen lassen und gegebenenfalls exportieren.

(Achtung: Externe Aktivitäten werden im Suchergebnis nicht mitangezeigt)

Zugehörige Forschungsaktivitäten in der Suche anzeigen

Projekte	Keine verknüpften Projekte vorhanden
Publikationen	Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus (2018) C. Heuberger, D. Krenn, H. Prodinger 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) Kein Verlag ausgewählt zur Publikation Irreducible polynomials in Int(Z) Irreducible polynomials in Int(Z) (2018) R. Rissner, S. Nakato, A. Antoniou International Conference on Mathematics (ICM 2018) Recent Advances in Algebra, Numerical Analysis, Applied Analysis and Statistics Kein Verlag ausgewählt zur Publikation A Combinatorial Identity for Rooted Labelled Forests A Combinatorial Identity for Rooted Labelled Forests (2019) B. Hackl Aequationes mathematicae Kein Verlag ausgewählt zur Publikation Pop-stack sorting and its image: Permutations with overlapping runs Pop-stack sorting and its image: Permutations with overlapping runs (2019) A. Asinowski, C. Banderier, S. Billey, B. Hackl, S. Linusson Acta Mathematica Universitatis Comenianae Kein Verlag ausgewählt zur Publikation Reducing Simply Generated Trees by Iterative Leaf Cutting. Reducing Simply Generated Trees by Iterative Leaf Cutting. (2019) B. Hackl, C. Heuberger, S. Wagner 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) Kein Verlag ausgewählt zur Publikation The Necklace Process: A Generating Function Approach The Necklace Process: A Generating Function Approach (2018) B. Hackl, H. Prodinger Statistics & Probability Letters Kein Verlag ausgewählt zur Publikation Sets of lengths of factorizations of integer-valued polynomials on Dedekind domains with finite residue fields Sets of lengths of factorizations of integer-valued polynomials on Dedekind domains with finite residue fields (2019) S. Frisch, S. Nakato, R. Rissner Journal of Algebra Kein Verlag ausgewählt zur Publikation Non-minimality of the width-w non-adjacent form in conjunction with trace one τ-adic digit expansions and Koblitz curves in characteristic two Non-minimality of the width-w non-adjacent form in conjunction with trace one τ-adic digit expansions and Koblitz curves in characteristic two (2017) D. Krenn, V. Ziegler Mathematics of Computation Kein Verlag ausgewählt zur Publikation Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences (2019) C. Heuberger, D. Krenn Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO19) Kein Verlag ausgewählt zur Publikation Asymptotic Analysis of Regular Sequences Asymptotic Analysis of Regular Sequences (2019) C. Heuberger, D. Krenn Algorithmica Kein Verlag ausgewählt zur Publikation Flip-sort and extremal cases of pop-stack sorting Flip-sort and extremal cases of pop-stack sorting (2019) A. Asinowski, C. Banderier, B. Hackl Permutation Patterns 2019, University of Zurich Kein Verlag ausgewählt zur Publikation Counting ascents in generalized Dyck paths Counting ascents in generalized Dyck paths (2018) B. Hackl, C. Heuberger, H. Prodinger 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) Kein Verlag ausgewählt zur Publikation
Veranstaltungen	Keine verknüpften Veranstaltung vorhanden
Vorträge	Iterative Cutting of Non-Catalan Trees Iterative Cutting of Non-Catalan Trees B. Hackl Universität Klagenfurt , Österreich seit 17.07.2018 Zum Vortrag Digit Expansions in Elliptic Curve Cryptography Digit Expansions in Elliptic Curve Cryptography C. Heuberger Klagenfurt , Österreich seit 19.06.2018 Zum Vortrag Lessons Learned from Cutting Trees Lessons Learned from Cutting Trees B. Hackl seit 10.12.2019 Zum Vortrag Cutting Down and Growing Trees Cutting Down and Growing Trees B. Hackl seit 09.05.2019 Zum Vortrag Flip-Sorting and Step-Changing Lattice Walks, or: Asymptotic Counting and Analytic Properties via Algebraic Classification Flip-Sorting and Step-Changing Lattice Walks, or: Asymptotic Counting and Analytic Properties via Algebraic Classification B. Hackl seit 11.09.2019 Zum Vortrag Cutting Down and Growing Trees Cutting Down and Growing Trees B. Hackl seit 05.06.2019 Zum Vortrag From Touchard to Growing Trees and Lattice Paths From Touchard to Growing Trees and Lattice Paths B. Hackl seit 27.02.2019 Zum Vortrag Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences Esthetic Numbers and Lifting Restrictions on the Analysis of Summatory Functions of Regular Sequences C. Heuberger, D. Krenn seit 06.01.2019 Zum Vortrag Digits, Transducers, Regular Sequences Digits, Transducers, Regular Sequences C. Heuberger seit 27.02.2019 Zum Vortrag Flip sort and extremal cases of pop-stack sorting Flip sort and extremal cases of pop-stack sorting A. Asinowski, A. Asinowski, C. Banderier, B. Hackl seit 18.06.2019 Zum Vortrag Algorithmic counting of nonequivalent compact Huffman codes Algorithmic counting of nonequivalent compact Huffman codes C. Heuberger seit 26.06.2019 Zum Vortrag Pop-stack sorting and its image: Permutations with overlapping runs Pop-stack sorting and its image: Permutations with overlapping runs A. Asinowski, A. Asinowski, C. Banderier, S. Billey, B. Hackl, S. Linusson seit 26.08.2019 Zum Vortrag Reducing Simply Generated Trees by Iterative Leaf Cutting. Reducing Simply Generated Trees by Iterative Leaf Cutting. B. Hackl, C. Heuberger, S. Wagner seit 06.01.2019 Zum Vortrag Analysis of sequences using transducer automata Analysis of sequences using transducer automata C. Heuberger seit 12.04.2018 Zum Vortrag Cutting Down and Growing Trees Cutting Down and Growing Trees B. Hackl seit 28.05.2018 Zum Vortrag From the Lifting-the-Exponent-Lemma to Elliptic curves with isomorphic groups of points – how Olympiad Mathematics influences Mathematical Research From the Lifting-the-Exponent-Lemma to Elliptic curves with isomorphic groups of points – how Olympiad Mathematics influences Mathematical Research C. Heuberger, C. Heuberger, M. Mazzoli seit 19.07.2018 Zum Vortrag Counting Ascents in Generalized Dyck Paths Counting Ascents in Generalized Dyck Paths B. Hackl, C. Heuberger, H. Prodinger seit 29.06.2018 Zum Vortrag Ascents of Non-Negative Lattice Paths Ascents of Non-Negative Lattice Paths B. Hackl, C. Heuberger, S. Wagner seit 14.02.2018 Zum Vortrag Irreducible polynomials in Int(Z) Irreducible polynomials in Int(Z) R. Rissner seit 19.12.2018 Zum Vortrag Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus Analysis of Summatory Functions of Regular Sequences: Transducer and Pascal's Rhombus C. Heuberger seit 21.02.2018 Zum Vortrag An extended note on the comparison-optimal dual-pivot quickselect An extended note on the comparison-optimal dual-pivot quickselect D. Krenn, D. Krenn seit 16.01.2017 Zum Vortrag Precise analysis of the optimal multi-pivot quicksort Precise analysis of the optimal multi-pivot quicksort D. Krenn seit 22.06.2017 Zum Vortrag