{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:18Z","timestamp":1740133938372,"version":"3.37.3"},"reference-count":32,"publisher":"World Scientific Pub Co Pte Ltd","issue":"05","funder":[{"DOI":"10.13039\/501100003725","name":"National Research Foundation of Korea","doi-asserted-by":"publisher","award":["NRF-2020R1A4A3079947"],"award-info":[{"award-number":["NRF-2020R1A4A3079947"]}],"id":[{"id":"10.13039\/501100003725","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:p> We study the NFA reductions by invariant equivalences and preorders. It is well-known that the NFA minimization problem is PSPACE-complete. Therefore, there have been many approaches to reduce the size of NFAs in low polynomial time by computing invariant equivalence or preorder relation and merging the states within same equivalence class. Here we consider the nondeterminism reduction of NFAs by invariant equivalences and preorders. We, in particular, show that computing equivalence and preorder relation from the left is more useful than the right for reducing the degree of nondeterminism in NFAs. We also present experimental evidence for showing that NFA reduction from the left achieves the better reduction of nondeterminism than reduction from the right. <\/jats:p>","DOI":"10.1142\/s0129054121410069","type":"journal-article","created":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T07:46:01Z","timestamp":1619423161000},"page":"531-550","source":"Crossref","is-referenced-by-count":0,"title":["Left is Better Than Right for Reducing Nondeterminism of NFAs"],"prefix":"10.1142","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5406-5104","authenticated-orcid":false,"given":"Sang-Ki","family":"Ko","sequence":"first","affiliation":[{"name":"Department of Computer Science and Engineering, Kangwon National University, 1 Gangwondaehak-gil, Chuncheon-Si, Gangwon-Do 24341, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7211-6657","authenticated-orcid":false,"given":"Yo-Sub","family":"Han","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50 Yonsei-Ro, Seodaemun-Gu, Seoul 03722, Republic of Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2021,4,23]]},"reference":[{"key":"S0129054121410069BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02979-0_10"},{"key":"S0129054121410069BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00182-4"},{"key":"S0129054121410069BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"S0129054121410069BIB004","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00296-X"},{"key":"S0129054121410069BIB005","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.02.048"},{"key":"S0129054121410069BIB006","volume-title":"Mastering Regular Expressions","author":"Friedl J. E. F.","year":"2002","edition":"2"},{"key":"S0129054121410069BIB007","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n05ABEH004112"},{"key":"S0129054121410069BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90053-K"},{"key":"S0129054121410069BIB009","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J.","year":"1979","edition":"2"},{"key":"S0129054121410069BIB010","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45022-X_17"},{"key":"S0129054121410069BIB011","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2001.3069"},{"key":"S0129054121410069BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27812-2_11"},{"key":"S0129054121410069BIB013","doi-asserted-by":"publisher","DOI":"10.1007\/11496656_27"},{"key":"S0129054121410069BIB014","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45687-2_27"},{"key":"S0129054121410069BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00090-7"},{"key":"S0129054121410069BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00311-6"},{"key":"S0129054121410069BIB017","doi-asserted-by":"publisher","DOI":"10.1137\/0222067"},{"key":"S0129054121410069BIB018","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-23247-4_16"},{"key":"S0129054121410069BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30500-2_2"},{"key":"S0129054121410069BIB020","doi-asserted-by":"publisher","DOI":"10.1007\/s002360050133"},{"key":"S0129054121410069BIB022","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003418"},{"key":"S0129054121410069BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90033-7"},{"key":"S0129054121410069BIB024","doi-asserted-by":"publisher","DOI":"10.1109\/TEC.1960.5221603"},{"key":"S0129054121410069BIB025","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44688-5_1"},{"key":"S0129054121410069BIB026","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316135228"},{"key":"S0129054121410069BIB027","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31623-4_20"},{"key":"S0129054121410069BIB028","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39310-5_21"},{"key":"S0129054121410069BIB029","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.07.006"},{"key":"S0129054121410069BIB030","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054117500137"},{"key":"S0129054121410069BIB031","doi-asserted-by":"publisher","DOI":"10.1137\/0218083"},{"key":"S0129054121410069BIB032","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"volume-title":"Theory of Computation","year":"1987","author":"Wood D.","key":"S0129054121410069BIB033"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054121410069","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,12]],"date-time":"2021-08-12T01:44:34Z","timestamp":1628732674000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054121410069"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,23]]},"references-count":32,"journal-issue":{"issue":"05","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["10.1142\/S0129054121410069"],"URL":"https:\/\/doi.org\/10.1142\/s0129054121410069","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2021,4,23]]}}}