{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T21:58:49Z","timestamp":1648936729271},"reference-count":9,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2005,10]]},"abstract":"<jats:p> Iwama et al. showed that there exists an n-state binary nondeterministic finite automaton such that its equivalent minimal deterministic finite automaton has exactly 2<jats:sup>n<\/jats:sup> - \u03b1 states, for all n \u2265 7 and 5 \u2264 \u03b1 \u2264 2n-2, subject to certain coprimality conditions. We investigate the same question for both unary and binary symmetric difference nondeterministic finite automata. In the binary case, we show that for any n \u2265 4, there is an n-state symmetric difference nondeterministic finite automaton for which the equivalent minimal deterministic finite automaton has 2<jats:sup>n - 1<\/jats:sup> + 2<jats:sup>k - 1<\/jats:sup> - 1 states, for 2 &lt; k \u2264 n - 1. In the unary case, we consider a large practical subclass of unary symmetric difference nondeterministic finite automata: for all n \u2265 2, we argue that there are many values of \u03b1 such that there is no n-state unary symmetric difference nondeterministic finite automaton with an equivalent minimal deterministic finite automaton with 2<jats:sup>n<\/jats:sup> - \u03b1 states, where 0 &lt; \u03b1 &lt; 2<jats:sup>n - 1<\/jats:sup>. For each n \u2265 2, we quantify such values of \u03b1 precisely. <\/jats:p>","DOI":"10.1142\/s0129054105003455","type":"journal-article","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T11:41:41Z","timestamp":1129203701000},"page":"1027-1038","source":"Crossref","is-referenced-by-count":13,"title":["MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS"],"prefix":"10.1142","volume":"16","author":[{"given":"LYNETTE","family":"VAN ZIJL","sequence":"first","affiliation":[{"name":"Department of Computer Science,  Stellenbosch University, P\/Bag X1, 7602 Matieland, South Africa"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf2","volume-title":"Additive Cellular Automata Theory and Applications","volume":"1","author":"Chaudhuri P. P.","year":"1997"},{"key":"rf3","first-page":"469","volume":"7","author":"Domaratzki M.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf4","volume-title":"Applied Modern Algebra","author":"Dornhoff L. L.","year":"1977"},{"key":"rf5","volume-title":"Shift Register Sequences","author":"Golomb S. W.","year":"1967"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00029-3"},{"key":"rf7","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00891-5"},{"key":"rf11","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","year":"1997"},{"key":"rf12","volume-title":"Discrete Mathematical Structures","author":"Stone H.","year":"1973"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.012"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054105003455","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:41:32Z","timestamp":1565138492000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054105003455"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,10]]},"references-count":9,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2005,10]]}},"alternative-id":["10.1142\/S0129054105003455"],"URL":"https:\/\/doi.org\/10.1142\/s0129054105003455","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,10]]}}}