On the Average Complexity of Moore's State Minimization Algorithm

Simple item page
dc.creatorBassino, Frédérique
dc.creatorDavid, Julien
dc.creatorNicaud, Cyril
dc.date2009-02-06
dc.date.accessioned2026-07-07T12:38:54Z
dc.date.available2026-07-07T12:38:54Z
dc.descriptionWe 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 O(n log n). Moreover this bound is tight in the case of unary utomata.
dc.identifierhttps://arxiv.org/abs/0902.1048
dc.identifierhttp://arxiv.org/abs/0902.1048
dc.identifier26th International Symposium on Theoretical Aspects of Computer Science STACS 2009 (2009) 123-134
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/218926
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleOn the Average Complexity of Moore's State Minimization Algorithm
dc.typetext

Files

Collections

arXiv