{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:20:13Z","timestamp":1759638013809,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-0430994"],"award-info":[{"award-number":["IIS-0430994"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["639.021.508"],"award-info":[{"award-number":["639.021.508"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>We study FO(MTC), first-order logic with monadic transitive closure, a logical formalism in between FO and MSO on trees. We characterize the expressive power of FO(MTC) in terms of nested tree-walking automata. Using the latter, we show that FO(MTC) is strictly less expressive than MSO, solving an open problem. We also present a temporal logic on trees that is expressively complete for FO(MTC), in the form of an extension of the XML document navigation language XPath with two operators: the Kleene star for taking the transitive closure of path expressions, and a subtree relativisation operator, allowing one to restrict attention to a specific subtree while evaluating a subexpression. We show that the expressive power of this XPath dialect equals that of FO(MTC) for Boolean, unary and binary queries. We also investigate the complexity of the automata model as well as the XPath dialect. We show that query evaluation be done in polynomial time (combined complexity), but that emptiness (or, satisfiability) is 2ExpTime-complete.<\/jats:p>","DOI":"10.1145\/1706591.1706598","type":"journal-article","created":{"date-parts":[[2010,3,25]],"date-time":"2010-03-25T12:17:18Z","timestamp":1269519438000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Transitive closure logic, nested tree walking automata, and XPath"],"prefix":"10.1145","volume":"57","author":[{"given":"Balder Ten","family":"Cate","sequence":"first","affiliation":[{"name":"INRIA, ENS-Cachan, Santa Cruz, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Luc","family":"Segoufin","sequence":"additional","affiliation":[{"name":"INRIA, ENS-Cachan, Cedex, France"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,3,29]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.19"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065172"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.10.030"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_9"},{"key":"e_1_2_1_5_1","unstructured":"Bird S. Chen Y. Davidson S. B. Lee H. and Zheng Y. 2005. Extending XPath to support linguistic queries. In PLAN-X. 35--46. Bird S. Chen Y. Davidson S. B. Lee H. and Zheng Y. 2005. Extending XPath to support linguistic queries. In PLAN-X. 35--46."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645427"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_15"},{"key":"e_1_2_1_8_1","first-page":"2","article-title":"Nested pebbles and transitive closure. Logi","volume":"3","author":"Engelfriet J.","year":"2007","unstructured":"Engelfriet , J. , and Hoogeboom , H. J. 2007 . Nested pebbles and transitive closure. Logi . Meth. Comput. Sci. 3 , 2 . Engelfriet, J., and Hoogeboom, H. J. 2007. Nested pebbles and transitive closure. Logi. Meth. Comput. Sci. 3, 2.","journal-title":"Meth. Comput. Sci."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265540"},{"volume-title":"Proceedings of the International Conference on Data Engineering. IEEE Computer Society Press","author":"Fan W.","key":"e_1_2_1_10_1","unstructured":"Fan , W. , Geerts , F. , Jia , X. , and Kementsietsidis , A . 2007. Rewriting regular xpath queries on XML views . In Proceedings of the International Conference on Data Engineering. IEEE Computer Society Press , Los Alamitos, CA, 666--675. Fan, W., Geerts, F., Jia, X., and Kementsietsidis, A. 2007. Rewriting regular xpath queries on XML views. In Proceedings of the International Conference on Data Engineering. IEEE Computer Society Press, Los Alamitos, CA, 666--675."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92687-0_13"},{"volume-title":"Proceedings of the Symposium on Very Large Data Bases. ACM","author":"Gottlob G.","key":"e_1_2_1_12_1","unstructured":"Gottlob , G. , Koch , C. , and Pichler , R . 2002. Efficient algorithms for processing XPath queries . In Proceedings of the Symposium on Very Large Data Bases. ACM , New York, 95--106. Gottlob, G., Koch, C., and Pichler, R. 2002. Efficient algorithms for processing XPath queries. In Proceedings of the Symposium on Very Large Data Bases. ACM, New York, 95--106."},{"key":"e_1_2_1_13_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 10th International Workshop on Computer Science Logic","author":"Gr\u00e4del E.","unstructured":"Gr\u00e4del , E. 1991. On transitive closure logic . In Proceedings of the 10th International Workshop on Computer Science Logic . Lecture Notes in Computer Science , vol. 626 . Springer-Verlag, Berlin , Germany , 149--163. Gr\u00e4del, E. 1991. On transitive closure logic. In Proceedings of the 10th International Workshop on Computer Science Logic. Lecture Notes in Computer Science, vol. 626. Springer-Verlag, Berlin, Germany, 149--163."},{"volume-title":"Proceedings of the Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press","author":"Laroussinie F.","key":"e_1_2_1_14_1","unstructured":"Laroussinie , F. , Markey , N. , and Schnoebelen , P . 2002. Temporal logic with forgettable past . In Proceedings of the Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press , Los Alamitos, CA, 383--392. Laroussinie, F., Markey, N., and Schnoebelen, P. 2002. Temporal logic with forgettable past. In Proceedings of the Annual IEEE Symposium on Logic in Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 383--392."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1111\/j.1755-2567.1966.tb00600.x","article-title":"First-order predicate logic with generalized quantifiers","volume":"32","author":"Lindstr\u00f6m P.","year":"1996","unstructured":"Lindstr\u00f6m , P. 1996 . First-order predicate logic with generalized quantifiers . Theoria 32 , 3, 186 -- 195 . Lindstr\u00f6m, P. 1996. First-order predicate logic with generalized quantifiers. Theoria 32, 3, 186--195.","journal-title":"Theoria"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24741-8_28"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114244.1114247"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1083784.1083792"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00214-4"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/514183.514186"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00013-0"},{"volume-title":"Mathematical Logic and Foundations of Set Theory. North-Holland","author":"Rabin M. O.","key":"e_1_2_1_23_1","unstructured":"Rabin , M. O. 1970. Weakly definable relations and special automata . In Mathematical Logic and Foundations of Set Theory. North-Holland , Amsterdam, The Netherlands , 1--23. Rabin, M. O. 1970. Weakly definable relations and special automata. In Mathematical Logic and Foundations of Set Theory. North-Holland, Amsterdam, The Netherlands, 1--23."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/645729.667843"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142398"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265541"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_10"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1706591.1706598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1706591.1706598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:20Z","timestamp":1750278380000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1706591.1706598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1706591.1706598"],"URL":"https:\/\/doi.org\/10.1145\/1706591.1706598","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2009-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-03-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}