LIPIcs, Volume 159
AofA 2020, June 15-19, 2020, Klagenfurt, Austria (Virtual Conference)
Editors: Michael Drmota and Clemens Heuberger
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 1-402, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Proceedings{drmota_et_al:LIPIcs.AofA.2020, title = {{LIPIcs, Volume 159, AofA 2020, Complete Volume}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {1--402}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020}, URN = {urn:nbn:de:0030-drops-120296}, doi = {10.4230/LIPIcs.AofA.2020}, annote = {Keywords: LIPIcs, Volume 159, AofA 2020, Complete Volume} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{drmota_et_al:LIPIcs.AofA.2020.0, author = {Drmota, Michael and Heuberger, Clemens}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {0:i--0:xii}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.0}, URN = {urn:nbn:de:0030-drops-120309}, doi = {10.4230/LIPIcs.AofA.2020.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Andrei Asinowski and Cyril Banderier. On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{asinowski_et_al:LIPIcs.AofA.2020.1, author = {Asinowski, Andrei and Banderier, Cyril}, title = {{On Lattice Paths with Marked Patterns: Generating Functions and Multivariate Gaussian Distribution}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.1}, URN = {urn:nbn:de:0030-drops-120317}, doi = {10.4230/LIPIcs.AofA.2020.1}, annote = {Keywords: Lattice path, Dyck path, Motzkin path, generating function, algebraic function, kernel method, context-free grammar, multivariate Gaussian distribution} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Cyril Banderier, Marie-Louise Lackner, and Michael Wallner. Latticepathology and Symmetric Functions (Extended Abstract). In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 2:1-2:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{banderier_et_al:LIPIcs.AofA.2020.2, author = {Banderier, Cyril and Lackner, Marie-Louise and Wallner, Michael}, title = {{Latticepathology and Symmetric Functions (Extended Abstract)}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {2:1--2:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.2}, URN = {urn:nbn:de:0030-drops-120329}, doi = {10.4230/LIPIcs.AofA.2020.2}, annote = {Keywords: Lattice path, generating function, symmetric function, algebraic function, kernel method, context-free grammar, Sparre Andersen formula, Spitzer’s identity, Wiener - Hopf factorization} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Frédérique Bassino, Tsinjo Rakotoarimalala, and Andrea Sportiello. The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bassino_et_al:LIPIcs.AofA.2020.3, author = {Bassino, Fr\'{e}d\'{e}rique and Rakotoarimalala, Tsinjo and Sportiello, Andrea}, title = {{The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.3}, URN = {urn:nbn:de:0030-drops-120336}, doi = {10.4230/LIPIcs.AofA.2020.3}, annote = {Keywords: Average-case analysis of algorithms, String Pattern Matching, Computational Complexity bounds} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Valérie Berthé, Eda Cesaratto, Frédéric Paccaut, Pablo Rotondo, Martín D. Safe, and Brigitte Vallée. Two Arithmetical Sources and Their Associated Tries. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berthe_et_al:LIPIcs.AofA.2020.4, author = {Berth\'{e}, Val\'{e}rie and Cesaratto, Eda and Paccaut, Fr\'{e}d\'{e}ric and Rotondo, Pablo and Safe, Mart{\'\i}n D. and Vall\'{e}e, Brigitte}, title = {{Two Arithmetical Sources and Their Associated Tries}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.4}, URN = {urn:nbn:de:0030-drops-120345}, doi = {10.4230/LIPIcs.AofA.2020.4}, annote = {Keywords: Combinatorics of words, Information Theory, Probabilistic analysis, Analytic combinatorics, Dirichlet generating functions, Sources, Partitions, Trie structure, Continued fraction expansion, Farey map, Sturm words, Transfer operator} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Gabriel Berzunza, Xing Shi Cai, and Cecilia Holmgren. The k-Cut Model in Conditioned Galton-Watson Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.5, author = {Berzunza, Gabriel and Cai, Xing Shi and Holmgren, Cecilia}, title = {{The k-Cut Model in Conditioned Galton-Watson Trees}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {5:1--5:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.5}, URN = {urn:nbn:de:0030-drops-120352}, doi = {10.4230/LIPIcs.AofA.2020.5}, annote = {Keywords: k-cut, cutting, conditioned Galton-Watson trees} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Gabriel Berzunza and Cecilia Holmgren. Largest Clusters for Supercritical Percolation on Split Trees. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 6:1-6:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{berzunza_et_al:LIPIcs.AofA.2020.6, author = {Berzunza, Gabriel and Holmgren, Cecilia}, title = {{Largest Clusters for Supercritical Percolation on Split Trees}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {6:1--6:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.6}, URN = {urn:nbn:de:0030-drops-120361}, doi = {10.4230/LIPIcs.AofA.2020.6}, annote = {Keywords: Split trees, random trees, supercritical bond-percolation, cluster size, Poisson measures} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Jacopo Borga and Mickaël Maazoun. Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{borga_et_al:LIPIcs.AofA.2020.7, author = {Borga, Jacopo and Maazoun, Micka\"{e}l}, title = {{Scaling and Local Limits of Baxter Permutations Through Coalescent-Walk Processes}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {7:1--7:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.7}, URN = {urn:nbn:de:0030-drops-120370}, doi = {10.4230/LIPIcs.AofA.2020.7}, annote = {Keywords: Local and scaling limits, permutations, planar maps, random walks in cones} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Mireille Bousquet-Mélou and Michael Wallner. More Models of Walks Avoiding a Quadrant. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bousquetmelou_et_al:LIPIcs.AofA.2020.8, author = {Bousquet-M\'{e}lou, Mireille and Wallner, Michael}, title = {{More Models of Walks Avoiding a Quadrant}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {8:1--8:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.8}, URN = {urn:nbn:de:0030-drops-120383}, doi = {10.4230/LIPIcs.AofA.2020.8}, annote = {Keywords: Enumerative combinatorics, lattice paths, non-convex cones, algebraic series, D-finite series} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
François Chapon, Éric Fusy, and Kilian Raschel. Polyharmonic Functions And Random Processes in Cones. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chapon_et_al:LIPIcs.AofA.2020.9, author = {Chapon, Fran\c{c}ois and Fusy, \'{E}ric and Raschel, Kilian}, title = {{Polyharmonic Functions And Random Processes in Cones}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {9:1--9:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.9}, URN = {urn:nbn:de:0030-drops-120390}, doi = {10.4230/LIPIcs.AofA.2020.9}, annote = {Keywords: Brownian motion in cones, Heat kernel, Random walks in cones, Harmonic functions, Polyharmonic functions, Complete asymptotic expansions, Functional equations} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Michael Drmota, Marc Noy, and Benedikt Stufler. Cut Vertices in Random Planar Maps. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{drmota_et_al:LIPIcs.AofA.2020.10, author = {Drmota, Michael and Noy, Marc and Stufler, Benedikt}, title = {{Cut Vertices in Random Planar Maps}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.10}, URN = {urn:nbn:de:0030-drops-120403}, doi = {10.4230/LIPIcs.AofA.2020.10}, annote = {Keywords: random planar maps, cut vertices, generating functions, local graph limits} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Andrew Elvey Price, Wenjie Fang, and Michael Wallner. Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{elveyprice_et_al:LIPIcs.AofA.2020.11, author = {Elvey Price, Andrew and Fang, Wenjie and Wallner, Michael}, title = {{Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {11:1--11:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.11}, URN = {urn:nbn:de:0030-drops-120419}, doi = {10.4230/LIPIcs.AofA.2020.11}, annote = {Keywords: Airy function, asymptotics, directed acyclic graphs, Dyck paths, bijection, stretched exponential, compacted trees, minimal automata, finite languages} }
Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)
Ilse Fischer and Matjaž Konvalinka. The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem. In 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 159, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fischer_et_al:LIPIcs.AofA.2020.12, author = {Fischer, Ilse and Konvalinka, Matja\v{z}}, title = {{The First Bijective Proof of the Alternating Sign Matrix Theorem Theorem}}, booktitle = {31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)}, pages = {12:1--12:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-147-4}, ISSN = {1868-8969}, year = {2020}, volume = {159}, editor = {Drmota, Michael and Heuberger, Clemens}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2020.12}, URN = {urn:nbn:de:0030-drops-120424}, doi = {10.4230/LIPIcs.AofA.2020.12}, annote = {Keywords: enumeration, bijective proof, alternating sign matrix, plane partition} }
Feedback for Dagstuhl Publishing