{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:05:48Z","timestamp":1737435948372,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540432838"},{"type":"electronic","value":"9783540458418"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45841-7_53","type":"book-chapter","created":{"date-parts":[[2007,8,12]],"date-time":"2007-08-12T08:11:17Z","timestamp":1186906277000},"page":"645-657","source":"Crossref","is-referenced-by-count":3,"title":["Learnability and Definability in Trees and Similar Structures"],"prefix":"10.1007","author":[{"given":"Martin","family":"Grohe","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gyorgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,2,21]]},"reference":[{"key":"53_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/PL00001593","volume":"7","author":"H. Aizenstein","year":"1998","unstructured":"H. Aizenstein, T. Heged\u0171s, L. Hellerstein, and L. Pitt. Complexity-theoretic hardness results for query learning. Computational Complexity, 7:19\u201353, 1998.","journal-title":"Computational Complexity"},{"key":"53_CR2","first-page":"319","volume":"2","author":"D. Angluin","year":"1988","unstructured":"D. Angluin. Queries and concept learning. Machine Learning, 2:319\u2013342, 1988.","journal-title":"Machine Learning"},{"key":"53_CR3","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/3-540-48168-0_2","volume-title":"The consistency dimension, compactness and query learning","author":"J.L. Balc\u00e1zar","year":"1999","unstructured":"J.L. Balc\u00e1zar. The consistency dimension, compactness and query learning. In J. Flum and M. Rodriguez-Artalejo, editors, Computer Science Logic, 13th International Workshop CSL\u201999, volume 1683 of Lecture Notes in Computer Science, pages 2\u201313. Springer-Verlag, 1999."},{"key":"53_CR4","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/3-540-46769-6_7","volume-title":"The consistency dimension and distribution-dependent learning from queries","author":"J.L. Balc\u00e1zar","year":"1999","unstructured":"J.L. Balc\u00e1zar, J. Castro, D. Guijarro, and H.U. Simon. The consistency dimension and distribution-dependent learning from queries. In O. Watanabe and T. Yokomori, editors, Algorithmic Learning Theory, 10th International Conference, ALT\u2019 99, volume 1720 of Lecture Notes in Computer Science, pages 77\u201392. Springer-Verlag, 1999."},{"key":"53_CR5","doi-asserted-by":"crossref","unstructured":"M. Benedikt, L. Libkin, T. Schwentick, and L. Segoufin. A model-theoretic approach to regular string relations. In Proceedings of the 16th IEEE Symposium on Logic in Computer Science, pages 431\u2013440, 2001.","DOI":"10.1109\/LICS.2001.932518"},{"key":"53_CR6","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"A. Blumer, A. Ehrenfeucht, D. Haussler, and M.K. Warmuth. Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36:929\u2013965, 1989.","journal-title":"Journal of the ACM"},{"key":"53_CR7","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/0022-0000(93)90004-G","volume":"46","author":"B. Courcelle","year":"1993","unstructured":"B. Courcelle, J. Engelfriet, and G. Rozenberg. Handle-rewriting hypergraph grammars. Journal of Computer and System Sciences, 46:218\u2013270, 1993.","journal-title":"Journal of Computer and System Sciences"},{"key":"53_CR8","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/S0166-218X(99)00184-5","volume":"101","author":"B. Courcelle","year":"2000","unstructured":"B. Courcelle and S. Olariu. Upper bounds to the clique-width of graphs. Discrete Applied Mathematics, 101:77\u2013114, 2000.","journal-title":"Discrete Applied Mathematics"},{"key":"53_CR9","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"D. Eppstein. Diameter and treewidth in minor-closed graph families. Algorithmica, 27:275\u2013291, 2000.","journal-title":"Algorithmica"},{"key":"53_CR10","doi-asserted-by":"crossref","unstructured":"H. Gaifman. On local and non-local properties. In Proceedings of the Herbrand Symposium, Logic Colloquium\u2019 81. North Holland, 1982.","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"53_CR11","doi-asserted-by":"crossref","unstructured":"M. Grohe. Local tree-width, excluded minors, and approximation algorithms. Combinatorica. To appear.","DOI":"10.1007\/s00493-003-0037-9"},{"key":"53_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/3-540-44693-1_2","volume-title":"Generalized model-checking problems for first-order logic","author":"M. Grohe","year":"2001","unstructured":"M. Grohe. Generalized model-checking problems for first-order logic. In H. Reichel and A. Ferreira, editors, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, volume 2010 of Lecture Notes in Computer Science, pages 12\u201326. Springer-Verlag, 2001."},{"key":"53_CR13","unstructured":"M. Grohe and Gy. Tur\u00e1n. Learnability and definability in trees and similar structures. Currently available at http:\/\/www.dcs.ed.ac.uk\/home\/grohe\/pub.html ."},{"key":"53_CR14","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1145\/234752.234755","volume":"43","author":"L. Hellerstein","year":"1996","unstructured":"L. Hellerstein, K. Pillaipakkamnatt, V. Raghavan, and D. Wilkins. How many queries are needed to learn? Journal of the ACM, 43:840\u2013862, 1996.","journal-title":"Journal of the ACM"},{"key":"53_CR15","doi-asserted-by":"crossref","unstructured":"W. Hodges. Model Theory. Cambridge University Press, 1993.","DOI":"10.1017\/CBO9780511551574"},{"key":"53_CR16","doi-asserted-by":"crossref","unstructured":"M.J. Kearns and U.V. Vazirani. An Introduction to Computational Learning Theory. MIT Press, 1994.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"issue":"2","key":"53_CR17","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1112\/jlms\/s2-45.2.377","volume":"45","author":"M.C. Laskowski","year":"1992","unstructured":"M.C. Laskowski. Vapnik-Chervonenkis classes of definable sets. Journal of the London Mathematical Society (2), 45:377\u2013384, 1992.","journal-title":"Journal of the London Mathematical Society"},{"key":"53_CR18","first-page":"107","volume":"9","author":"W. Maass","year":"1992","unstructured":"W. Maass and Gy. Tur\u00e1n. Lower bound methods and separation results for on-line learning models. Machine Learning, 9:107\u2013145, 1992.","journal-title":"Machine Learning"},{"key":"53_CR19","unstructured":"W. Maass and Gy. Tur\u00e1n. On learnability and predicate logic. In Proceedings of the Bar-Ilan Symposium on the Foundations of Artificial Intelligence (BISFAI-95), pages 75\u201385, 1995."},{"key":"53_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-62927-0","volume-title":"Foundations of Inductive Logic Programming","author":"S.-H. Nienhuys-Cheng","year":"1997","unstructured":"S.-H. Nienhuys-Cheng and R. deWolf. Foundations of Inductive Logic Programming, volume 1228 of Lecture Notes in Computer Science. Springer-Verlag, 1997."},{"issue":"58","key":"53_CR21","first-page":"217","volume":"57","author":"D.N. Osherson","year":"1991","unstructured":"D.N. Osherson, M. Stob, and S. Weinstein. New directions in automated scientific discovery. Information Sciences, 57-58:217\u2013230, 1991.","journal-title":"Information Sciences"},{"key":"53_CR22","doi-asserted-by":"crossref","first-page":"101","DOI":"10.4064\/fm-100-2-101-107","volume":"100","author":"K.P. Podewski","year":"1978","unstructured":"K.P. Podewski and M. Ziegler. Stable graphs. Fundamenta Mathematicae, 100:101\u2013107, 1978.","journal-title":"Fundamenta Mathematicae"},{"key":"53_CR23","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors II. Algorithmic aspects of tree-width. Journal of Algorithms, 7:309\u2013322, 1986.","journal-title":"Journal of Algorithms"},{"key":"53_CR24","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/0095-8956(86)90030-4","volume":"41","author":"N. Robertson","year":"1986","unstructured":"N. Robertson and P.D. Seymour. Graph minors V. Excluding a planar graph. Journal of Combinatorial Theory, Series B, 41:92\u2013114, 198","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"53_CR25","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N. Sauer","year":"1972","unstructured":"N. Sauer. On the density of families of sets. Jornal of Combinatorial Theory, Series A, 13:145\u2013147, 1972.","journal-title":"Jornal of Combinatorial Theory"},{"key":"53_CR26","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1016\/0003-4843(71)90015-5","volume":"3","author":"S. Shelah","year":"1971","unstructured":"S. Shelah. Stability, the f.c.p. and superstability.Annals of Mathematical Logic, 3:271\u2013362, 1971.","journal-title":"Annals of Mathematical Logic"},{"key":"53_CR27","doi-asserted-by":"crossref","first-page":"241","DOI":"10.2140\/pjm.1972.41.247","volume":"41","author":"S. Shelah","year":"1972","unstructured":"S. Shelah. A combinatorial problem: stability and order for models and theories in infinitary languages. Pacific Journal of Mathematics, 41:241\u2013261, 1972.","journal-title":"Pacific Journal of Mathematics"},{"key":"53_CR28","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/BF01691346","volume":"2","author":"J.W. Thatcher","year":"1968","unstructured":"J.W. Thatcher and J.B. Wright. Generalised finite automata theory with an application to a decision problem of second-order logic. Mathematical Systems Theory, 2:57\u201381, 1968.","journal-title":"Mathematical Systems Theory"},{"key":"53_CR29","doi-asserted-by":"crossref","unstructured":"I. Tsapara and Gy. Tur\u00e1n. Learning atomic formulas with prescribed properties. In Proceedings of the Eleventh Annual Conference on Computational Learning Theory (COLT\u201998), pages 166\u2013174, 1998.","DOI":"10.1145\/279943.279978"},{"key":"53_CR30","doi-asserted-by":"crossref","unstructured":"L. van den Dries. Tame Topology and O-minimal Structures. Cambridge University Press, 1998.","DOI":"10.1017\/CBO9780511525919"},{"key":"53_CR31","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. Vapnik","year":"1971","unstructured":"V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications, 16:264\u2013280, 1971.","journal-title":"Theory of Probability and its Applications"}],"container-title":["Lecture Notes in Computer Science","STACS 2002"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45841-7_53","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T08:55:39Z","timestamp":1737363339000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45841-7_53"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540432838","9783540458418"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/3-540-45841-7_53","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}