{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T13:38:55Z","timestamp":1774964335064,"version":"3.50.1"},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,8,1]],"date-time":"2013-08-01T00:00:00Z","timestamp":1375315200000},"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":[[2013,8]]},"abstract":"\n Let\n D<\/jats:italic>\n denote an infinite alphabet -- a set that consists of infinitely many symbols. A word\n w<\/jats:italic>\n \u2009=\u2009\n a<\/jats:italic>\n 0<\/jats:sub>\n b<\/jats:italic>\n 0<\/jats:sub>\n a<\/jats:italic>\n 1<\/jats:sub>\n b<\/jats:italic>\n 1<\/jats:sub>\n \u2009\u22ef\u2009\n a<\/jats:italic>\n n<\/jats:sub>\n b<\/jats:italic>\n n<\/jats:sub>\n of even length over\n D<\/jats:italic>\n can be viewed as a directed graph\n G<\/jats:italic>\n w<\/jats:sub>\n whose vertices are the symbols that appear in\n w<\/jats:italic>\n , and the edges are (\n a<\/jats:italic>\n 0<\/jats:sub>\n ,\n b<\/jats:italic>\n 0<\/jats:sub>\n ), (\n a<\/jats:italic>\n 1<\/jats:sub>\n ,\n b<\/jats:italic>\n 1<\/jats:sub>\n ), ..., (\n a<\/jats:italic>\n n<\/jats:sub>\n ,\n b<\/jats:italic>\n n<\/jats:sub>\n ). For a positive integer\n m<\/jats:italic>\n , define a language\n R<\/jats:italic>\n m<\/jats:sub>\n such that a word\n w<\/jats:italic>\n \u2009=\u2009\n a<\/jats:italic>\n 0<\/jats:sub>\n b<\/jats:italic>\n 0<\/jats:sub>\n \u2009\u22ef\u2009\n a<\/jats:italic>\n n<\/jats:sub>\n b<\/jats:italic>\n n<\/jats:sub>\n \u2009\u2208\u2009\n R<\/jats:italic>\n m<\/jats:sub>\n if and only if there is a path in the graph\n G<\/jats:italic>\n w<\/jats:sub>\n of length \u2264\u2009\n m<\/jats:italic>\n from the vertex\n a<\/jats:italic>\n 0<\/jats:sub>\n to the vertex\n b<\/jats:italic>\n n<\/jats:sub>\n .\n <\/jats:p>\n \n We establish the following hierarchy theorem for pebble automata over infinite alphabet. For every positive integer\n k<\/jats:italic>\n , (i) there exists a\n k<\/jats:italic>\n -pebble automaton that accepts the language\n R<\/jats:italic>\n 2k\u2009\u2212\u20091<\/jats:sub>\n ; (ii) there is no\n k<\/jats:italic>\n -pebble automaton that accepts the language\n R<\/jats:italic>\n 2k\u2009+\u20091\u2009\u2212\u20092<\/jats:sub>\n . Using this fact, we establish the following main results in this article: (a) a strict hierarchy of the pebble automata languages based on the number of pebbles; (b) the separation of monadic second order logic from the pebble automata languages; (c) the separation of one-way deterministic register automata languages from pebble automata languages.\n <\/jats:p>","DOI":"10.1145\/2499937.2499940","type":"journal-article","created":{"date-parts":[[2013,9,3]],"date-time":"2013-09-03T11:57:11Z","timestamp":1378209431000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Graph Reachability and Pebble Automata over Infinite Alphabets"],"prefix":"10.1145","volume":"14","author":[{"given":"Tony","family":"Tan","sequence":"first","affiliation":[{"name":"Hasselt University and Transnational University of Limburg"}]}],"member":"320","published-online":{"date-parts":[[2013,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274958"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the International Symposium on Foundations of Computation Theory. 88--99","author":"Bj\u00f6rklund H.","unstructured":"Bj\u00f6rklund , H. and Schwentick , T . 2007. On notions of regularity for data languages . In Proceedings of the International Symposium on Foundations of Computation Theory. 88--99 . Bj\u00f6rklund, H. and Schwentick, T. 2007. On notions of regularity for data languages. In Proceedings of the International Symposium on Foundations of Computation Theory. 88--99."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970403"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.48"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00229-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507244.1507246"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2006.08.003"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1995.1100"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00119-3"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)90242-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213010"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1877714.1877716"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1013560.1013562"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00030-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11874683_3"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Tan T. 2009. Determinizing two-way alternating pebble automata over infinite alphabets. Tech rep. Department of Computer Science Technion -- Israel Institute of Technology. http:\/\/www.cs.technion.ac.il\/users\/wwwb\/cgi-bin\/tr-list.cgi\/2009\/CS. Tan T. 2009. Determinizing two-way alternating pebble automata over infinite alphabets. Tech rep. Department of Computer Science Technion -- Israel Institute of Technology. http:\/\/www.cs.technion.ac.il\/users\/wwwb\/cgi-bin\/tr-list.cgi\/2009\/CS.","DOI":"10.1109\/LICS.2009.23"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2010.03.004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90166-3"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499937.2499940","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2499937.2499940","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:34:00Z","timestamp":1750232040000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2499937.2499940"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,8]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,8]]}},"alternative-id":["10.1145\/2499937.2499940"],"URL":"https:\/\/doi.org\/10.1145\/2499937.2499940","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,8]]},"assertion":[{"value":"2011-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-08-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}