{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,1]],"date-time":"2024-06-01T16:29:53Z","timestamp":1717259393427},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2000,9,1]],"date-time":"2000-09-01T00:00:00Z","timestamp":967766400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["New Gener Comput"],"published-print":{"date-parts":[[2000,9]]},"DOI":"10.1007\/bf03037530","type":"journal-article","created":{"date-parts":[[2009,4,23]],"date-time":"2009-04-23T23:17:12Z","timestamp":1240528632000},"page":"217-242","source":"Crossref","is-referenced-by-count":23,"title":["Polynomial-time learning of elementary formal systems"],"prefix":"10.1007","volume":"18","author":[{"given":"Satoru","family":"Miyano","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takeshi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF03037530_CR1","doi-asserted-by":"crossref","unstructured":"Abe, N., \u201cPolynomial Learnability and Locality of Formal Grammars,\u201d inProc. 26th Meeting of the Assciation for Computational Linguistics, 1988.","DOI":"10.3115\/982023.982051"},{"key":"BF03037530_CR2","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1016\/0022-0000(80)90041-0","volume":"21","author":"D. Angluin","year":"1980","unstructured":"Angluin, D., \u201cFinding Patterns Common to a Set of Strings,\u201dJournal of Computer and System Sciences, 21, pp. 46\u201362, 1980.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF03037530_CR3","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0890-5401(87)90052-6","volume":"75","author":"D. Angluin","year":"1987","unstructured":"Angluin, D., \u201cLearning Regular Sets from Queries and Counterexamples,\u201dInformation and Computation, 75, pp. 87\u2013106, 1987.","journal-title":"Information and Computation"},{"key":"BF03037530_CR4","doi-asserted-by":"crossref","unstructured":"Arikawa, S., Kuhara, S., Miyano, S., Shinohara, A., and Shinohara, T., \u201cA Learning Algorithm for Elementary Formal Systems and its Experiments on Identification of Transmembrane Domains,\u201d inProc. 25th Hawaii International Conference on System Sciences, Vol. I, pp. 675\u2013684, 1992.","DOI":"10.1109\/HICSS.1992.183220"},{"key":"BF03037530_CR5","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0304-3975(92)90068-Q","volume":"95","author":"S. Arikawa","year":"1992","unstructured":"Arikawa, S., Shinohara, T., and Yamamoto, A., \u201cLearning Elementary Formal Systems,\u201dTheoretical Computer Science, 95, pp. 97\u2013113, 1992.","journal-title":"Theoretical Computer Science"},{"key":"BF03037530_CR6","unstructured":"Arimura, H.,Personal Communication, 1993."},{"key":"BF03037530_CR7","doi-asserted-by":"crossref","unstructured":"Berger, B., Rompel, J., and Shor, P., \u201cEfficient NC Algorithms for Set Cover with Application to Learning and Geometry,\u201d inProc. of the 30th Annual Symposium on Foundations of Computer Science, pp. 54\u201359, 1989.","DOI":"10.1109\/SFCS.1989.63455"},{"issue":"4","key":"BF03037530_CR8","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M., \u201cLearnability and the Vapnik-Chervonenkis Dimension,\u201dJACM, 36, 4, pp. 929\u2013965, 1989.","journal-title":"JACM"},{"issue":"3","key":"BF03037530_CR9","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V. Chvatal","year":"1979","unstructured":"Chvatal, V., \u201cA Greedy Heuristic for the Set Covering Problem,\u201dMathematics of Operations Research, 4, 3, pp. 233\u2013235, 1979.","journal-title":"Mathematics of Operations Research"},{"key":"BF03037530_CR10","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E. Gold","year":"1967","unstructured":"Gold, E., \u201cLanguage Identification in the Limit,\u201dInformation and Control, 10, pp. 447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"BF03037530_CR11","unstructured":"Haussler, D., Kearns, M., Littlestone, N., and Warmuth, M., \u201cEquivalence of Models for Polynomial Learnability,\u201d inProc. of the 1st Workshop on Computational Learning Theory, pp. 34\u201350, 1988."},{"key":"BF03037530_CR12","doi-asserted-by":"crossref","unstructured":"Jiang, T. and Li, M., \u201cOn the Complexity of Learning Strings and Sequences,\u201d inProc. of the 4th Annual Workshop on Computational Learning Theory, pp. 367\u2013371, 1991.","DOI":"10.1016\/B978-1-55860-213-7.50036-5"},{"issue":"3","key":"BF03037530_CR13","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01200064","volume":"1","author":"K. Ko","year":"1991","unstructured":"Ko, K. and Tzeng, W., \u201cThree \u03a3 2 p -complete Problems in Computational Learning Theory,\u201dComputational Complexity, 1, 3, pp. 269\u2013310, 1991.","journal-title":"Computational Complexity"},{"key":"BF03037530_CR14","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"Maier, D., \u201cThe Complexity of Some Problems on Subsequences and Supersequences,\u201dJACM, 25, pp. 322\u2013336, 1978.","journal-title":"JACM"},{"key":"BF03037530_CR15","doi-asserted-by":"crossref","unstructured":"Moriyama, T. and Sato, M., \u201cProperties of Language Classes with Finite Elasticity,\u201d inProc. 4th International Workshop on Algorithmic Learning Theory (Lecture Notes In Artificial Intelligence 744), pp. 187\u2013196, 1993.","DOI":"10.1007\/3-540-57370-4_47"},{"key":"BF03037530_CR16","doi-asserted-by":"crossref","unstructured":"Mukouchi, Y. and Arikawa, S., \u201cInductive Inference Machines that can Refute Hypothesis Spaces,\u201d inProc. 4th International Workshop on Algorithmic Learning Theory (Lecture Notes in Artificial Intelligence 744), pp. 123\u2013136, 1993.","DOI":"10.1007\/3-540-57370-4_42"},{"issue":"1","key":"BF03037530_CR17","first-page":"67","volume":"4","author":"B. Natarajan","year":"1989","unstructured":"Natarajan, B., \u201cOn Learning Sets and Functions,\u201dMachine Learning, 4, 1., pp. 67\u201397, 1989.","journal-title":"Machine Learning"},{"key":"BF03037530_CR18","unstructured":"Natarajan, B.,Machine Learning \u2014 A Theoretical Approach, Morgan Kaufmann Publishers, 1991."},{"issue":"2","key":"BF03037530_CR19","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/0022-0000(80)90036-7","volume":"21","author":"W. Ruzzo","year":"1980","unstructured":"Ruzzo, W., \u201cTree-size Bounded Alternation,\u201dJournal of Computer and System Sciences, 21, 2, pp. 218\u2013235, 1980.","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"BF03037530_CR20","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"W. Ruzzo","year":"1981","unstructured":"Ruzzo, W., \u201cOn Uniform Circuit Complexity,\u201dJournal of Computer and System Sciences, 22, 3, pp. 365\u2013383, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF03037530_CR21","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":"Sakakibara, Y., \u201cOn Learning Smullyan\u2019s Elementary Formal Systems: Towards an Efficient Learning for Context-sensitive Languages,\u201dAdvances in Software Science and Technology, 2, pp. 79\u2013101, 1990.","journal-title":"Advances in Software Science and Technology"},{"key":"BF03037530_CR22","doi-asserted-by":"crossref","unstructured":"Schapire, R., \u201cPattern Languages are not Learnable,\u201d inProceedings of the 3rd Annual Workshop on Computational Learning Theory, pp. 122\u2013129, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50012-6"},{"key":"BF03037530_CR23","unstructured":"Shinohara, T., \u201cPolynomial Time Inference of Pattern Languages and its Applications,\u201d inProc. 7th IBM Symp. Math. Found. Comp. Sci., pp. 191\u2013209, 1982."},{"key":"BF03037530_CR24","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/3-540-11980-9_19","volume":"147","author":"T. Shinohara","year":"1983","unstructured":"Shinohara, T., \u201cPolynomial Time Inference of Extended Regular Pattern Languages,\u201dLecture Notes in Computer Science, 147, pp. 115\u2013127, 1983.","journal-title":"Lecture Notes in Computer Science"},{"key":"BF03037530_CR25","doi-asserted-by":"crossref","unstructured":"Shinohara, T., \u201cInductive Inference from Positive Data is Powerful,\u201d inProceedings of the 3rd Annual Workshop on Computational Learning Theory, pp. 97\u2013110, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50010-2"},{"key":"BF03037530_CR26","doi-asserted-by":"crossref","unstructured":"Smullyan, R.,Theory of Formal Systems, Princeton University Press, 1961.","DOI":"10.1515\/9781400882007"},{"issue":"3","key":"BF03037530_CR27","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1145\/322077.322083","volume":"25","author":"I. Sudborough","year":"1978","unstructured":"Sudborough, I., \u201cOn the Tape Complexity of Deterministic Context-free Languages,\u201dJACM, 25, 3, pp. 405\u2013414, 1978.","journal-title":"JACM"},{"issue":"11","key":"BF03037530_CR28","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. Valiant","year":"1984","unstructured":"Valiant, L., \u201cA Theory of the Learnable,\u201dCACM, 27, 11, pp. 1134\u20131142, 1984.","journal-title":"CACM"},{"key":"BF03037530_CR29","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0890-5401(92)90047-J","volume":"96","author":"J. S. Vitter","year":"1992","unstructured":"Vitter, J. S. and Lin, J.-H., \u201cLearning in Parallel,\u201dInformation and Computation, 96, pp. 179\u2013202, 1992.","journal-title":"Information and Computation"},{"key":"BF03037530_CR30","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. Wagner","year":"1974","unstructured":"Wagner, R. and Fischer, M., \u201cThe String-to-string Correction Problem\u201dJACM, 21, pp. 168\u201373, 1974.","journal-title":"JACM"},{"issue":"1","key":"BF03037530_CR31","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0743-1066(92)90022-U","volume":"13","author":"A. Yamamoto","year":"1992","unstructured":"Yamamoto, A., \u201cProcedural Semantics and Negative Information of Elementary Formal System,\u201dJournal of Logic Programming, 13, 1, pp. 89\u201397, 1992.","journal-title":"Journal of Logic Programming"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037530.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF03037530\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037530","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T20:52:39Z","timestamp":1558558359000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF03037530"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,9]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2000,9]]}},"alternative-id":["BF03037530"],"URL":"https:\/\/doi.org\/10.1007\/bf03037530","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"value":"0288-3635","type":"print"},{"value":"1882-7055","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,9]]}}}