{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T02:26:17Z","timestamp":1747189577261,"version":"3.40.5"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Ltd","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2025,4]]},"abstract":"<jats:p> We examine the costs of the conversions between six automata models: deterministic finite automata, partial deterministic finite automata, nondeterministic finite automata with a unique final state and multiple final states, respectively, alternating finite automata, and Boolean finite automata. We present a tight upper bound for each conversion. All witnesses are described over a unary or binary alphabet, and we show that whenever a binary alphabet is used, it is always optimal. <\/jats:p>","DOI":"10.1142\/s0129054124430020","type":"journal-article","created":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T08:26:46Z","timestamp":1722587206000},"page":"321-344","source":"Crossref","is-referenced-by-count":0,"title":["Conversions Between Six Models of Finite Automata"],"prefix":"10.1142","volume":"36","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1752-544X","authenticated-orcid":false,"given":"Michal","family":"Hospod\u00e1r","sequence":"first","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9817-8197","authenticated-orcid":false,"given":"Galina","family":"Jir\u00e1skov\u00e1","sequence":"additional","affiliation":[{"name":"Mathematical Institute, Slovak Academy of Sciences, Gre\u0161\u00e1kova 6, 040 01 Ko\u0161ice, Slovakia"}]}],"member":"219","published-online":{"date-parts":[[2024,8,2]]},"reference":[{"key":"S0129054124430020BIB001","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90198-5"},{"key":"S0129054124430020BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90069-9"},{"key":"S0129054124430020BIB003","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322243"},{"key":"S0129054124430020BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90142-8"},{"issue":"4","key":"S0129054124430020BIB005","first-page":"45","volume":"1","author":"Ershov Yu. L.","year":"1962","journal-title":"Algebra i logika"},{"key":"S0129054124430020BIB006","doi-asserted-by":"publisher","DOI":"10.1080\/00207169008803893"},{"key":"S0129054124430020BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.07.001"},{"key":"S0129054124430020BIB008","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002199"},{"volume-title":"Introduction to Automata Theory, Languages and Computation","year":"1979","author":"Hopcroft J. E.","key":"S0129054124430020BIB009"},{"key":"S0129054124430020BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2021.02.002"},{"key":"S0129054124430020BIB011","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-98355-4_2"},{"key":"S0129054124430020BIB012","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054119400069"},{"key":"S0129054124430020BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.04.011"},{"key":"S0129054124430020BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30642-6_19"},{"key":"S0129054124430020BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23247-4_14"},{"key":"S0129054124430020BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.05.008"},{"key":"S0129054124430020BIB017","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1976.20"},{"key":"S0129054124430020BIB018","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(81)80005-9"},{"key":"S0129054124430020BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48340-3_21"},{"key":"S0129054124430020BIB020","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"volume-title":"Introduction to the Theory of Computation","year":"2012","author":"Sipser M.","key":"S0129054124430020BIB021"},{"key":"S0129054124430020BIB022","doi-asserted-by":"publisher","DOI":"10.4064\/aa-37-1-321-331"},{"key":"S0129054124430020BIB023","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\/S0129054124430020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T03:17:38Z","timestamp":1745551058000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054124430020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,2]]},"references-count":23,"journal-issue":{"issue":"03","published-print":{"date-parts":[[2025,4]]}},"alternative-id":["10.1142\/S0129054124430020"],"URL":"https:\/\/doi.org\/10.1142\/s0129054124430020","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2024,8,2]]}}}