DROPS

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}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1822

On the Average Complexity of Moore's State Minimization Algorithm

Authors: Frederique Bassino, Julien David, and Cyril Nicaud

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

We prove that, for any arbitrary finite alphabet and for the uniform distribution over deterministic and accessible automata with $n$ states, the average complexity of Moore's state minimization algorithm is in $\mathcal{O}(n \log n)$. Moreover this bound is tight in the case of unary automata.

Cite as

Frederique Bassino, Julien David, and Cyril Nicaud. On the Average Complexity of Moore's State Minimization Algorithm. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 123-134, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{bassino_et_al:LIPIcs.STACS.2009.1822,
  author =	{Bassino, Frederique and David, Julien and Nicaud, Cyril},
  title =	{{On the Average Complexity of Moore's State Minimization Algorithm}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{123--134},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1822},
  URN =		{urn:nbn:de:0030-drops-18222},
  doi =		{10.4230/LIPIcs.STACS.2009.1822},
  annote =	{Keywords: Finite automata, State minimization, Moore’s algorithm, Average complexity}
}

Search Results

Documents authored by David, Julien

Asymptotic enumeration of Minimal Automata

Abstract

Cite as

On the Average Complexity of Moore's State Minimization Algorithm

Abstract

Cite as

Thanks for your feedback!

Could not send message