Search Results

Documents authored by Sportiello, Andrea

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.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}
}
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-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact