{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T17:33:31Z","timestamp":1649093611614},"reference-count":33,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2012,9]]},"abstract":" Hyper-minimization of deterministic finite automata (DFA) is a recently introduced state reduction technique that allows a finite change in the recognized language. A generalization of this lossy compression method to the weighted setting over semifields is presented, which allows the recognized weighted language to differ for finitely many input strings. First, the structure of hyper-minimal deterministic weighted finite automata is characterized in a similar way as in classical weighted minimization and unweighted hyper-minimization. Second, an efficient hyper-minimization algorithm, which runs in time [Formula: see text], is derived from this characterization. Third, the closure properties of canonical regular languages, which are languages recognized by hyper-minimal DFA, are investigated. Finally, some recent results in the area of hyper-minimization are recalled. <\/jats:p>","DOI":"10.1142\/s0129054112400485","type":"journal-article","created":{"date-parts":[[2012,11,26]],"date-time":"2012-11-26T03:26:33Z","timestamp":1353900393000},"page":"1207-1225","source":"Crossref","is-referenced-by-count":1,"title":["UNWEIGHTED AND WEIGHTED HYPER-MINIMIZATION"],"prefix":"10.1142","volume":"23","author":[{"given":"ANDREAS","family":"MALETTI","sequence":"first","affiliation":[{"name":"Institute for Natural Language Processing, Universit\u00e4t Stuttgart, Pfaffenwaldring 5b, 70569 Stuttgart, Germany"}]},{"given":"DANIEL","family":"QUERNHEIM","sequence":"additional","affiliation":[{"name":"Institute for Natural Language Processing, Universit\u00e4t Stuttgart, Pfaffenwaldring 5b, 70569 Stuttgart, Germany"}]}],"member":"219","published-online":{"date-parts":[[2012,11,25]]},"reference":[{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1142\/S012905410900684X"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2007061"},{"key":"rf4","series-title":"CSLI Studies in Computational Linguistics","volume-title":"Finite State Morphology","author":"Beesley K. R.","year":"2003"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-73235-5"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102000960"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00292-9"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2005006"},{"key":"rf10","volume-title":"Jewels of Stringology","author":"Crochemore M.","year":"2003"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/0097-8493(93)90079-O"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809088"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791194094"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/14.1.79"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9333-5"},{"key":"rf19","first-page":"97","volume":"2","author":"Gries D.","journal-title":"Acta Inform."},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1967.10500922"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1142\/3903"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.029"},{"key":"rf24","doi-asserted-by":"crossref","unstructured":"J. E.\u00a0Hopcroft , Theory of Machines and Computations (Academic Press, 1971)\u00a0pp. 189\u2013196.","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"rf25","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"2007"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(67)90032-6"},{"key":"rf28","series-title":"Monographs on Linguistic Analysis","doi-asserted-by":"crossref","DOI":"10.1515\/9783110876000","volume-title":"Formal Aspects of Phonological Description","author":"Johnson C. D.","year":"1972"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289588"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002187"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69959-7"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.007"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04131-0"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054111009094"},{"key":"rf37","first-page":"269","volume":"23","author":"Mohri M.","journal-title":"Comput. Linguist."},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-01492-5_4"},{"key":"rf40","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1137\/0201010"},{"key":"rf43","doi-asserted-by":"crossref","unstructured":"P.\u00a0van Emde Boas , Algorithms and Complexity, Handbook of Theoretical Computer Science\u00a0A (Elsevier and MIT Press, 1990)\u00a0pp. 1\u201366.","DOI":"10.1016\/B978-0-444-88071-0.50006-0"},{"key":"rf44","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054112400485","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T12:02:49Z","timestamp":1565092969000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054112400485"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9]]},"references-count":33,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,11,25]]},"published-print":{"date-parts":[[2012,9]]}},"alternative-id":["10.1142\/S0129054112400485"],"URL":"https:\/\/doi.org\/10.1142\/s0129054112400485","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9]]}}}