{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:15:38Z","timestamp":1759637738351},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602460"},{"type":"electronic","value":"9783540447689"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60246-1_132","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:55:54Z","timestamp":1330278954000},"page":"257-266","source":"Crossref","is-referenced-by-count":2,"title":["Graph inference from a walk for trees of bounded degree 3 is NP-complete"],"prefix":"10.1007","author":[{"given":"Osamu","family":"Maruyama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Satoru","family":"Miyano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,2]]},"reference":[{"key":"24_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:337\u2013350, 1978.","journal-title":"Inform. Control"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proc. 33rd IEEE Symp. Foundations of Computer Science, pages 14\u201323, 1992.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"J. A. Aslam and R. L. Rivest. Inferring graphs from walks. In Proc. 3rd Workshop on Computational Learning Theory, pages 359\u2013370, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50031-X"},{"key":"24_CR4","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979."},{"key":"24_CR5","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":"24_CR6","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02090396","volume":"24","author":"J. Haralambides","year":"1991","unstructured":"J. Haralambides, F. Makedon, and B. Monien. Badndwidth minimization: An approximation algorithm for caterpillars. Math. Systems Theory, 24:169\u2013177, 1991.","journal-title":"Math. Systems Theory"},{"key":"24_CR7","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/3-540-55808-X_37","volume":"629","author":"O. Maruyama","year":"1992","unstructured":"O. Maruyama and S. Miyano. Inferring a tree from walks. In Proc. 17th Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, volume 629, pages 383\u2013391, 1992; To appear in Theoretical Computer Science.","journal-title":"Lecture Notes in Computer Science"},{"issue":"3","key":"24_CR8","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. J. Comput. System Sci., 43(3):425\u2013440, 1991.","journal-title":"J. Comput. System Sci."},{"key":"24_CR9","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley Publishing Company, 1994."},{"key":"24_CR10","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1016\/S0022-0000(05)80089-3","volume":"49","author":"V. Raghavan","year":"1994","unstructured":"V. Raghavan. Bounded degree graph inference from walks. J. Comput. System Sci., 49:108\u2013132, 1994.","journal-title":"J. Comput. System Sci."},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"S. Rudich. Inferring the structure of a Markov chain from its output. In Proc. 26th IEEE Symp. Foundations of Computer Science, pages 321\u2013326, 1985.","DOI":"10.1109\/SFCS.1985.34"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1995"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60246-1_132.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:34:10Z","timestamp":1619573650000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60246-1_132"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602460","9783540447689"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/3-540-60246-1_132","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}