{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T09:10:39Z","timestamp":1774775439885,"version":"3.50.1"},"reference-count":23,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>Based on recent results from extremal graph theory, we prove that every n-state binary deterministic finite automaton can be converted into an equivalent regular expression of size O(1.742<jats:sup>n<\/jats:sup>) using state elimination. Furthermore, we give improved upper bounds on the language operations intersection and interleaving on regular expressions.<\/jats:p>","DOI":"10.1142\/s0129054113500330","type":"journal-article","created":{"date-parts":[[2014,4,2]],"date-time":"2014-04-02T06:43:49Z","timestamp":1396421029000},"page":"1255-1279","source":"Crossref","is-referenced-by-count":5,"title":["PROVABLY SHORTER REGULAR EXPRESSIONS FROM FINITE AUTOMATA"],"prefix":"10.1142","volume":"24","author":[{"given":"HERMANN","family":"GRUBER","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, D-35392, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARKUS","family":"HOLZER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, D-35392, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,4]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01788542"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480195282550"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/321239.321249"},{"key":"p_6","volume":"67","author":"Brzozowski Janusz A.","year":"1963","journal-title":"IEEE Transactions on Electronic Computers, EC12(2)"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.05.007"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1307\/mmj\/1028998975"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(76)80034-7"},{"issue":"4","key":"p_13","first-page":"407","volume":"10","author":"Ellul Keith","year":"2005","journal-title":"Languages and Combinatorics"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1137\/05064299X"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.04.036"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1145\/2071368.2071372"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.09.025"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0216-Q"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1137\/0136016"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(69)80016-2"},{"key":"p_28","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"issue":"3","key":"p_29","doi-asserted-by":"crossref","first-page":"611","DOI":"10.3233\/FI-2009-0061","volume":"91","author":"Moreira Nelma","year":"2009","journal-title":"Fundamenta Informaticae"},{"key":"p_30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.01.010"},{"key":"p_31","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113500330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,17]],"date-time":"2020-08-17T03:56:03Z","timestamp":1597636563000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113500330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":23,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2014,4]]},"published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1142\/S0129054113500330"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113500330","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]}}}