{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,20]],"date-time":"2026-09-20T04:10:49Z","timestamp":1789877449804,"version":"4.0.1"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2011,5,1]],"date-time":"2011-05-01T00:00:00Z","timestamp":1304208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2011,5]]},"abstract":"<jats:p>A data tree is an unranked ordered tree whose every node is labeled by a letter from a finite alphabet and an element (\u201cdatum\u201d) from an infinite set, where the latter can only be compared for equality. The article considers alternating automata on data trees that can move downward and rightward, and have one register for storing data. The main results are that nonemptiness over finite data trees is decidable but not primitive recursive, and that nonemptiness of safety automata is decidable but not elementary. The proofs use nondeterministic tree automata with faulty counters. Allowing upward moves, leftward moves, or two registers, each causes undecidability. As corollaries, decidability is obtained for two data-sensitive fragments of the XPath query language.<\/jats:p>","DOI":"10.1145\/1929954.1929956","type":"journal-article","created":{"date-parts":[[2011,5,17]],"date-time":"2011-05-17T12:59:03Z","timestamp":1305637143000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["Alternating automata on data trees and XPath satisfiability"],"prefix":"10.1145","volume":"12","author":[{"given":"Marcin","family":"Jurdzi\u0144ski","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ranko","family":"Lazi\u0107","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,5,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01782772"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346333"},{"key":"e_1_2_1_3_1","volume-title":"34th International Colloquium on Automata, Language and Programming (ICALP). Lecture Notes in Computer Science","volume":"4596","author":"Bj\u00f6rklund H.","unstructured":"Bj\u00f6rklund , H. and Boja\u0144czyk , M . 2007. Bounded depth data trees. In Proceeding of the 34th International Colloquium on Automata, Language and Programming (ICALP). Lecture Notes in Computer Science , vol. 4596 . Springer, 862--874. Bj\u00f6rklund, H. and Boja\u0144czyk, M. 2007. Bounded depth data trees. In Proceeding of the 34th International Colloquium on Automata, Language and Programming (ICALP). Lecture Notes in Computer Science, vol. 4596. Springer, 862--874."},{"key":"e_1_2_1_4_1","volume-title":"In Proceeding of the 16th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science","volume":"4639","author":"Bj\u00f6rklund H.","unstructured":"Bj\u00f6rklund , H. and Schwentick , T . 2007. On notions of regularity for data languages . In In Proceeding of the 16th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science , vol. 4639 . Springer, 88--99. Bj\u00f6rklund, H. and Schwentick, T. 2007. On notions of regularity for data languages. In In Proceeding of the 16th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 4639. Springer, 88--99."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516512.1516515"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2006.51"},{"key":"e_1_2_1_7_1","unstructured":"Bray T. Paoli J. and Sperberg-McQueen C. 1998. Extensible markup language (XML) 1.0. W3C Recommendation.  Bray T. Paoli J. and Sperberg-McQueen C. 1998. Extensible markup language (XML) 1.0. W3C Recommendation."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90069-9"},{"key":"e_1_2_1_9_1","unstructured":"Clark J. and DeRose S. 1999. XML path language (XPath). W3C Recommendation.  Clark J. and DeRose S. 1999. XML path language (XPath). W3C Recommendation."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1018438.1021843"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559795.1559827"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00102-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/11601524_8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIME.2006.11"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.11"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"e_1_2_1_20_1","volume-title":"Lecture Notes in Computer Science","volume":"4800","author":"Kaminski M.","unstructured":"Kaminski , M. and Tan , T . 2008. Tree automata over infinite alphabets. In Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occassion of His 85th Birthday . Lecture Notes in Computer Science , vol. 4800 . Springer, 386--423. Kaminski, M. and Tan, T. 2008. Tree automata over infinite alphabets. In Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occassion of His 85th Birthday. Lecture Notes in Computer Science, vol. 4800. Springer, 386--423."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11944836_35"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the IFIP International Conference on Theoretical Computer Science (IFIPTCS). Lecture Notes in Computer Science","volume":"1878","author":"L\u00f6ding C.","unstructured":"L\u00f6ding , C. and Thomas , W . 2000. Alternating automata and logics over infinite words . In Proceedings of the IFIP International Conference on Theoretical Computer Science (IFIPTCS). Lecture Notes in Computer Science , vol. 1878 . Springer, 521--535. L\u00f6ding, C. and Thomas, W. 2000. Alternating automata and logics over infinite words. In Proceedings of the IFIP International Conference on Theoretical Computer Science (IFIPTCS). Lecture Notes in Computer Science, vol. 1878. Springer, 521--535."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 13th International Colloquinm on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science","volume":"226","author":"Muller D. E.","unstructured":"Muller , D. E. , Saoudi , A. , and Schupp , P. E . 1986. Alternating automata, the weak monadic theory of the tree, and its complexity . In Proceedings of the 13th International Colloquinm on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science , vol. 226 . Springer, 275--283. Muller, D. E., Saoudi, A., and Schupp, P. E. 1986. Alternating automata, the weak monadic theory of the tree, and its complexity. In Proceedings of the 13th International Colloquinm on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 226. Springer, 275--283."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013560.1013562"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/967900.968032"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00105-X"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_3"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929954.1929956","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1929954.1929956","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:52:38Z","timestamp":1750243958000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929954.1929956"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5]]},"references-count":26,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,5]]}},"alternative-id":["10.1145\/1929954.1929956"],"URL":"https:\/\/doi.org\/10.1145\/1929954.1929956","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5]]},"assertion":[{"value":"2008-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-05-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}