{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T19:21:28Z","timestamp":1649013688681},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,4,10]],"date-time":"2013-04-10T00:00:00Z","timestamp":1365552000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2015,4]]},"DOI":"10.1007\/s10878-013-9609-9","type":"journal-article","created":{"date-parts":[[2013,4,9]],"date-time":"2013-04-09T03:53:21Z","timestamp":1365479601000},"page":"670-684","source":"Crossref","is-referenced-by-count":0,"title":["On the hardness of learning queries from tree structured data"],"prefix":"10.1007","volume":"29","author":[{"given":"Xianmin","family":"Liu","sequence":"first","affiliation":[]},{"given":"Jianzhong","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,4,10]]},"reference":[{"key":"9609_CR1","volume-title":"Data on the web: from relations to semistructured data and xml","author":"S Abiteboul","year":"2000","unstructured":"Abiteboul S, Buneman P, Suciu D (2000) Data on the web: from relations to semistructured data and xml. Morgan Kaufmann, San Francisco"},{"key":"9609_CR2","doi-asserted-by":"crossref","unstructured":"Amer-Yahia S, Cho S, Lakshmanan LVS, Srivastava D (2002) Tree pattern query minimization. VLDB J 11(4):315\u2013331","DOI":"10.1007\/s00778-002-0076-7"},{"issue":"2","key":"9609_CR3","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0019-9958(80)90285-5","volume":"45","author":"D Angluin","year":"1980","unstructured":"Angluin D (1980) Inductive inference of formal languages from positive data. Inf Control 45(2):117\u2013135","journal-title":"Inf Control"},{"key":"9609_CR4","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 (1987) Learning regular sets from queries and counterexamples. Inf Comput 75:87\u2013106","journal-title":"Inf Comput"},{"issue":"2","key":"9609_CR5","first-page":"121","volume":"5","author":"D Angluin","year":"1990","unstructured":"Angluin D (1990) Negative results for equivalence queries. Mach Learn 5(2):121\u2013150","journal-title":"Mach Learn"},{"issue":"2","key":"9609_CR6","first-page":"11:1","volume":"35","author":"GJ Bex","year":"2010","unstructured":"Bex GJ, Neven F, Schwentick T, Vansummeren S (2010) Inference of concise regular expressions and dtds. ACM Trans Database Syst (TODS) 35(2):11:1\u201311:47","journal-title":"ACM Trans Database Syst (TODS)"},{"key":"9609_CR7","unstructured":"Boag S, Chamberlin D, Fernandez M, Florescu D, Robie J, Simeon J, Stefanescu M (2002) Xquery 1.0: an xml query language, http:\/\/www.w3.org\/TR\/xquery"},{"key":"9609_CR8","doi-asserted-by":"crossref","unstructured":"Carme J, Ceresna M, Goebel M (2006) Query-based learning of xpath expressions. In: ICGI, pp 342\u2013343","DOI":"10.1007\/11872436_29"},{"issue":"1","key":"9609_CR9","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s10994-006-9613-8","volume":"66","author":"J Carme","year":"2007","unstructured":"Carme J, Gilleron R, Lemay A, Niehren J (2007) Interactive learning of node selecting tree transducer. Mach Learn 66(1):33\u201367","journal-title":"Mach Learn"},{"key":"9609_CR10","doi-asserted-by":"crossref","unstructured":"Deutch A, Fernandez M, Florescu D, Levy A, Suciu D (1999) A query language for xml. In: Proceedings of WWW","DOI":"10.1016\/S1389-1286(99)00020-1"},{"key":"9609_CR11","unstructured":"Garey MR, Johnson DS (1990) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman & Co., New York"},{"key":"9609_CR12","doi-asserted-by":"crossref","unstructured":"Gold EM (1967) Language identification in the limit. Inf Control 10(5):447\u2013474","DOI":"10.1016\/S0019-9958(67)91165-5"},{"key":"9609_CR13","unstructured":"Gonzalez G, Tari L, Gitter A, Leaman R, Nikkila S, Wendt R, Zeigler A, Baral C (2007) Integrating knowledge from biomedical literature: Normalization and evidence statements for interactions. In: Proceedings of the second bioCreative challenge evaluation workshop, pp 227\u2013236"},{"key":"9609_CR14","doi-asserted-by":"crossref","unstructured":"Higuera Cdl (1997) Characteristic sets for polynomial grammatical inference. Machine Learn 27(2):125\u2013138","DOI":"10.1023\/A:1007353007695"},{"key":"9609_CR15","doi-asserted-by":"crossref","unstructured":"Jagadish HV, Milo T, Srivastava D, Vista D (1999) Querying network directories. In: SIGMOD, pp 133\u2013144","DOI":"10.1145\/304182.304194"},{"key":"9609_CR16","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1089\/10665270252935511","volume":"9","author":"T Jiang","year":"2002","unstructured":"Jiang T, Lin G, Ma B, Zhang K (2002) A general edit distance between rna structures. J Comput Biol 9:371\u2013388","journal-title":"J Comput Biol"},{"key":"9609_CR17","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"MJ Kearns","year":"1994","unstructured":"Kearns MJ, Vazirani UV (1994) An introduction to computational learning theory. MIT Press, Cambridge"},{"key":"9609_CR18","doi-asserted-by":"crossref","unstructured":"Lemay A, Niehren J, Gilleron R (2006) Learning n-ary node selecting tree transducers from completely annotated examples. In: ICGI, pp 253\u2013267","DOI":"10.1007\/11872436_21"},{"issue":"3","key":"9609_CR19","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/BF03037530","volume":"18","author":"S Miyano","year":"2000","unstructured":"Miyano S, Shinohara A, Shinohara T (2000) Polynomial-time learning of elementary formal systems. New Gen Comput 18(3):217\u2013242","journal-title":"New Gen Comput"},{"key":"9609_CR20","unstructured":"Sarma AD, Parameswaran A, Garcia-Molina H, Widom J (2010) Synthesizing view definitions from data. In: ICDT"},{"key":"9609_CR21","doi-asserted-by":"crossref","unstructured":"Staworko S, Wieczorek P (2012) Learning twig and path queries. In: ICDT","DOI":"10.1145\/2274576.2274592"},{"key":"9609_CR22","doi-asserted-by":"crossref","unstructured":"Weis M, Naumann F (2005) Dogmatix tracks down duplicates in xml. In: SIGMOD","DOI":"10.1145\/1066157.1066207"},{"key":"9609_CR23","doi-asserted-by":"crossref","unstructured":"Zuckerman D (2006) Linear degree extractors and the inapproximability of max clique and chromatic number. In: STOC","DOI":"10.1145\/1132516.1132612"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9609-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-013-9609-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-013-9609-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T04:54:26Z","timestamp":1562907266000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-013-9609-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4,10]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4]]}},"alternative-id":["9609"],"URL":"https:\/\/doi.org\/10.1007\/s10878-013-9609-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,10]]}}}