{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:13:03Z","timestamp":1725549183699},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540243182"},{"type":"electronic","value":"9783540305002"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/978-3-540-30500-2_18","type":"book-chapter","created":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T16:39:36Z","timestamp":1267461576000},"page":"190-201","source":"Crossref","is-referenced-by-count":3,"title":["Minimal Unambiguous \u03b5NFA"],"prefix":"10.1007","author":[{"given":"Sebastian","family":"John","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"18_CR1","volume-title":"The Design and Anlalysis of Computer Algorithms","author":"A.V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E., Ullman, J.D.: The Design and Anlalysis of Computer Algorithms. Addison-Wesley, Reading (1974)"},{"key":"18_CR2","first-page":"166","volume":"47","author":"A. Arnold","year":"1992","unstructured":"Arnold, A., Dicky, A., Nivat, M.: A note about minimal non-deterministic automata. Bulletin of the European Association for Theoretical Computer Science\u00a047, 166\u2013169 (1992)","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"Brauer, W.: Automatentheorie. Teuber, Stuttgart (1984)","DOI":"10.1007\/978-3-322-92151-2"},{"key":"18_CR4","first-page":"113","volume":"35","author":"W. Brauer","year":"1988","unstructured":"Brauer, W.: On minimizing finite automata. Bulletin of the European Assciation for Theoretical Computer Science (EATCS)\u00a035, 113\u2013116 (1988)","journal-title":"Bulletin of the European Assciation for Theoretical Computer Science (EATCS)"},{"key":"18_CR5","first-page":"529","volume-title":"Mathematical Theory of Automata","author":"J.A. Brzozowski","year":"1962","unstructured":"Brzozowski, J.A.: Canonical regular expressions and minimal state graphs for definite events. In: Mathematical Theory of Automata, pp. 529\u2013561. Polytechnic Press, Polytechnic Institute of Brooklyn (1962)"},{"key":"18_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman and Co., New York (1979)"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-44977-9_14","volume-title":"Implementation and Application of Automata","author":"M. Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol.\u00a02608, pp. 148\u2013157. Springer, Heidelberg (2003)"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Hopcroft, J.E.: An n log n algorithm for minimizing states in a finite automaton. In: Proc. International Symposium on Theory of Machines and Computations, Technion, Haifa (IL), pp. 189\u2013196 (1971)","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"18_CR9","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J.E. Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading (1979)"},{"issue":"3-4","key":"18_CR10","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1016\/0016-0032(54)90618-3","volume":"257","author":"D.A. Huffman","year":"1954","unstructured":"Huffman, D.A.: The synthesis of sequential switching circuits. Journal of the Franklin Institute\u00a0257(3-4), 161\u2013190, 275\u2013303 (1954)","journal-title":"Journal of the Franklin Institute"},{"key":"18_CR11","unstructured":"John, S.: Minimal unambiguous eNFA. Technical report, TR-2003-22, Technical University Berlin"},{"key":"18_CR12","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"},{"key":"18_CR13","unstructured":"Kim, J.: State minimization of nondeterministic machines. Technical report, RC 4896, IBM Thomas J. Watson Research Center (1974)"},{"key":"18_CR14","unstructured":"Matz, O., Potthoff, A.: Computing small nondeterministic finite automata. In: Proc. Workshop on Tools and Algorithms for the Construction and Analysis of Systems, pp. 74\u201388 (1995)"},{"key":"18_CR15","doi-asserted-by":"crossref","first-page":"1045","DOI":"10.1002\/j.1538-7305.1955.tb03788.x","volume":"34","author":"G.H. Mealy","year":"1955","unstructured":"Mealy, G.H.: Method for synthesizing sequential circuits. Bell System Technical Journal\u00a034, 1045\u20131079 (1955)","journal-title":"Bell System Technical Journal"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Proc. 12th Annual Symposium on Switching and Automata Theory, pp. 188\u2013191 (1971)","DOI":"10.1109\/SWAT.1971.11"},{"key":"18_CR17","first-page":"129","volume":"34","author":"E.F. Moore","year":"1956","unstructured":"Moore, E.F.: Gedanken-experiments on sequential machines. Automata Studies, Annals of Mathematics Series\u00a034, 129\u2013153 (1956)","journal-title":"Automata Studies, Annals of Mathematics Series"},{"key":"18_CR18","unstructured":"Myhill, J.: Finite automata and the representation of events. Technical report, WADC TR-57-624, Wright Patterson Air Force Base, Ohio, USA (1957)"},{"key":"18_CR19","doi-asserted-by":"crossref","first-page":"514","DOI":"10.1090\/S0002-9939-1958-0135681-9","volume":"9","author":"A. Nerode","year":"1958","unstructured":"Nerode, A.: Linear automaton transformations. Proc. American Mathematical Society\u00a09, 514\u2013544 (1958)","journal-title":"Proc. American Mathematical Society"},{"key":"18_CR20","first-page":"351","volume":"3","author":"S. Neuber","year":"1967","unstructured":"Neuber, S., Starke, P.H.: \u00dcber Homomorphie und Reduktion bei nicht-deterministischen Automaten. EIK: Elektronische Informationsverarbeitung und Kybernetik\u00a03, 351\u2013362 (1967)","journal-title":"EIK: Elektronische Informationsverarbeitung und Kybernetik"},{"key":"18_CR21","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"M.O. Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.S.: Finite automata and their decision problems. IBM Journal of Research and Development\u00a03, 114\u2013125 (1959)","journal-title":"IBM Journal of Research and Development"},{"issue":"6","key":"18_CR22","doi-asserted-by":"publisher","first-page":"1263","DOI":"10.1137\/0218083","volume":"18","author":"B. Ravikumar","year":"1989","unstructured":"Ravikumar, B., Ibarra, O.H.: Relating the type of ambiguity of finite automata to the succinctness of their representation. SIAM Journal on Computing\u00a018(6), 1263\u20131282 (1989)","journal-title":"SIAM Journal on Computing"},{"key":"18_CR23","doi-asserted-by":"crossref","unstructured":"Schmidt, E.M.: Succinctness of descriptions of context-free, regular, and finite languages. Technical Report DAIMI PB-84, Department of Computer Science, University of Aarhus, Denmark (1978)","DOI":"10.7146\/dpb.v7i84.6500"},{"key":"18_CR24","series-title":"Languages and Parsing. EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61345-6","volume-title":"Parsing Theory","author":"S. Sippu","year":"1988","unstructured":"Sippu, S., Soisalon-Soininen, E.: Parsing Theory. Languages and Parsing. EATCS Monographs on Theoretical Computer Science, vol.\u00a0I. Springer, Heidelberg (1988)"},{"key":"18_CR25","first-page":"61","volume":"2","author":"P.H. Starke","year":"1966","unstructured":"Starke, P.H.: Einige Bemerkungen \u00fcber nicht-deterministische Automaten. EIK: Elektronische Informationsverarbeitung und Kybernetik\u00a02, 61\u201382 (1966)","journal-title":"EIK: Elektronische Informationsverarbeitung und Kybernetik"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Stearns, R.E., Hunt III, H.B.: On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata. In: IEEE: 22nd Annual Symposium on Foundations of Computer Science, pp. 74\u201381 (1981)","DOI":"10.1109\/SFCS.1981.29"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30500-2_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:57:10Z","timestamp":1605761830000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30500-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540243182","9783540305002"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30500-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}