{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T00:28:56Z","timestamp":1725496136038},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540650133"},{"type":"electronic","value":"9783540497301"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49730-7_18","type":"book-chapter","created":{"date-parts":[[2007,11,29]],"date-time":"2007-11-29T10:01:18Z","timestamp":1196330478000},"page":"234-246","source":"Crossref","is-referenced-by-count":0,"title":["Finding a One-Variable Pattern from Incomplete Data"],"prefix":"10.1007","author":[{"given":"Hiroshi","family":"Sakamoto","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,9,24]]},"reference":[{"key":"18_CR1","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"D. Angluin. Finding patterns common to a set of strings. Journal of Computer and System Sciences 21:46\u201362, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"18_CR2","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1007\/BF03037183","volume":"11","author":"S. Arikawa","year":"1993","unstructured":"S. Arikawa, S. Miyano, A. Shinohara, S. Kuhara, Y. Mukouchi and T. Shinohara. A machine discovery from amino acid sequences by decision trees over regular patterns. New Generation Computing 11:361\u2013375, 1993.","journal-title":"New Generation Computing"},{"key":"18_CR3","doi-asserted-by":"crossref","unstructured":"E. Boros, T. Ibaraki and K. Makino. Monotone extensions of Boolean data sets. In Proc. 8th International Workshop on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence 1316, pp. 161\u2013175, Berlin, 1997. Springer-Verlag.","DOI":"10.1007\/3-540-63577-7_42"},{"key":"18_CR4","doi-asserted-by":"crossref","unstructured":"T. Erlebach, P. Rossmanith, H. Stadtherr, A. Steger and T. Zeugmann. Learning one-variable pattern languages very eciently on average, in parallel, and by asking queries. In Proc. 8th International Workshop on Algorithmic Learning Theory, Lecture Notes in Artificial Intelligence 1316, pp. 260\u2013276, Berlin, 1997. Springer-Verlag.","DOI":"10.1007\/3-540-63577-7_48"},{"key":"18_CR5","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and company, 1983."},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"M.E. Gold. Language identication in the limit. Information and Control 10:447\u2013474.","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"18_CR7","unstructured":"J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Publ., 1979."},{"key":"18_CR8","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1007\/3-540-56939-1_81","volume-title":"Proc. 20th ICALP","author":"T. Jiang","year":"1993","unstructured":"T. Jiang, A. Salomaa, K. Salomaa and S. Yu. Inclusion is undecidable for pattern languages. In Proc. 20th ICALP, Lecture Notes in Computer Science 700, pp. 301\u2013312, Berlin, 1993. Springer-Verlag."},{"key":"18_CR9","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M.J. Kearns","year":"1994","unstructured":"M.J. Kearns and U.J. Vazirani. An Introduction to Computational Learning Theory. The MIT Press, Cambridge, MA 1994."},{"key":"18_CR10","unstructured":"C.H. Papadimitriou. Computational complexity. Addison-Wesley Publ., 1994."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"R. Reischuk and T. Zeugmann. Learning One-variable pattern languages in linear average time. In Proc. 11st Ann. Conference on Computational Learning Theory, 1998, to appear.","DOI":"10.1145\/279943.279984"},{"key":"18_CR12","first-page":"122","volume-title":"Proc. 3rd Annual ACM Workshop on Computational Learning Theory","author":"R.E. Schapire","year":"1990","unstructured":"R.E. Schapire. Pattern languages are not learnable. In M.A. Fulk and J. Case, editors, Proc. 3rd Annual ACM Workshop on Computational Learning Theory, pp. 122\u2013129, 1990. Morgan Kaufmann Publishers Inc., San Mateo."},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"T. Shinohara and S. Arikawa. Pattern inference. In Algorithmic Learning for Knowledge-Based Systems, Lecture Notes in Artificial Intelligence 961, pp. 259\u2013291, Berlin, 1995. Springer-Verlag.","DOI":"10.1007\/3-540-60217-8_13"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1080\/09528139408953785","volume":"6","author":"R. Wiehagen","year":"1994","unstructured":"R. Wiehagen and T. Zeugmann. Ignoring data may be the only way to learn eciently. Journal of Experimental and Theoretical Artificial Intelligence 6:131\u2013144, 1994.","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"key":"18_CR15","doi-asserted-by":"crossref","unstructured":"T. Zeugmann and S. Lange. A guided tour across the boundaries of learning recursive languages. In Algorithmic Learning for Knowledge-Based Systems, (K.P. Jantke and S. Lange, Eds.), Lecture Notes in Artificial Intelligence 961, pp. 193\u2013262, Berlin, 1995. Springer-Verlag.","DOI":"10.1007\/3-540-60217-8_12"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"T. Zeugmann, S. Lange and S. Kapur. Characterizations of monotonic and dual monotonic language learning. Information and Computation 120(2):155\u2013173.","DOI":"10.1006\/inco.1995.1107"}],"container-title":["Lecture Notes in Computer Science","Algorithmic Learning Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49730-7_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,5]],"date-time":"2019-05-05T08:19:16Z","timestamp":1557044356000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49730-7_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540650133","9783540497301"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-49730-7_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}