{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:42Z","timestamp":1725664722100},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_125","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:57Z","timestamp":1330292217000},"page":"112-123","source":"Crossref","is-referenced-by-count":2,"title":["On the hardness of approximating the minimum consistent OBDD problem"],"prefix":"10.1007","author":[{"given":"Kouichi","family":"Hirata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shinichi","family":"Shimozono","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"11_CR1","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0019-9958(78)90683-6","volume":"39","author":"D. Angluin","year":"1978","unstructured":"Angluin, D.: On the complexity of minimum inference of regular sets, Information and Control 39, 337\u2013350, 1978.","journal-title":"Information and Control"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D.: Learning regular sets from queries and counterexamples, Information and Computation 75, 87\u2013106, 1987.","journal-title":"Information and Computation"},{"key":"11_CR3","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D.: Queries and concept learning, Machine Learning 2, 319\u2013342, 1988.","journal-title":"Machine Learning"},{"key":"11_CR4","first-page":"121","volume":"5","author":"D. Angluin","year":"1990","unstructured":"Angluin, D.: Negative results for equivalence queries, Machine Learning 5, 121\u2013150, 1990.","journal-title":"Machine Learning"},{"key":"11_CR5","doi-asserted-by":"crossref","first-page":"470","DOI":"10.1145\/176584.176586","volume":"41","author":"A. Blum","year":"1994","unstructured":"Blum, A.: New approximation algorithms for graph coloring, Journal of the Association for Computing Machinery 41, 470\u2013516, 1994.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"11_CR6","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1016\/0304-3975(92)90367-O","volume":"100","author":"R. Board","year":"1992","unstructured":"Board, R. and Pitt, L.: On the necessity of Occam algorithms, Theoretical Computer Science 100, 157\u2013184, 1992.","journal-title":"Theoretical Computer Science"},{"unstructured":"Bolling, B. and Wegener, I.: Improving the variable ordering of OBDDs is NP-complete, Technical Report, Universit\u00e4t Dortmund, 1994.","key":"11_CR7"},{"key":"11_CR8","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1145\/136035.136043","volume":"24","author":"R. E. Bryant","year":"1992","unstructured":"Bryant, R. E.: Symbolic Boolean manipulation with ordered binary-decision diagrams, ACM Computing Surveys 24, 293\u2013318, 1992.","journal-title":"ACM Computing Surveys"},{"doi-asserted-by":"crossref","unstructured":"Erg\u00fcn, F., Kumar, S. R. and Rubinfeld, R.: On learning bounded-width branching programs, Proc. 8th International Workshop on Computational Learning Theory, 361\u2013368, 1995.","key":"11_CR9","DOI":"10.1145\/225298.225342"},{"unstructured":"Garey, M. and Johnson, D. S.: Computers and intractability: A guide to the theory of NP-completeness, W. H. Freeman and Company, 1978.","key":"11_CR10"},{"doi-asserted-by":"crossref","unstructured":"Gavald\u00e0, R. and Guijarro, D.: Learning ordered binary decision diagrams, Proc. 6th International Workshop on Algorithmic Learning Theory, 228\u2013238, LNAI 997, 1995.","key":"11_CR11","DOI":"10.1007\/3-540-60454-5_41"},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","volume":"37","author":"E. M. Gold","year":"1978","unstructured":"Gold, E. M.: Complexity of automaton identification from given data, Information and Control 37, 302\u2013320, 1978.","journal-title":"Information and Control"},{"doi-asserted-by":"crossref","unstructured":"Hancock, T., Jiang, T., Li, M. and Tromp, J.: Lower bounds on learning decision lists and trees, draft, 1996.","key":"11_CR13","DOI":"10.1006\/inco.1996.0040"},{"unstructured":"Li, M. and Vazirani, U.: On the learnability of finite automata, Proc. 1988 Workshop on Computational Learning Theory, 359\u2013370, 1988.","key":"11_CR14"},{"doi-asserted-by":"crossref","unstructured":"Lund, C. and Yannakakis, M.: On the hardness of approximating minimization problems, Proc. 25th Annual ACM Symposium on Theory of Computing, 286\u2013293, 1993.","key":"11_CR15","DOI":"10.1145\/167088.167172"},{"key":"11_CR16","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L. and Valiant, L. G.: Computational limitation on learning from examples, Journal of the Association for Computing Machinery 35, 965\u2013984, 1988.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"11_CR17","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1145\/138027.138042","volume":"40","author":"L. Pitt","year":"1993","unstructured":"Pitt, L. and Warmuth, M. K.: The minimum consistent DFA problem cannot be approximated within any polynomial, Journal of the Association for Computing Machinery 40, 95\u2013142, 1993.","journal-title":"Journal of the Association for Computing Machinery"},{"unstructured":"Sauerhoff, M. and Wegener, I.: On the complexity of minimizing the OBDD size for incompletely specified functions, Technical Report 560, Univ. Dortmund, 1994.","key":"11_CR18"},{"key":"11_CR19","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1016\/0020-0190(93)90256-9","volume":"48","author":"D. Sieling","year":"1993","unstructured":"Sieling, D. and Wegener, I.: Reduction of OBDDs in linear time, Information Processing Letter 48, 139\u2013144, 1993.","journal-title":"Information Processing Letter"},{"unstructured":"Takenaga, Y. and Yajima, S.: NP-completeness of minimum binary decision diagram identification, Technical Report of IEICE, COMP92-99, 57\u201362, 1993.","key":"11_CR20"},{"key":"11_CR21","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G.: A theory of the learnable, Communications of the ACM 27, 1134\u20131142, 1984.","journal-title":"Communications of the ACM"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_125.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:05:58Z","timestamp":1605647158000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_125"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_125","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}