文章基本信息

标题：On the Average Complexity of Moore's State Minimization Algorithm
本地全文：下载
作者：Frederique Bassino ; Julien David ; Cyril Nicaud 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2009
卷号：3
页码：123-134
DOI：10.4230/LIPIcs.STACS.2009.1822
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Finite automata; State minimization; Moore's algorithm; Average complexity