{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T08:06:56Z","timestamp":1649146016950},"reference-count":3,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2016,2]]},"abstract":"<jats:p>We analyze the average complexity of Brzozowski's minimization algorithm for distributions of deterministic automata with a small number of final states. We show that, as in the case of the uniform distribution, the average complexity is super-polynomial even if we consider random deterministic automata with only one final state. Such results were only known for distributions where the expected number of final states was linear in the number of states.<\/jats:p>","DOI":"10.1142\/s0129054116400025","type":"journal-article","created":{"date-parts":[[2016,5,4]],"date-time":"2016-05-04T08:25:46Z","timestamp":1462350346000},"page":"109-126","source":"Crossref","is-referenced-by-count":0,"title":["Average Case Analysis of Brzozowski's Algorithm"],"prefix":"10.1142","volume":"27","author":[{"given":"Sven De","family":"Felice","sequence":"first","affiliation":[{"name":"LIAFA, Universit\u00e9 Paris Diderot - Paris 7 &amp; CNRS UMR 7089, F-75205, Paris, France"}]},{"given":"Cyril","family":"Nicaud","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Est, LIGM (UMR 8049), UPEMLV, F-77454, Marne-la-Vall\u00e9e, France"}]}],"member":"219","published-online":{"date-parts":[[2016,5,4]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9557-7"},{"issue":"1","key":"p_5","doi-asserted-by":"crossref","DOI":"10.37236\/1558","volume":"8","author":"Chassaing P.","year":"2001","journal-title":"Electron. J. Combin."},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.10.011"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116400025","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,19]],"date-time":"2020-09-19T11:29:20Z","timestamp":1600514960000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116400025"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2]]},"references-count":3,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2016,5,4]]},"published-print":{"date-parts":[[2016,2]]}},"alternative-id":["10.1142\/S0129054116400025"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116400025","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2]]}}}