{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,3]],"date-time":"2024-09-03T02:49:58Z","timestamp":1725331798721},"reference-count":20,"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 compare deterministic finite automata (DFAs) and biautomata under the following two aspects: structural similarities between minimal and hyper-minimal automata, and computational complexity of the minimization and hyper-minimization problem. Concerning classical minimality, the known results such as isomorphism between minimal DFAs, and NL-completeness of the DFA minimization problem carry over to the biautomaton case. But surprisingly this is not the case for hyper-minimization: the similarity between almost-equivalent hyper-minimal biautomata is not as strong as it is between almost-equivalent hyper-minimal DFAs. Moreover, while hyper-minimization is NL-complete for DFAs, we prove that this problem turns out to be computationally intractable, i.e., NP-complete, for biautomata. <\/jats:p>","DOI":"10.1142\/s0129054116400050","type":"journal-article","created":{"date-parts":[[2016,5,4]],"date-time":"2016-05-04T08:25:46Z","timestamp":1462350346000},"page":"161-185","source":"Crossref","is-referenced-by-count":1,"title":["Minimal and Hyper-Minimal Biautomata"],"prefix":"10.1142","volume":"27","author":[{"given":"Markus","family":"Holzer","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen Arndtstr. 2, 35392 Giessen, Germany"}]},{"given":"Sebastian","family":"Jakobi","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen Arndtstr. 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2016,5,4]]},"reference":[{"key":"p_1","first-page":"166","volume":"47","author":"Arnold A.","year":"1992","journal-title":"Bull. EATCS"},{"issue":"1","key":"p_2","first-page":"69","volume":"43","author":"Badr A.","journal-title":"Applications"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90002-W"},{"key":"p_5","first-page":"356","volume":"201","author":"Gawrychowski P.","journal-title":"Slovakia"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054113400327"},{"key":"p_7","first-page":"179","volume":"201","author":"Holzer M.","journal-title":"Sweden"},{"key":"p_8","first-page":"112","volume":"201","author":"Holzer M.","journal-title":"Canada"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.11.013"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.029"},{"key":"p_11","first-page":"189","volume":"197","author":"Hopcroft J.","journal-title":"New York"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"p_14","first-page":"629","volume":"199","author":"Jiang T.","journal-title":"Springer"},{"key":"p_15","first-page":"196","volume":"201","author":"Jir\u00e1skov\u00e1 G.","journal-title":"Portugal"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80050-X"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1007\/BF01683259"},{"key":"p_18","first-page":"344","volume":"201","author":"Kl\u00edma O.","journal-title":"Taiwan"},{"issue":"4","key":"p_19","first-page":"573","volume":"46","author":"Kl\u00edma O.","journal-title":"Applications"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80063-7"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054116400050","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:02:42Z","timestamp":1565118162000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054116400050"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2]]},"references-count":20,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2016,5,4]]},"published-print":{"date-parts":[[2016,2]]}},"alternative-id":["10.1142\/S0129054116400050"],"URL":"https:\/\/doi.org\/10.1142\/s0129054116400050","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2]]}}}