4 Search Results for "Sportiello, Andrea"

Document
DOI: 10.4230/LIPIcs.AofA.2022.6
Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps

Authors: Guillaume Chapuy, Baptiste Louf, and Harriet Walsh

Published in: LIPIcs, Volume 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)

Abstract
We study the asymptotic behaviour of random integer partitions under a new probability law that we introduce, the Plancherel-Hurwitz measure. This distribution, which has a natural definition in terms of Young tableaux, is a deformation of the classical Plancherel measure. It appears naturally in the enumeration of Hurwitz maps, or equivalently transposition factorisations in symmetric groups. We study a regime in which the number of factors in the underlying factorisations grows linearly with the order of the group, and the corresponding maps are of high genus. We prove that the limiting behaviour exhibits a new, twofold, phenomenon: the first part becomes very large, while the rest of the partition has the standard Vershik-Kerov-Logan-Shepp limit shape. As a consequence, we obtain asymptotic estimates for unconnected Hurwitz numbers with linear Euler characteristic, which we use to study random Hurwitz maps in this regime. This result can also be interpreted as the return probability of the transposition random walk on the symmetric group after linearly many steps.
Cite as

Guillaume Chapuy, Baptiste Louf, and Harriet Walsh. Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 225, pp. 6:1-6:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chapuy_et_al:LIPIcs.AofA.2022.6,
  author =	{Chapuy, Guillaume and Louf, Baptiste and Walsh, Harriet},
  title =	{{Random Partitions Under the Plancherel-Hurwitz Measure, High Genus Hurwitz Numbers and Maps}},
  booktitle =	{33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022)},
  pages =	{6:1--6:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-230-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{225},
  editor =	{Ward, Mark Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2022.6},
  URN =		{urn:nbn:de:0030-drops-160921},
  doi =		{10.4230/LIPIcs.AofA.2022.6},
  annote =	{Keywords: Random partitions, limit shapes, transposition factorisations, map enumeration, Hurwitz numbers, RSK algorithm, giant components}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.3
The Complexity of the Approximate Multiple Pattern Matching Problem for Random Strings

Authors: Frédérique Bassino, Tsinjo Rakotoarimalala, and Andrea Sportiello

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We describe a multiple string pattern matching algorithm which is well-suited for approximate search and dictionaries composed of words of different lengths. We prove that this algorithm has optimal complexity rate up to a multiplicative constant, for arbitrary dictionaries. This extends to arbitrary dictionaries the classical results of Yao [SIAM J. Comput. 8, 1979], and Chang and Marr [Proc. CPM94, 1994].
Cite as

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)

Copy BibTex To Clipboard

@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.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}
}
Document
DOI: 10.4230/LIPIcs.AofA.2020.11
Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language

Authors: Andrew Elvey Price, Wenjie Fang, and Michael Wallner

Published in: LIPIcs, Volume 159, 31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)

Abstract
We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.
Cite as

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)

Copy BibTex To Clipboard

@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.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}
}
Document
DOI: 10.4230/LIPIcs.STACS.2012.88
Asymptotic enumeration of Minimal Automata

Authors: Frédérique Bassino, Julien David, and Andrea Sportiello

Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Abstract
We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over the possible transition structures, and a binomial distribution over terminal states, with arbitrary parameter b. It turns out that a fraction ~ 1-C(k,b) n^{-k+2} of automata is minimal, with C(k,b) a function, explicitly determined, involving the solution of a transcendental equation.
Cite as

Frédérique Bassino, Julien David, and Andrea Sportiello. Asymptotic enumeration of Minimal Automata. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 88-99, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{bassino_et_al:LIPIcs.STACS.2012.88,
  author =	{Bassino, Fr\'{e}d\'{e}rique and David, Julien and Sportiello, Andrea},
  title =	{{Asymptotic enumeration of Minimal Automata}},
  booktitle =	{29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
  pages =	{88--99},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-35-4},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{14},
  editor =	{D\"{u}rr, Christoph and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.88},
  URN =		{urn:nbn:de:0030-drops-34328},
  doi =		{10.4230/LIPIcs.STACS.2012.88},
  annote =	{Keywords: minimal automata, regular languages, enumeration of random structures}
}
  • Refine by Author
  • 2 Bassino, Frédérique
  • 2 Sportiello, Andrea
  • 1 Chapuy, Guillaume
  • 1 David, Julien
  • 1 Elvey Price, Andrew
  • Show More...

  • Refine by Classification
  • 2 Mathematics of computing → Enumeration
  • 1 Mathematics of computing → Distribution functions
  • 1 Mathematics of computing → Generating functions
  • 1 Mathematics of computing → Random graphs
  • 1 Theory of computation → Design and analysis of algorithms
  • Show More...

  • Refine by Keyword
  • 2 minimal automata
  • 1 Airy function
  • 1 Average-case analysis of algorithms
  • 1 Computational Complexity bounds
  • 1 Dyck paths
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2020
  • 1 2012
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023 Schloss Dagstuhl - LZI GmbH Imprint Privacy Contact