{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:04:38Z","timestamp":1758272678695},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540404347"},{"type":"electronic","value":"9783540450078"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45007-6_15","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T14:34:37Z","timestamp":1188311677000},"page":"194-205","source":"Crossref","is-referenced-by-count":6,"title":["NFA Reduction Algorithms by Means of Regular Inequalities"],"prefix":"10.1007","author":[{"given":"Jean-Marc","family":"Champarnaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabien","family":"Coulon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,18]]},"reference":[{"key":"15_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45526-4_1","volume-title":"Automata Implementation, WIA\u201999","author":"J. Amilhastre","year":"2001","unstructured":"J. Amilhastre, P. Janssen, and M.C. Vilarem. FA minimization heuristics for a class of finite languages. In O. Boldt and H. J\u00fcrgensen, editors, Automata Implementation, WIA\u201999, Lecture Notes in Computer Science, volume 2214, pages 1\u201312. Springer, 2001."},{"key":"15_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1007\/3-540-60249-6_44","volume-title":"Rewriting regular inequalities","author":"V. Antimirov","year":"1995","unstructured":"V. Antimirov. Rewriting regular inequalities. Lecture notes in computer science, 965:116\u2013125, 1995."},{"key":"15_CR3","first-page":"529","volume":"12","author":"J.A. Brzozowski","year":"1962","unstructured":"J.A. Brzozowski. Canonical regular expressions and minimal state graphs for definite events. Mathematical Theory of Automata, MRI Symposia Series, 12:529\u2013561, 1962.","journal-title":"Mathematical Theory of Automata, MRI Symposia Series"},{"key":"15_CR4","unstructured":"J.-M. Champarnaud and F. Coulon. Theoretical study and implementation of the canonical automaton. Technical Report AIA 2003.03, LIFAR, Universit\u00e9 de Rouen, 2003."},{"key":"15_CR5","unstructured":"J.-M. Champarnaud, F. Coulon, and T. Parantho\u00ebn. Compact and fast algorithms for regular expression search. Technical Report AIA 2003.01, LIFAR, Universit\u00e9 de Rouen, 2003."},{"key":"15_CR6","doi-asserted-by":"crossref","first-page":"48","DOI":"10.3115\/1611533.1611538","volume-title":"FSMNLP\u201998","author":"J. Daciuk","year":"1998","unstructured":"J. Daciuk, B.-W. Watson, and R.-E. Watson. Incremental construction of minimal acyclic finite state automata and transducers. In L. Karttunen, editor, FSMNLP\u201998, pages 48\u201355. Association for Computational Linguistics, Somerset, New Jersey, 1998."},{"key":"15_CR7","doi-asserted-by":"crossref","unstructured":"John E. Hopcroft. An n log n algorithm for minimizing the states in a finite automaton. In Z. Kohavi, editor, The Theory of Machines and Computations, pages 189\u2013196. Academic Press, 1971.","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"15_CR8","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/S0022-0000(76)80038-4","volume":"12","author":"H. Hunt","year":"1976","unstructured":"H. Hunt, D. Rosenkrantz, and T. Szymanski. On the equivalence, containment and covering problems for the regular and context-free languages. J. Comput. System Sci., 12:222\u2013268, 1976.","journal-title":"J. Comput. System Sci."},{"key":"15_CR9","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1007\/3-540-45687-2_27","volume-title":"Algorithms for computing small NFAs","author":"L. Ilie","year":"2002","unstructured":"L. Ilie and S. Yu. Algorithms for computing small NFAs. In K. Diks and W. Rytter, editors, Lecture Notes in Computer Science, volume 2420, pages 328\u2013340. Springer, 2002."},{"key":"15_CR10","unstructured":"J. Jaja. An introduction to parallel algorithms. Addison-Wesley, 1992."},{"issue":"6","key":"15_CR11","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"T. Jiang and B. Ravikumar. Minimal NFA problems are hard. SIAM J. Comput. Vol 22, No 6, pages 1117\u20131141, 1993.","journal-title":"SIAM J. Comput."},{"issue":"19","key":"15_CR12","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1109\/T-C.1970.222994","volume":"C","author":"T. Kameda","year":"1970","unstructured":"T. Kameda and P. Weiner. On the state minimization of nondeterministic finite automata. IEEE Trans. Comp., C(19):617\u2013627, 1970.","journal-title":"IEEE Trans. Comp."},{"key":"15_CR13","unstructured":"H. Sengoku. Minimization of nondeterministic finite automata. Master\u2019s thesis, Kyoto University, 1992."},{"key":"15_CR14","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/135239.135244","volume":"31","author":"S. Wu","year":"1992","unstructured":"S. Wu and U. Manber. Fast text searching algorithm allowing errors. In Communication of the ACM, 31, pages 83\u201391, October 1992.","journal-title":"Communication of the ACM"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45007-6_15","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T17:09:06Z","timestamp":1556816946000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45007-6_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540404347","9783540450078"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-45007-6_15","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2003]]}}}