{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:23:38Z","timestamp":1725488618065},"publisher-location":"Berlin, Heidelberg","reference-count":26,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424871"},{"type":"electronic","value":"9783540446699"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44669-9_18","type":"book-chapter","created":{"date-parts":[[2007,8,10]],"date-time":"2007-08-10T10:32:26Z","timestamp":1186741946000},"page":"172-183","source":"Crossref","is-referenced-by-count":1,"title":["Prediction-Preserving Reducibility with Membership Queries on Formal Languages"],"prefix":"10.1007","author":[{"given":"Kouichi","family":"Hirata","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hiroshi","family":"Sakamoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,2]]},"reference":[{"issue":"6","key":"18_CR1","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"A. V. Aho","year":"1975","unstructured":"A. V. Aho, M. J. Corasick, Efficient string matching: An aid to bibliographic search, Comm. ACM 18(6) (1975), 333\u2013340.","journal-title":"Comm. ACM"},{"issue":"1","key":"18_CR2","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, J. Comput. System Sci. 21(1) (1980) 46\u201362.","journal-title":"J. Comput. System Sci."},{"issue":"2","key":"18_CR3","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) (1987) 87\u2013106.","journal-title":"Inform. Comput."},{"unstructured":"D. Angluin, Learning k-bounded context-free grammars, Technical Report YALEU\/DCS\/RR-557, Yale University, 1987.","key":"18_CR4"},{"issue":"4","key":"18_CR5","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin, Queries and concept learning, Mach. Learn. 2(4) (1988) 319\u2013342.","journal-title":"Mach. Learn."},{"issue":"2","key":"18_CR6","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1995.1026","volume":"50","author":"D. Angluin","year":"1995","unstructured":"D. Angluin, M. Kharitonov, When won\u2019t membership queries help?, J. Comput. System Sci. 50(2) (1995) 336\u2013355.","journal-title":"J. Comput. System Sci."},{"doi-asserted-by":"crossref","unstructured":"A. Ginsburg, The mathematical theory of context free languages (McGraw-Hill, 1966).","key":"18_CR7","DOI":"10.1109\/FOCS.1965.7"},{"unstructured":"M. A. Harrison, Introduction to formal language theory (Addison-Wesley, 1978).","key":"18_CR8"},{"unstructured":"J. E. Hopcroft, J. D. Ullman, Introduction to automata theory, languages and computation (Addison-Wesley, 1979).","key":"18_CR9"},{"issue":"2","key":"18_CR10","first-page":"151","volume":"5","author":"H. Ishizaka","year":"1990","unstructured":"H. Ishizaka, Polynomial time learnability of simple deterministic languages, Mach. Learn. 5(2) (1990) 151\u2013164.","journal-title":"Mach. Learn."},{"doi-asserted-by":"crossref","unstructured":"M. Kearns, L. Pitt, A polynomial-time algorithm for learning k-variable pattern languages from examples, in: Proc. 2nd Ann. Conf. on Computational Learning Theory (ACM, 1989) 57\u201371.","key":"18_CR11","DOI":"10.1016\/B978-0-08-094829-4.50007-6"},{"issue":"1","key":"18_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"M. Kearns, L. Valiant, Cryptographic limitations on learning Boolean formulae and finite automata, J. ACM 41(1) (1994) 67\u201395.","journal-title":"J. ACM"},{"issue":"2","key":"18_CR13","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/0890-5401(87)90026-5","volume":"74","author":"A. Marron","year":"1987","unstructured":"A. Marron, Identification of pattern languages from examples and queries, Inform. Comput. 74(2) (1987) 91\u2013112.","journal-title":"Inform. Comput."},{"unstructured":"A. Marron, Learning pattern languages from a single initial example and from queries, in: Proc. 1st Ann. Workshop on Computational Learning Theory (ACM, 1988) 345\u2013358.","key":"18_CR14"},{"doi-asserted-by":"crossref","unstructured":"S. Matsumoto, A. Shinohara, Learning pattern languages using queries, in: Proc. 3rd Euro. Conf. on Computational Learning Theory, LNAI 1208 (Springer, 1997) 185\u2013197.","key":"18_CR15","DOI":"10.1007\/3-540-62685-9_16"},{"issue":"3","key":"18_CR16","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1145\/321406.321411","volume":"14","author":"R. McNaughton","year":"1967","unstructured":"R. McNaughton, Parenthesis grammars, J. ACM 14(3) (1967) 490\u2013500.","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"J. Nessel, S. Lange, Learning erasing pattern languages with queries, in: Proc. 11th Internat. Conf. on Algorithmic Learning Theory, LNAI 1968 (Springer, 2000) 86\u2013100.","key":"18_CR17","DOI":"10.1007\/3-540-40992-0_7"},{"issue":"3","key":"18_CR18","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"L. Pitt, M. K. Warmuth, Prediction-preserving reduction, J. Comput. System Sci. 41(3) (1990) 430\u2013467.","journal-title":"J. Comput. System Sci."},{"issue":"2\u20133","key":"18_CR19","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(90)90017-C","volume":"76","author":"Y. Sakakibara","year":"1990","unstructured":"Y. Sakakibara, Learning context-free grammars from structural data in polynomial time, Theor. Comput. Sci. 76(2\u20133) (1990) 223\u2013242.","journal-title":"Theor. Comput. Sci."},{"key":"18_CR20","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/B978-0-12-037102-0.50010-8","volume":"2","author":"Y. Sakakibara","year":"1990","unstructured":"Y. Sakakibara, On learning Smullyan\u2019s elementary formal systems: Towards an efficient learning method for context-sensitive languages, Adv. Soft. Sci. Tech. 2 (1990) 79\u2013101.","journal-title":"Adv. Soft. Sci. Tech."},{"doi-asserted-by":"crossref","unstructured":"H. Sakamoto, Language learning from membership queries and characteristic examples, in: Proc. 6th Internat. Workshop on Algorithmic Learning Theory, LNAI 997 (Springer, 1995) 55\u201365.","key":"18_CR21","DOI":"10.1007\/3-540-60454-5_28"},{"unstructured":"H. Sakamoto, K. Hirata, H. Arimura, Learning elementary formal systems with queries, Technical Report DOI-TR-179, Department of Informatics, Kyushu University, 2000. Also available at http:\/\/www.i.kyushu-u.ac.jp\/doi-tr.html .","key":"18_CR22"},{"doi-asserted-by":"crossref","unstructured":"N. Sugimoto, T. Toyoshima, S. Shimozono, K. Hirata, Constructive learning of context-free languages with a subpansive tree, in: Proc. 5th Internat. Colloq. on Grammatical Inference, LNAI 1891 (Springer, 2000) 270\u2013283.","key":"18_CR23","DOI":"10.1007\/978-3-540-45257-7_22"},{"key":"18_CR24","first-page":"61","volume":"18","author":"E. Shamir","year":"1965","unstructured":"E. Shamir, On sequential languages and two classes of regular events, Zeit. Phone., Sprach. und Kommun. 18 (1965) 61\u201369.","journal-title":"Zeit. Phone., Sprach. und Kommun"},{"key":"18_CR25","series-title":"Lect Notes Comput Sci","first-page":"115","volume-title":"Proc. RIMS Symposia on Software Science and Engineering","author":"T. Shinohara","year":"1982","unstructured":"T. Shinohara, Polynomial time inference of extended regular pattern languages, in: Proc. RIMS Symposia on Software Science and Engineering, LNCS 147 (Springer, 1982) 115\u2013127."},{"key":"18_CR26","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/S0304-3975(99)00270-4","volume":"241","author":"T. Shinohara","year":"2000","unstructured":"T. Shinohara, H. Arimura, Inductive inference of unbounded unions of pattern languages from positive data, Theor. Comput. Sci. 241 (2000) 191\u2013209.","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44669-9_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,1]],"date-time":"2019-05-01T22:13:24Z","timestamp":1556748804000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44669-9_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424871","9783540446699"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/3-540-44669-9_18","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}