{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T21:11:19Z","timestamp":1772745079776,"version":"3.50.1"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[1991,9,1]],"date-time":"1991-09-01T00:00:00Z","timestamp":683683200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Comput Complexity"],"published-print":{"date-parts":[[1991,9]]},"DOI":"10.1007\/bf01200064","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T12:07:51Z","timestamp":1108728471000},"page":"269-310","source":"Crossref","is-referenced-by-count":18,"title":["Three ? P 2 -complete problems in computational learning theory"],"prefix":"10.1007","volume":"1","author":[{"given":"Ker-I","family":"Ko","sequence":"first","affiliation":[]},{"given":"Wen-Guey","family":"Tzeng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","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 (1980), 46?62.","journal-title":"J. Comput. System Sci."},{"key":"CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1987","unstructured":"D. Angluin, Queries and concept learning,Mach. Learn.,2 (1987), 319?342.","journal-title":"Mach. Learn."},{"key":"CR3","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler andM. Warmuth, Learnability and the Vapnik-Chervonenkis dimension,J Assoc. Comput. Mach.,36 (1989), 929?965.","journal-title":"J Assoc. Comput. Mach."},{"key":"CR4","doi-asserted-by":"crossref","unstructured":"R. Board and L. Pitt, On the necessity of Occam algorithms, inProc. 22nd Ann. ACM Symp. Theory of Computing, 1990, 54?63.","DOI":"10.1145\/100216.100223"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"S.A. Cook, The complexity of theory-proving procedures, inProc. 3rd Ann. ACM Symp. Theory of Computing, 1971, 151?158.","DOI":"10.1145\/800157.805047"},{"key":"CR6","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"M.R. Garey andD.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 1979."},{"key":"CR7","doi-asserted-by":"crossref","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F. Harary","year":"1969","unstructured":"F. Harary,Graph Theory, Addison-Wesley, Reading, MA., 1969."},{"key":"CR8","first-page":"42","volume-title":"Proc. 1st Workshop Computational Learning Theory","author":"D. Haussler","year":"1988","unstructured":"D. Haussler, M. Kearns, N. Littlestone andM.K. Warmuth, Equivalence of models for polynomial learnability, inProc. 1st Workshop Computational Learning Theory, Morgan Kaufmann, San Mateo, CA., 1988, 42?55."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"D. Haussler, N. Littlestone and M.K. Warmuth, Predicting {0,1}-functions on randomly drawn points, inProc. 29th Ann. IEEE Symp. Foundations of Computer Science, 1988, 100?109.","DOI":"10.1109\/SFCS.1988.21928"},{"key":"CR10","doi-asserted-by":"crossref","unstructured":"T. Huynh, Deciding the inequivalence of context-free grammars with 1-letter terminal alphabet is ? P 2 -complete, inProc. 23rd Ann. IEEE Sympo. Foundations of Computer Science, 1982, 21?31.","DOI":"10.1109\/SFCS.1982.65"},{"key":"CR11","doi-asserted-by":"crossref","unstructured":"R. Karp and R. Lipton, Some connections between nonuniform and uniform complexity classes, inProc. 12th Ann. ACM Symp. Thoery of Computing, 1980, 302?309.","DOI":"10.1145\/800141.804678"},{"key":"CR12","first-page":"57","volume-title":"Proceedings of the 2nd Workshop on Computational Learning Theory","author":"M. Kearns","year":"1989","unstructured":"M. Kearns andL. Pitt, A polynomial time algorithm for learningk-variable pattern languages from examples, inProceedings of the 2nd Workshop on Computational Learning Theory, Morgan Kaufmann, San Mateo, CA., 1989, 57?71."},{"key":"CR13","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(87)90006-7","volume":"34","author":"K. Ko","year":"1987","unstructured":"K. Ko andC. Hua, A note on the two-variable pattern-finding problem,J. Comput. System Sci.,34 (1987), 75?86.","journal-title":"J. Comput. System Sci."},{"key":"CR14","first-page":"384","volume-title":"Proc. 7th Intern. Conf. Machine Learning","author":"K. Ko","year":"1990","unstructured":"K. Ko, A. Marron andW. Tzeng, Learning string patterns and tree patterns from examples, inProc. 7th Intern. Conf. Machine Learning, Morgan Kaufmann, San Mateo, CA., 1990, 384?391."},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"A.R. Meyer and L.J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space, inProc. 13th IEEE Symposium on Switching and Automata Theory, 1972, 125?129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"L. Pitt andL.G. Valiant, Computational limitations on learning from examples.J. Assoc. Comput. Mach.,35 (1988), 965?984.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR17","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"L. Pitt andM.K. Warmuth, Prediction-preserving reducibility,J. Comput. System Sci.,41 (1990), 430?467.","journal-title":"J. Comput. System Sci."},{"key":"CR18","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1145\/322217.322221","volume":"27","author":"Y. Sagiv","year":"1980","unstructured":"Y. Sagiv andM. Yannakakis, Equivalences among relational expressions with the union and difference operators,J. Assoc. Comput. Mach.,27 (1980), 633?655.","journal-title":"J. Assoc. Comput. Mach."},{"key":"CR19","first-page":"197","volume":"5","author":"R.E. Schapire","year":"1990","unstructured":"R.E. Schapire, The strength of weak learnability,Mach. Learn.,5 (1990), 197?227.","journal-title":"Mach. Learn."},{"key":"CR20","first-page":"122","volume-title":"Proc. 3rd Workshop Computational Learning Theory","author":"R.E. Schapire","year":"1990","unstructured":"R.E. Schapire, Pattern languages are not learnable, inProc. 3rd Workshop Computational Learning Theory, Morgan Kaufmann, San Mateo, CA., 1990, 122?129."},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"L.J. Stockmeyer and A.R. Meyer, Word problems requiring exponential time, inProc. 5th Ann. ACM Symp Theory of Computing, 1973, 1?9.","DOI":"10.1145\/800125.804029"},{"key":"CR22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(76)90061-X","volume":"3","author":"L.J. Stockmeyer","year":"1977","unstructured":"L.J. Stockmeyer, The polynomial-time hierarchy,Theoret. Comput. Sci.,3 (1977), 1?22.","journal-title":"Theoret. Comput. Sci."},{"key":"CR23","first-page":"1134","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"L.G. Valiant, A theory of the learnable,Comm. Assoc. Comput. Mach.,27 (1984), 1134?1142.","journal-title":"Comm. Assoc. Comput. Mach."},{"key":"CR24","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1007\/BF00289117","volume":"23","author":"K.W. Wagner","year":"1986","unstructured":"K.W. Wagner, The complexity of combinatorial problems with succinct input representation,Acta Inform.,23 (1986), 325?356.","journal-title":"Acta Inform."},{"key":"CR25","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0304-3975(76)90062-1","volume":"3","author":"C. Wrathall","year":"1977","unstructured":"C. Wrathall, Complete sets and the polynomial-time hierarchy,Theoret. Comput. Sci.,3 (1977), 23?33.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Computational Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200064.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01200064\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01200064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T20:57:10Z","timestamp":1586120230000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01200064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1991,9]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1991,9]]}},"alternative-id":["BF01200064"],"URL":"https:\/\/doi.org\/10.1007\/bf01200064","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[1991,9]]}}}