{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,11]],"date-time":"2025-07-11T10:14:32Z","timestamp":1752228872125},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540618638"},{"type":"electronic","value":"9783540707196"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61863-5_34","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:29:34Z","timestamp":1330295374000},"page":"59-66","source":"Crossref","is-referenced-by-count":8,"title":["Limits of exact algorithms for inference of minimum size finite state machines"],"prefix":"10.1007","author":[{"given":"Arlindo L.","family":"Oliveira","sequence":"first","affiliation":[]},{"given":"Stephen","family":"Edwards","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1978","unstructured":"D. Angluin. On the complexity of minimum inference of regular sets. Inform. Control, 39(3):337\u2013350, 1978.","journal-title":"Inform. Control"},{"issue":"2","key":"6_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"D. Angluin. Learning regular sets from queries and counterexamples. Inform. Comput., 75(2):87\u2013106, November 1987.","journal-title":"Inform. Comput."},{"key":"6_CR3","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1109\/TSE.1976.233812","volume":"SE-2","author":"A. W. Biermann","year":"1976","unstructured":"A. W. Biermann and R. Krishnaswamy. Constructing programs from example computations. IEEE Trans. on Software Engineering, SE-2:141\u2013153, 1976.","journal-title":"IEEE Trans. on Software Engineering"},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"122","DOI":"10.1109\/T-C.1975.224180","volume":"C-24","author":"A. W. B. R. I. Biermann","year":"1975","unstructured":"A. W. B. R. I. Biermann and F. E. Petry. Speeding up the synthesis of programs from traces. IEEE Trans. on Computers, C-24:122\u2013136, 1975.","journal-title":"IEEE Trans. on Computers"},{"key":"6_CR5","doi-asserted-by":"crossref","first-page":"677","DOI":"10.1109\/TC.1986.1676819","volume":"35","author":"R. E. Bryant","year":"1986","unstructured":"R. E. Bryant. Graph-based algorithms for Boolean function manipulation. IEEE Transactions on Computers, 35:677\u2013691, 1986.","journal-title":"IEEE Transactions on Computers"},{"key":"6_CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979."},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E. M. Gold","year":"1978","unstructured":"E. M. Gold. Complexity of automaton identification from given data. Inform. Control, 37:302\u2013320, 1978.","journal-title":"Inform. Control"},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"G. Hachtel, J.-K. Rho, F. Somenzi, and R. Jacoby. Exact and heuristic algorithms for the minimization of incompletely specified state machines. In The Proceedings of the European Design Automation Conference, 1991.","DOI":"10.1109\/EDAC.1991.206387"},{"key":"6_CR9","unstructured":"T. Kam and R.K. Brayton. Multi-valued decision diagrams. Tech. Report No. UCB\/ERL M90\/125, December 1990."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"T. Kam, T. Villa, R. K. Brayton, and A. Sangiovanni Vincentelli. A fully implicit algorithm for exact state minimization. Proc. Design Automat. Conf., 1994.","DOI":"10.1145\/196244.196615"},{"key":"6_CR11","unstructured":"Arlindo L. Oliveira and Stephen A. Edwards. Inference of state machines from examples of behavior. Technical report, UCB\/ERL Technical Report M95\/12, Berkeley, CA, 1995."},{"issue":"1","key":"6_CR12","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L. Pitt","year":"1993","unstructured":"L. Pitt and M. Warmuth. The minimum consistent DFA problem cannot be approximated within any polynomial. J. ACM, 40(1):95\u2013142, 1993.","journal-title":"J. ACM"},{"key":"6_CR13","doi-asserted-by":"crossref","first-page":"386","DOI":"10.21236\/ADA206851","volume-title":"Learning automata from ordered examples","author":"S. Porat","year":"1988","unstructured":"S. Porat and J. A. Feldman. Learning automata from ordered examples. In Proc. 1st Annu. Workshop on Comput. Learning Theory, pages 386\u2013396, San Mateo, CA, 1988. Morgan Kaufmann."},{"key":"6_CR14","volume-title":"The Design and Analysis of Efficient Learning Algorithms","author":"R. E. Schapire","year":"1992","unstructured":"R. E. Schapire. The Design and Analysis of Efficient Learning Algorithms. MIT Press, Cambridge, MA, 1992."}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61863-5_34.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:37:15Z","timestamp":1619573835000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61863-5_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540618638","9783540707196"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-61863-5_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}