{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T14:40:17Z","timestamp":1691592017484},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2015,4,17]],"date-time":"2015-04-17T00:00:00Z","timestamp":1429228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2015,11]]},"DOI":"10.1007\/s00224-015-9623-7","type":"journal-article","created":{"date-parts":[[2015,4,16]],"date-time":"2015-04-16T06:33:46Z","timestamp":1429166026000},"page":"967-1007","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Deciding Twig-definability of Node Selecting Tree Automata"],"prefix":"10.1007","volume":"57","author":[{"given":"Timos","family":"Antonopoulos","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dag","family":"Hovland","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wim","family":"Martens","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frank","family":"Neven","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,4,17]]},"reference":[{"issue":"1\u20132","key":"9623_CR1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/S0304-3975(00)00294-2","volume":"267","author":"J Albert","year":"2001","unstructured":"Albert, J., Giammerresi, D., Wood, D.: Normal form algorithms for extended context free grammars. Theor. Comput. Sci. 267(1\u20132), 35\u201347 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"9623_CR2","doi-asserted-by":"crossref","unstructured":"Antonopoulos, T., Hovland, D., Martens, W., Neven, F.: Deciding twig-definability of node selecting tree automata. In: Deutsch, A. (ed.) ICDT, pp 61\u201373. ACM (2012)","DOI":"10.1145\/2274576.2274584"},{"key":"9623_CR3","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Fan, W., Geerts, F.: XPath satisfiability in the presence of DTDs. J. ACM 55(2) (2008)","DOI":"10.1145\/1346330.1346333"},{"issue":"1","key":"9623_CR4","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/j.tcs.2004.10.030","volume":"336","author":"M Benedikt","year":"2005","unstructured":"Benedikt, M., Fan, W., Kuper, G.M.: Structural properties of XPath fragments. Theor. Comput. Sci. 336(1), 3\u201331 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9623_CR5","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Koch, C.: XPath leashed. ACM Comput. Surv. 41(1) (2008)","DOI":"10.1145\/1456650.1456653"},{"key":"9623_CR6","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Segoufin, L.: Regular tree languages definable in FO and in FO m o d . ACM Trans. Comput. Log. 11(1) (2009)","DOI":"10.1145\/1614431.1614435"},{"key":"9623_CR7","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M.: Tree-walking automata. In: International Conference on Language and Automata Theory and Applications (LATA), pp 1\u20132 (2008)","DOI":"10.1007\/978-3-540-88282-4_1"},{"key":"9623_CR8","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Muscholl, A., Schwentick, T., Segoufin, L.: Two-variable logic on data trees and XML reasoning. J. ACM 56(3) (2009)","DOI":"10.1145\/1516512.1516515"},{"key":"9623_CR9","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Parys, P.: XPath evaluation in linear time. J. ACM. To appear","DOI":"10.1145\/1376916.1376951"},{"key":"9623_CR10","doi-asserted-by":"crossref","unstructured":"Boja\u0144czyk, M., Segoufin, L.: Tree languages defined in first-order logic with one quantifier alternation. Logical Methods Comput. Sci. 6(4) (2010)","DOI":"10.2168\/LMCS-6(4:1)2010"},{"issue":"2\u20133","key":"9623_CR11","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/j.tcs.2006.01.018","volume":"358","author":"M Boja\u0144czyk","year":"2006","unstructured":"Boja\u0144czyk, M., Walukiewicz, I.: Characterizing EF and EX tree logics. Theor. Comput. Sci. 358(2\u20133), 255\u2013272 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9623_CR12","doi-asserted-by":"crossref","unstructured":"Calvanese, D., Giacomo, G.D., Lenzerini, M., Vardi, M.Y.: Node selection query languages for trees. In: AAAI Conference on Artificial Intelligence (AAAI) (2010)","DOI":"10.1609\/aaai.v24i1.7598"},{"key":"9623_CR13","doi-asserted-by":"crossref","unstructured":"Carme, J., Niehren, J., Tommasi, M.: Querying unranked trees with stepwise tree automata. In: International Conference on Rewriting Techniques and Applications (RTA), pp. 105\u2013118 (2004)","DOI":"10.1007\/978-3-540-25979-4_8"},{"key":"9623_CR14","unstructured":"Comon, H., Dauchet, M., Gilleron, R., Jacquemard, F., Lugiez, D., L\u00f6ding, C., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications. Available on http:\/\/tata.gforge.inria.fr\/ (2007)"},{"issue":"3","key":"9623_CR15","doi-asserted-by":"crossref","first-page":"272","DOI":"10.1006\/jcss.1998.1564","volume":"57","author":"MP Consens","year":"1998","unstructured":"Consens, M.P., Milo, T.: Algebras for querying text regions. Expressive power and optimization. J. Comput. Syst. Sci. 57(3), 272\u2013288 (1998)","journal-title":"J. Comput. Syst. Sci."},{"key":"9623_CR16","unstructured":"Frick, M., Grohe, M., Koch, C.: Query evaluation on compressed trees (extended abstract). In: IEEE Symposium on Logic in Computer Science (LICS), pp. 188 (2003)"},{"key":"9623_CR17","doi-asserted-by":"crossref","unstructured":"Gelade, W., Idziaszek, T., Martens, W., Neven, F.: Simplifying XML Schema: single-type approximations of regular tree languages. In: ACM Symposium on Principles of Database Systems (PODS), pp. 251\u2013260 (2010)","DOI":"10.1145\/1807085.1807118"},{"key":"9623_CR18","doi-asserted-by":"crossref","unstructured":"Goris, E., Marx, M.: Looping caterpillars. In: Annual IEEE Symposium on Logic in Computer Science (LICS), pp. 51\u201360 (2005)","DOI":"10.1109\/LICS.2005.24"},{"issue":"1","key":"9623_CR19","doi-asserted-by":"crossref","first-page":"74","DOI":"10.1145\/962446.962450","volume":"51","author":"G Gottlob","year":"2004","unstructured":"Gottlob, G., Koch, C.: Monadic datalog and the expressive power of languages for web information extraction. J. ACM 51(1), 74\u2013113 (2004)","journal-title":"J. ACM"},{"issue":"2","key":"9623_CR20","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1145\/1071610.1071614","volume":"30","author":"G Gottlob","year":"2005","unstructured":"Gottlob, G., Koch, C., Pichler, R.: Efficient algorithms for processing XPath queries. ACM Trans. Database Syst. 30(2), 444\u2013491 (2005)","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"9623_CR21","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1145\/1059513.1059520","volume":"52","author":"G Gottlob","year":"2005","unstructured":"Gottlob, G., Koch, C., Pichler, R., Segoufin, L.: The complexity of xpath query evaluation and XML typing. J. ACM 52(2), 284\u2013335 (2005)","journal-title":"J. ACM"},{"issue":"4","key":"9623_CR22","doi-asserted-by":"crossref","first-page":"1486","DOI":"10.1137\/080743457","volume":"39","author":"W Martens","year":"2009","unstructured":"Martens, W., Neven, F., Schwentick, T.: Complexity of decision problems for XML schemas and chain regular expressions. SIAM J. Comput. 39(4), 1486\u20131530 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9623_CR23","doi-asserted-by":"crossref","first-page":"770","DOI":"10.1145\/1166074.1166076","volume":"31","author":"W Martens","year":"2006","unstructured":"Martens, W., Neven, F., Schwentick, T., Bex, G.J.: Expressiveness and complexity of XML Schema. ACM Trans. Database Syst. 31(3), 770\u2013813 (2006)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"9623_CR24","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/1114244.1114247","volume":"30","author":"M Marx","year":"2005","unstructured":"Marx, M.: Conditional XPath. ACM Trans. Database Syst. 30(4), 929\u2013959 (2005)","journal-title":"ACM Trans. Database Syst."},{"issue":"1","key":"9623_CR25","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1145\/962446.962448","volume":"51","author":"G Miklau","year":"2004","unstructured":"Miklau, G., Suciu, D.: Containment and equivalence for a fragment of XPath. J. ACM 51(1), 2\u201345 (2004)","journal-title":"J. ACM"},{"key":"9623_CR26","volume-title":"Design and Analysis of Query Languages for Structured Documents","author":"F Neven","year":"1999","unstructured":"Neven, F.: Design and Analysis of Query Languages for Structured Documents. PhD thesis, Limburgs Universitair Centrum (1999)"},{"issue":"3","key":"9623_CR27","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1145\/601858.601869","volume":"31","author":"F Neven","year":"2002","unstructured":"Neven, F.: Automata theory for XML researchers. SIGMOD Record 31(3), 39\u201346 (2002)","journal-title":"SIGMOD Record"},{"issue":"2","key":"9623_CR28","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.jcss.2004.10.008","volume":"70","author":"F Neven","year":"2005","unstructured":"Neven, F.: Attribute grammars for unranked trees as a query language for structured documents. J. Comput. Syst. Sci. 70(2), 221\u2013257 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"9623_CR29","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1145\/505241.505245","volume":"49","author":"F Neven","year":"2002","unstructured":"Neven, F., den Bussche, J.V.: Expressiveness of structured document query languages based on attribute grammars. J. ACM 49(1), 56\u2013100 (2002)","journal-title":"J. ACM"},{"key":"9623_CR30","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: Expressive and efficient pattern languages for tree-structured data. In: ACM Symposium on Principles of Database Systems (PODS), pp. 145\u2013156 (2000)","DOI":"10.1145\/335168.335217"},{"issue":"1-2","key":"9623_CR31","doi-asserted-by":"crossref","first-page":"633","DOI":"10.1016\/S0304-3975(01)00301-2","volume":"275","author":"F Neven","year":"2002","unstructured":"Neven, F., Schwentick, T.: Query automata over finite trees. Theor. Comput. Sci. 275(1-2), 633\u2013674 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9623_CR32","doi-asserted-by":"crossref","unstructured":"Neven, F., Schwentick, T.: On the complexity of XPath containment in the presence of disjunction, DTDs, and variables. Logical Methods Comput. Sci. 2(3) (2006)","DOI":"10.2168\/LMCS-2(3:1)2006"},{"key":"9623_CR33","doi-asserted-by":"crossref","unstructured":"Place, T., Segoufin, L.: Deciding definability in FO2(<) (or XPath) on trees. In: Annual IEEE Symposium on Logic in Computer Science (LICS), pp. 253\u2013262 (2010)","DOI":"10.1109\/LICS.2010.17"},{"issue":"1","key":"9623_CR34","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1145\/974121.974140","volume":"33","author":"T Schwentick","year":"2004","unstructured":"Schwentick, T.: XPath query containment. SIGMOD Record 33(1), 101\u2013109 (2004)","journal-title":"SIGMOD Record"},{"issue":"3","key":"9623_CR35","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1137\/0219027","volume":"19","author":"H Seidl","year":"1990","unstructured":"Seidl, H.: Deciding equivalence of finite tree automata. SIAM J. Comput. 19 (3), 424\u2013437 (1990)","journal-title":"SIAM J. Comput."},{"key":"9623_CR36","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Lutz, C.: The complexity of query containment in expressive fragments of XPath 2.0. J. ACM 56(6) (2009)","DOI":"10.1145\/1568318.1568321"},{"key":"9623_CR37","doi-asserted-by":"crossref","unstructured":"ten Cate, B., Segoufin, L.: Transitive closure logic, nested tree walking automata, and XPath. J. ACM 57(3) (2010)","DOI":"10.1145\/1706591.1706598"},{"key":"9623_CR38","doi-asserted-by":"crossref","unstructured":"Thomas, W.: Languages, automata, and logic. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, volume 3, chapter 7, Springer (1997)","DOI":"10.1007\/978-3-642-59126-6_7"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9623-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-015-9623-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-015-9623-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T14:02:16Z","timestamp":1691589736000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-015-9623-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4,17]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,11]]}},"alternative-id":["9623"],"URL":"https:\/\/doi.org\/10.1007\/s00224-015-9623-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,4,17]]}}}