{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:10:38Z","timestamp":1725491438452},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540732075"},{"type":"electronic","value":"9783540732082"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-73208-2_38","type":"book-chapter","created":{"date-parts":[[2007,9,12]],"date-time":"2007-09-12T07:58:11Z","timestamp":1189583891000},"page":"411-421","source":"Crossref","is-referenced-by-count":2,"title":["On Transition Minimality of Bideterministic Automata"],"prefix":"10.1007","author":[{"given":"Hellis","family":"Tamm","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"38_CR1","first-page":"471","volume":"64","author":"S. Yu","year":"2005","unstructured":"Yu, S.: State complexity: recent results and open problems. Fundamenta Informaticae\u00a064, 471\u2013480 (2005)","journal-title":"Fundamenta Informaticae"},{"key":"38_CR2","first-page":"519","volume":"7","author":"J. Hromkovic","year":"2002","unstructured":"Hromkovic, J.: Descriptional complexity of finite automata: concepts and open problems. Journal of Automata, Languages and Combinatorics\u00a07, 519\u2013531 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"38_CR3","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"C-20","author":"F. Moore","year":"1971","unstructured":"Moore, F.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput.\u00a0C-20, 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"38_CR4","doi-asserted-by":"publisher","first-page":"1117","DOI":"10.1137\/0222067","volume":"22","author":"T. Jiang","year":"1993","unstructured":"Jiang, T., Ravikumar, B.: Minimal NFA problems are hard. SIAM J. Comput.\u00a022, 1117\u20131141 (1993)","journal-title":"SIAM J. Comput."},{"key":"38_CR5","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2004.07.010","volume":"328","author":"H. Tamm","year":"2004","unstructured":"Tamm, H., Ukkonen, E.: Bideterministic automata and minimal representations of regular languages. Theoretical Computer Science\u00a0328, 135\u2013149 (2004)","journal-title":"Theoretical Computer Science"},{"key":"38_CR6","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/322326.322334","volume":"3","author":"D. Angluin","year":"1982","unstructured":"Angluin, D.: Inference of reversible languages. Journal of the Association for Computing Machinery\u00a03, 741\u2013765 (1982)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"38_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/BFb0023844","volume-title":"LATIN \u201992","author":"J.E. Pin","year":"1992","unstructured":"Pin, J.E.: On reversible automata. In: Simon, I. (ed.) LATIN 1992. LNCS, vol.\u00a0583, pp. 401\u2013416. Springer, Heidelberg (1992)"},{"key":"38_CR8","unstructured":"Latteux, M., Roos, Y., Terlutte, A.: BiRFSA languages and minimal NFAs. Technical Report GRAPPA-0205, GRAPPA (2005)"},{"key":"38_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11821069_28","volume-title":"Mathematical Foundations of Computer Science 2006","author":"M. Domaratzki","year":"2006","unstructured":"Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol.\u00a04162, pp. 315\u2013326. Springer, Heidelberg (2006)"},{"key":"38_CR10","unstructured":"Gruber, H., Holzer, M.: Results on the average state and transition complexity of finite automata accepting finite languages. In: Proceedings of DCFS, Computer Science Technical Report, NMSU-CS-2006-001, New Mexico State University, pp. 267\u2013275 (2006)"},{"key":"38_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/11523468_32","volume-title":"Automata, Languages and Programming","author":"J. Hromkovic","year":"2005","unstructured":"Hromkovic, J., Schnitger, G.: NFAs with and without \u03b5-transitions. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol.\u00a03580, pp. 385\u2013396. Springer, Heidelberg (2005)"},{"key":"38_CR12","first-page":"166","volume":"47","author":"A. Arnold","year":"1992","unstructured":"Arnold, A., Dicky, A., Nivat, M.: A note about minimal non-deterministic automata. Bull. EATCS\u00a047, 166\u2013169 (1992)","journal-title":"Bull. EATCS"},{"key":"38_CR13","unstructured":"Sakarovitch, J.: Elements of Automata Theory (to appear)"},{"key":"38_CR14","unstructured":"John, S.: Minimal unambiguous \u03b5-NFA. Technical Report TR-2003-22, Technical University Berlin (2003)"},{"key":"38_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/978-3-540-30500-2_18","volume-title":"Implementation and Application of Automata","author":"S. John","year":"2005","unstructured":"John, S.: Minimal unambiguous \u03b5-NFA. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol.\u00a03317, pp. 190\u2013201. Springer, Heidelberg (2005)"},{"key":"38_CR16","doi-asserted-by":"publisher","first-page":"1775","DOI":"10.1016\/S0304-3975(02)00083-X","volume":"290","author":"P. Shankar","year":"2003","unstructured":"Shankar, P., Dasgupta, A., Deshmukh, K., Rajan, B.S.: On viewing block codes as finite automata. Theoretical Computer Science\u00a0290, 1775\u20131797 (2003)","journal-title":"Theoretical Computer Science"},{"key":"38_CR17","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0019-9958(67)90481-0","volume":"11","author":"R. McNaughton","year":"1967","unstructured":"McNaughton, R.: The loop complexity of pure-group events. Information and Control\u00a011, 167\u2013176 (1967)","journal-title":"Information and Control"},{"key":"38_CR18","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/S0022-0000(70)80025-3","volume":"4","author":"R.S. Cohen","year":"1970","unstructured":"Cohen, R.S.: Star height of certain families of regular events. J. Comput. Syst. Sci.\u00a04, 281\u2013297 (1970)","journal-title":"J. Comput. Syst. Sci."},{"key":"38_CR19","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)"},{"key":"38_CR20","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 automata. IEEE Trans. Comput.\u00a0C-19, 617\u2013627 (1970)","journal-title":"IEEE Trans. Comput."},{"key":"38_CR21","unstructured":"Tamm, H.: On minimality and size reduction of one-tape and multitape finite automata. PhD thesis, Department of Computer Science, University of Helsinki, Finland (2004)"},{"key":"38_CR22","doi-asserted-by":"publisher","first-page":"999","DOI":"10.1142\/S0129054105003431","volume":"16","author":"L. Polak","year":"2005","unstructured":"Polak, L.: Minimalizations of NFA using the universal automaton. International Journal of Foundations of Computer Science\u00a016, 999\u20131010 (2005)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"38_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1007\/3-540-45465-9_16","volume-title":"Automata, Languages and Programming","author":"S. Lombardy","year":"2002","unstructured":"Lombardy, S.: On the construction of reversible automata for reversible languages. In: Widmayer, P., Triguero, F., Morales, R., Hennessy, M., Eidenbenz, S., Conejo, R. (eds.) ICALP 2002. LNCS, vol.\u00a02380, pp. 170\u2013182. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73208-2_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T01:34:39Z","timestamp":1558488879000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73208-2_38"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540732075","9783540732082"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73208-2_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}