{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T05:01:33Z","timestamp":1648962093383},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,12]]},"abstract":"<jats:p> Our aim is to enumerate all NFAs (nondeterministic finite automata) that recognize a given regular language [Formula: see text]. More precisely, we produce a set \ud835\udd38 of automata such that each automaton A recognizing [Formula: see text] appears in \ud835\udd38 up to the merging of some states and the addition of some transitions, that is, there is a surjective morphism that maps A onto an automaton of \ud835\udd38. We provide a common theoretical framework, based on morphism properties, to previous works of Kameda and Weiner (1970), and of Sengoku (1992), whose issue is the minimization of NFAs. Our paper gives two incomparable enumeration techniques. Both proceed by enumerating a specific class of grid covers of the automaton map. The first one is related to the canonical automaton introduced by Carrez. The second one is based on new outcomes related to the relationship between grid covers and their projections. <\/jats:p>","DOI":"10.1142\/s0129054105003790","type":"journal-article","created":{"date-parts":[[2005,12,2]],"date-time":"2005-12-02T11:54:25Z","timestamp":1133524465000},"page":"1253-1266","source":"Crossref","is-referenced-by-count":0,"title":["ENUMERATING NONDETERMINISTIC AUTOMATA FOR A GIVEN LANGUAGE WITHOUT CONSTRUCTING THE CANONICAL AUTOMATON"],"prefix":"10.1142","volume":"16","author":[{"given":"J.-M.","family":"CHAMPARNAUD","sequence":"first","affiliation":[{"name":"LIFAR,  University of Rouen, France"}]},{"given":"F.","family":"COULON","sequence":"additional","affiliation":[{"name":"LIFAR,  University of Rouen, France"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"166","volume":"47","author":"Arnold A.","journal-title":"Bulletin of the EATCS"},{"key":"rf2","unstructured":"J. A.\u00a0Brzozowski, Mathematical Theory of Automata, MRI Symposia Series\u00a012 (1962)\u00a0pp. 529\u2013561."},{"key":"rf4","first-page":"23","volume":"55","author":"Champarnaud J.-M.","journal-title":"Fundamenta Informaticae"},{"key":"rf5","first-page":"241","volume":"3","author":"Champarnaud J.-M.","journal-title":"Theoret. Comput. Sci."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090394"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1137\/0222067"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1970.222994"},{"key":"rf9","unstructured":"O.\u00a0Matz and A.\u00a0Potthoff, Tools and Algorithms for the Construction and Analysis of Systems \u2013 TACAS 95\u00a0NS-95-2 (1995)\u00a0pp. 74\u201388."},{"key":"rf11","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\/S0129054105003790","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:29:20Z","timestamp":1565191760000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003790"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,12]]},"references-count":9,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,12]]}},"alternative-id":["10.1142\/S0129054105003790"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003790","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,12]]}}}