{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:24:08Z","timestamp":1770963848259,"version":"3.50.1"},"reference-count":17,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01","funder":[{"DOI":"10.13039\/501100006769","name":"Russian Science Foundation","doi-asserted-by":"publisher","award":["23-11-00133"],"award-info":[{"award-number":["23-11-00133"]}],"id":[{"id":"10.13039\/501100006769","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2026,1]]},"abstract":"<jats:p>Deterministic graph-walking automata equipped with finitely many \u201cdrop-once\u201d pebbles are investigated: these automata explore a graph by following its edges using finitely many states, and they can also leave pebbles at some nodes, but cannot lift these pebbles anymore. It is proved that for every such automaton there is a graph-walking automaton without pebbles that recognizes the same set of graphs. To be precise, for an automaton with m drop-once pebbles and n states, operating on graphs with k labels of edge end-points, an automaton without pebbles with [Formula: see text] states accepting the same set of graphs is constructed. The results apply to two-way finite automata (with [Formula: see text]) and to tree-walking automata as special cases.<\/jats:p>","DOI":"10.1142\/s0129054125410023","type":"journal-article","created":{"date-parts":[[2025,1,26]],"date-time":"2025-01-26T23:28:20Z","timestamp":1737934100000},"page":"23-46","source":"Crossref","is-referenced-by-count":0,"title":["A Time to Cast Away Stones: On a Family of Pebble Automata"],"prefix":"10.1142","volume":"37","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1249-5173","authenticated-orcid":false,"given":"Olga","family":"Martynova","sequence":"first","affiliation":[{"name":"Department of Mathematics and Computer Science, St. Petersburg State University, 14th Line V. O., 29, Saint Petersburg 199178, Russia"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1615-2725","authenticated-orcid":false,"given":"Alexander","family":"Okhotin","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, St. Petersburg State University, 14th Line V. O., 29, Saint Petersburg 199178, Russia"}]}],"member":"219","published-online":{"date-parts":[[2025,1,25]]},"reference":[{"key":"S0129054125410023BIB001","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.1967.6"},{"key":"S0129054125410023BIB002","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1978.30"},{"key":"S0129054125410023BIB003","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_15"},{"key":"S0129054125410023BIB004","doi-asserted-by":"publisher","DOI":"10.1002\/mana.19780860120"},{"key":"S0129054125410023BIB005","doi-asserted-by":"publisher","DOI":"10.1145\/3356883"},{"key":"S0129054125410023BIB006","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60207-8_7"},{"key":"S0129054125410023BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.07.014"},{"key":"S0129054125410023BIB008","doi-asserted-by":"publisher","DOI":"10.1051\/ita\/2011001"},{"key":"S0129054125410023BIB009","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00119-3"},{"key":"S0129054125410023BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90208-Y"},{"key":"S0129054125410023BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104631"},{"key":"S0129054125410023BIB012","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105127"},{"key":"S0129054125410023BIB013","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2023.105011"},{"key":"S0129054125410023BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.09.017"},{"key":"S0129054125410023BIB015","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288647"},{"key":"S0129054125410023BIB016","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(74)90017-3"},{"key":"S0129054125410023BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(80)90053-5"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054125410023","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:37:17Z","timestamp":1770961037000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054125410023"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,25]]},"references-count":17,"journal-issue":{"issue":"01","published-print":{"date-parts":[[2026,1]]}},"alternative-id":["10.1142\/S0129054125410023"],"URL":"https:\/\/doi.org\/10.1142\/s0129054125410023","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,1,25]]}}}