{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:09Z","timestamp":1759639089484,"version":"3.40.5"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319155784"},{"type":"electronic","value":"9783319155791"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-15579-1_58","type":"book-chapter","created":{"date-parts":[[2015,2,23]],"date-time":"2015-02-23T08:36:13Z","timestamp":1424680573000},"page":"739-751","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Sublinear DTD Validity"],"prefix":"10.1007","author":[{"given":"Antoine","family":"Ndione","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aur\u00e9lien","family":"Lemay","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Niehren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"58_CR1","doi-asserted-by":"crossref","unstructured":"Akutsu, T.: A relation between edit distance for ordered trees and edit distance for Euler strings. Inf. Process. Lett., 105\u2013109 (2006)","DOI":"10.1016\/j.ipl.2006.06.002"},{"key":"58_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular Languages are Testable with a Constant Number of Queries. SIAM J. Comput., 1842\u20131862 (2000)","DOI":"10.1137\/S0097539700366528"},{"key":"58_CR3","doi-asserted-by":"crossref","unstructured":"Alur, R., Madhusudan, P.: Adding nesting structure to words. Journal of the ACM, 1\u201343 (2009)","DOI":"10.1145\/1516512.1516518"},{"key":"58_CR4","doi-asserted-by":"crossref","unstructured":"Br\u00fcggemann-Klein, A.: Regular Expressions to Finite Automata. Theoretical Computer Science, 197\u2013213 (1993)","DOI":"10.1016\/0304-3975(93)90287-4"},{"key":"58_CR5","doi-asserted-by":"crossref","unstructured":"Chockler, H., Kupferman, O.: w-Regular languages are testable with a constant number of queries. Theor. Comput. Sci., 71\u201392 (2004)","DOI":"10.1016\/j.tcs.2004.08.004"},{"key":"58_CR6","unstructured":"Comon, H., Dauchet, M., Gilleron, R., L\u00f6ding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007)"},{"key":"58_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, E., Magniez, F., de Rougemont, M.: Approximate satisfiability and equivalence. In: LICS, pp. 421\u2013430 (2006)","DOI":"10.1109\/LICS.2006.12"},{"key":"58_CR8","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorial property testing (a survey). In: Randomization Methods in Algorithm Design, pp. 45\u201360 (1998)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"58_CR9","doi-asserted-by":"crossref","unstructured":"Green, T.J., Gupta, A., Miklau, G., Onizuka, M., Suciu, D.: Processing XML streams with deterministic automata and stream indexes. ACM Trans. Database Syst., 752\u2013788 (2004)","DOI":"10.1145\/1042046.1042051"},{"key":"58_CR10","doi-asserted-by":"crossref","unstructured":"Hagenah, C., Muscholl, A.: Computing epsilon-free nfa from regular expressions in $$O(n log^2(n))$$ time. ITA, 257\u2013278 (2000)","DOI":"10.1051\/ita:2000116"},{"key":"58_CR11","doi-asserted-by":"crossref","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML schema. ACM Transactions of Database Systems, 770\u2013813 (2006)","DOI":"10.1145\/1166074.1166076"},{"key":"58_CR12","doi-asserted-by":"crossref","unstructured":"Ndione, A., Lemay, A., Niehren, J.: Approximate membership for regular languages modulo the edit distance. Theor. Comput. Sci., 37\u201349 (2013)","DOI":"10.1016\/j.tcs.2013.03.004"},{"key":"58_CR13","doi-asserted-by":"crossref","unstructured":"Newman, I., Sohler, C.: Every property of hyperfinite graphs is testable. In: STOC, pp. 675\u2013684 (2011)","DOI":"10.1145\/1993636.1993726"},{"key":"58_CR14","doi-asserted-by":"crossref","unstructured":"Pawlik, M., Augsten, N.: RTED: A Robust Algorithm for the Tree Edit Distance. PVLDB, 334\u2013345 (2011)","DOI":"10.14778\/2095686.2095692"},{"key":"58_CR15","doi-asserted-by":"crossref","unstructured":"Ron, D.: Property Testing: A Learning Theory Perspective. Foundations and Trends in Machine Learning, 307\u2013402 (2008)","DOI":"10.1561\/2200000004"},{"key":"58_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"432","DOI":"10.1007\/11672142_35","volume-title":"STACS 2006","author":"G Schnitger","year":"2006","unstructured":"Schnitger, G.: Regular expressions and NFAs without $$\\varepsilon $$-transitions. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 432\u2013443. Springer, Heidelberg (2006)"},{"key":"58_CR17","doi-asserted-by":"crossref","unstructured":"Selkow, S.M.: The Tree-to-Tree Editing Problem. Inf. Process. Lett., 184\u2013186 (1977)","DOI":"10.1016\/0020-0190(77)90064-3"},{"key":"58_CR18","doi-asserted-by":"crossref","unstructured":"Zhang, K., Shasha, D.: Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. SIAM J. Comput., 1245\u20131262 (1989)","DOI":"10.1137\/0218082"}],"container-title":["Lecture Notes in Computer Science","Language and Automata Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-15579-1_58","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,19]],"date-time":"2025-05-19T21:57:16Z","timestamp":1747691836000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-15579-1_58"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319155784","9783319155791"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-15579-1_58","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"24 February 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}