{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,7]],"date-time":"2025-06-07T17:41:25Z","timestamp":1749318085849},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642146831"},{"type":"electronic","value":"9783642146848"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14684-8_9","type":"book-chapter","created":{"date-parts":[[2010,7,24]],"date-time":"2010-07-24T11:52:18Z","timestamp":1279972338000},"page":"81-92","source":"Crossref","is-referenced-by-count":5,"title":["Reducing Nondeterministic Finite Automata with SAT Solvers"],"prefix":"10.1007","author":[{"given":"Jaco","family":"Geldenhuys","sequence":"first","affiliation":[]},{"given":"Brink","family":"van der Merwe","sequence":"additional","affiliation":[]},{"given":"Lynette","family":"van Zijl","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/3-540-45526-4_1","volume-title":"Automata Implementation","author":"J. Amilhastre","year":"1999","unstructured":"Amilhastre, J., Janssen, P., Vilarem, M.C.: FA minimization heuristics for a class of finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol.\u00a02214, pp. 1\u201312. Springer, Heidelberg (1999)"},{"unstructured":"Carrez, C.: On the minimalization of nondeterministic automata. Technical report, Laboratoire de Calcul de Facult\u00e9 des Sciences de l\u2019Universit\u00e9 de Lille (1970)","key":"9_CR2"},{"issue":"3","key":"9_CR3","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.tcs.2004.02.048","volume":"327","author":"J.-M. Champarnaud","year":"2004","unstructured":"Champarnaud, J.-M., Coulon, F.: Nfa reduction algorithms by means of regular inequalities. Theoretical Computer Science\u00a0327(3), 241\u2013253 (2004)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"9_CR4","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1162\/089120100561601","volume":"26","author":"J. Daciuk","year":"2000","unstructured":"Daciuk, J., Mihov, S., Watson, B.W., Watson, R.E.: Incremental construction of minimal acyclic finite-state automata. Comp. Linguistics\u00a026(1), 3\u201316 (2000)","journal-title":"Comp. Linguistics"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/978-3-540-27812-2_11","volume-title":"Theory Is Forever","author":"L. Ilie","year":"2004","unstructured":"Ilie, L., Navarro, G., Yu, S.: On NFA reductions. In: Karhum\u00e4ki, J., Maurer, H., P\u0103un, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol.\u00a03113, pp. 112\u2013124. Springer, Heidelberg (2004)"},{"key":"9_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1007\/3-540-45687-2_27","volume-title":"Mathematical Foundations of Computer Science 2002","author":"L. Ilie","year":"2002","unstructured":"Ilie, L., Yu, S.: Algorithms for computing small NFAs. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol.\u00a02420, pp. 328\u2013340. Springer, Heidelberg (2002)"},{"unstructured":"Indermark, K.: Zur Zustandsminimisierung nichdeterministischer erkennender Automaten. GMD Seminarberichte Bd.\u00a033, Gesellschaft f\u00fcr Mathematik und Datenverarbeitung (1970)","key":"9_CR7"},{"key":"9_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1007\/3-540-54233-7_169","volume-title":"Automata, Languages and Programming","author":"T. Jiang","year":"1991","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. In: Leach Albert, J., Monien, B., Rodr\u00edguez-Artalejo, M. (eds.) ICALP 1991. LNCS, vol.\u00a0510, pp. 629\u2013640. Springer, Heidelberg (1991)"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1109\/T-C.1970.222994","volume":"C-19","author":"T. Kameda","year":"1970","unstructured":"Kameda, T., Weiner, P.: On the state minimization of nondeterministic finite automata. IEEE Transactions on Computers\u00a0C-19, 617\u2013627 (1970)","journal-title":"IEEE Transactions on Computers"},{"unstructured":"Kim, J.H.: State minimization of nondeterministic machines. Technical Report RC 4896, IBM Thomas J.\u00a0Watson Research Center (1974)","key":"9_CR10"},{"issue":"3","key":"9_CR11","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1016\/j.tcs.2004.03.070","volume":"327","author":"A. Malcher","year":"2004","unstructured":"Malcher, A.: Minimizing finite automata is computationally hard. Theoretical Computer Science\u00a0327(3), 375\u2013390 (2004)","journal-title":"Theoretical Computer Science"},{"unstructured":"Matz, O., Miller, A., Potthoff, A., Thomas, W., Valkema, E.: Report on the program AMoRE. Technical Report 9507, Christian-Albrechts-Unversit\u00e4t, Kiel (Oct. 1995)","key":"9_CR12"},{"issue":"2","key":"9_CR13","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/BF03014374","volume":"6","author":"B.F. Melnikov","year":"1999","unstructured":"Melnikov, B.F.: A new algorithm of the state-minimization for the nondeterministic finite automata. Korean Jnl. of Comp. and Appl. Mathematics\u00a06(2), 277\u2013290 (1999)","journal-title":"Korean Jnl. of Comp. and Appl. Mathematics"},{"unstructured":"Mihov, S.: Direct building of minimal automaton for given list. Annuaire de l\u2019Universite de Sofia \u201cSt. Kl. Ohridski\u201d (1998)","key":"9_CR14"},{"issue":"2","key":"9_CR15","first-page":"269","volume":"23","author":"M. Mohri","year":"1997","unstructured":"Mohri, M.: Finite-state transducers in language and speech processing. Comp. Linguistics\u00a023(2), 269\u2013311 (1997)","journal-title":"Comp. Linguistics"},{"unstructured":"M\u00fcller, G.: Minimization of symmetric difference finite automata. Master\u2019s thesis, Stellenbosch University (April 2006)","key":"9_CR16"},{"issue":"5","key":"9_CR17","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1142\/S0129054105003431","volume":"16","author":"L. Pol\u00e1k","year":"2005","unstructured":"Pol\u00e1k, L.: Minimalizations of NFA using the universal automaton. International Jnl. of Foundations of Computer Science\u00a016(5), 999\u20131010 (2005)","journal-title":"International Jnl. of Foundations of Computer Science"},{"key":"9_CR18","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1002\/9780470053928.ch5","volume-title":"Parallel Combinatorial Optimization, ch. 5","author":"D. Singer","year":"2006","unstructured":"Singer, D.: Parallel resolution of the satisfiability problem: A survey. In: Talbi, E.-G. (ed.) Parallel Combinatorial Optimization, ch. 5, pp. 123\u2013148. John Wiley and Sons, Chichester (2006)"},{"key":"9_CR19","first-page":"69","volume":"34","author":"L. Zijl van","year":"2005","unstructured":"van Zijl, L., Daciuk, J., M\u00fcller, G.: Minimization of unary symmetric difference NFAs. South African Computer Jnl.\u00a034, 69\u201375 (2005)","journal-title":"South African Computer Jnl."},{"unstructured":"http:\/\/www.princeton.edu\/~chaff\/zchaff.html","key":"9_CR20"}],"container-title":["Lecture Notes in Computer Science","Finite-State Methods and Natural Language Processing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14684-8_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T13:30:10Z","timestamp":1591536610000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14684-8_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642146831","9783642146848"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14684-8_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}