{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,18]],"date-time":"2025-05-18T15:05:40Z","timestamp":1747580740519},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1994,9,1]],"date-time":"1994-09-01T00:00:00Z","timestamp":778377600000},"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":[[1994,9]]},"DOI":"10.1007\/bf03037352","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T23:14:17Z","timestamp":1240355657000},"page":"359-374","source":"Crossref","is-referenced-by-count":2,"title":["On PAC learnability of functional dependencies"],"prefix":"10.1007","volume":"12","author":[{"given":"Tatsuya","family":"Akutsu","sequence":"first","affiliation":[]},{"given":"Atsuhiro","family":"Takasu","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"BF03037352_CR1","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1145\/362384.362685","volume":"13","author":"E. F. Codd","year":"1970","unstructured":"Codd, E. F., \u201cA Relational Model for Large Shared Data Banks,\u201dCommunications of ACM, 13, pp. 377\u2013387, 1970.","journal-title":"Communications of ACM"},{"key":"BF03037352_CR2","unstructured":"Ullman, J. D.,Principles of Database and Knowledge-Base Systems, Vol. 1, Computer Science Press, 1988."},{"key":"BF03037352_CR3","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G., \u201cA Theory of the Learnable,\u201dCommunications of ACM, 27, pp. 1134\u20131142, 1984.","journal-title":"Communications of ACM"},{"key":"BF03037352_CR4","doi-asserted-by":"crossref","first-page":"591","DOI":"10.1002\/int.4550070703","volume":"7","author":"M. Kantola","year":"1992","unstructured":"Kantola, M., Mannila, H., R\u00e4lh\u00e4, K., and Siirtola, H., \u201cDiscovering Functional and Inclusion Dependencies in Relational Databases,\u201dInternational Journal of Intelligent Systems, 7, pp. 591\u2013607, 1992.","journal-title":"International Journal of Intelligent Systems"},{"key":"BF03037352_CR5","unstructured":"Ziarko, W., \u201cThe Discovery, Analysis, and Representation of Data Dependencies in Databases,\u201dProc. of AAAI-91 Workshop on Knowledge Discovery in Databases, AAAI Press, pp. 195\u2013209, 1991."},{"key":"BF03037352_CR6","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/0890-5401(89)90010-2","volume":"80","author":"J. R. Quinlan","year":"1989","unstructured":"Quinlan, J. R. and Rivest, R. L., \u201cInferring Decision Trees Using the Minimum Description Length Principle,\u201dInformation and Computation, 80, pp. 227\u2013248, 1989.","journal-title":"Information and Computation"},{"key":"BF03037352_CR7","unstructured":"Piatetsky-Shapiro, G., \u201cDiscovery and Analysis of Strong Rules in Databases,\u201dProc. of Advanced Database System Symposium, Information Processing Society of Japan, pp. 135\u2013142, 1989."},{"key":"BF03037352_CR8","unstructured":"Sonoo, K., Kawano, H., Nishio, S., and Hasegawa, T., \u201cAccuracy Evaluation of Rules Derived form Sample Data in VLKD\u201d (in Japanese),Proc. of the 5th Conference of Japanese Society of Artificial Intelligence, Japanese Society for Artificial Intelligence, pp. 181\u2013184, 1989."},{"key":"BF03037352_CR9","unstructured":"Mannila, H. and R\u00e4ih\u00e4, K., \u201cDependency Inference,\u201dProc. of the 13th VLDB Conference, pp. 155\u2013158, 1987."},{"key":"BF03037352_CR10","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0166-218X(92)90031-5","volume":"40","author":"H. Mannila","year":"1992","unstructured":"Mannila, H. and R\u00e4ih\u00e4, K., \u201cOn the Complexity of Inferring Functional Dependencies,\u201dDiscrete Applied Mathematics, 40, pp. 237\u2013243, 1992.","journal-title":"Discrete Applied Mathematics"},{"key":"BF03037352_CR11","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0166-218X(92)90177-C","volume":"39","author":"P. Flajolet","year":"1992","unstructured":"Flajolet, P., Gardy, D., and Thimonier, L., \u201cBirthday Paradox, Coupon Collectors, Cashing Algorithms and Self-Organizing Search,\u201dDiscrete Applied Mathematics, 39, pp. 207\u2013229, 1992.","journal-title":"Discrete Applied Mathematics"},{"key":"BF03037352_CR12","doi-asserted-by":"crossref","unstructured":"Kivinen, J. and Mannila, H., \u201cApproximate Dependency Inference from Relations,\u201dProc. of 4th International Conference of Database Theory, Springer-Verlag, pp. 86\u201398, 1992.","DOI":"10.1007\/3-540-56039-4_34"},{"key":"BF03037352_CR13","unstructured":"Kivinen, J. and Mannila, H., \u201cThe Power of Sampling in Knowledge Discovery,\u201dTechnical Report, C-1993-66, University of Helsinki, Department of Computer Science, 1993."},{"key":"BF03037352_CR14","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1990","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M., \u201cLearnability and the Vapnik-Chervonenkis Dimension,\u201dJournal of ACM, 36, pp. 929\u2013965, 1990.","journal-title":"Journal of ACM"},{"key":"BF03037352_CR15","volume-title":"Machine Learning \u2014 A Theoretical Approach","author":"B. K. Natarajan","year":"1991","unstructured":"Natarajan, B. K.,Machine Learning \u2014 A Theoretical Approach, Morgan Kaufmann, CA, 1991."},{"key":"BF03037352_CR16","doi-asserted-by":"crossref","unstructured":"Haussler, D., \u201cGeneralizing the PAC Model: Sample Size Bounds from Metric Dimension-Based Uniform Convergence Results,\u201dProc. of the 30th Annual Symposium on Foundations of Computer Science, IEEE, pp. 40\u201345, 1989.","DOI":"10.1109\/SFCS.1989.63453"},{"key":"BF03037352_CR17","doi-asserted-by":"crossref","unstructured":"Yamanishi, K., \u201cA Learning Criterion for Stochastic Rules,\u201dProc. of the 3rd Workshop on Computational Learning Theory, ACM, pp. 76\u201381, 1990.","DOI":"10.1016\/B978-1-55860-146-8.50008-4"},{"key":"BF03037352_CR18","doi-asserted-by":"crossref","unstructured":"Kearns, J. K., Schapire, R. E., and Linda, M. S., \u201cTowards Efficient Agnostic Learning,\u201dProc. of the 5th Workshop on Computational Learning Theory, ACM, pp. 341\u2013353, 1992.","DOI":"10.1145\/130385.130424"},{"key":"BF03037352_CR19","unstructured":"Takasu, A. and Akutsu, T., \u201cAn Approximate Learning Algorithm for Functional Dependencies,\u201dProc. of 47th Conference of Information Processing Society of Japan, Information Processing Society of Japan, pp. 7C-1, 1993."},{"key":"BF03037352_CR20","unstructured":"Akutsu, T. and Takasu, A., \u201cInferring Approximate Functional Dependencies from Sample Data,\u201dProc. of AAAI-93 Workshop on Knowledge Discovery in Databases, AAAI Press, pp. 138\u2013152, 1993."}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037352.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF03037352\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037352","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T20:52:35Z","timestamp":1558558355000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF03037352"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["BF03037352"],"URL":"https:\/\/doi.org\/10.1007\/bf03037352","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"value":"0288-3635","type":"print"},{"value":"1882-7055","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}