{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T20:41:13Z","timestamp":1648586473592},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2014,12]]},"abstract":"<jats:p> Stateless variants of deterministic one-way multi-head finite automata with pebbles, that is, automata where the heads can drop, sense, and pick up pebbles, are studied. The relation between heads and pebbles is investigated, and a proper double hierarchy concerning these two resources is obtained. Moreover, it is shown that a conversion of an arbitrary automaton to a stateless automaton can always be achieved at the cost of additional heads and\/or pebbles. On the other hand, there are languages where one head cannot be traded for any number of additional pebbles and vice versa. Finally, the emptiness problem and related problems are shown to be undecidable even for the \u2018simplest\u2019 model, namely, for stateless one-way finite automata with two heads and one pebble. <\/jats:p>","DOI":"10.1142\/s0129054114400292","type":"journal-article","created":{"date-parts":[[2015,2,25]],"date-time":"2015-02-25T01:32:14Z","timestamp":1424827934000},"page":"1141-1159","source":"Crossref","is-referenced-by-count":1,"title":["STATELESS ONE-WAY MULTI-HEAD FINITE AUTOMATA WITH PEBBLES"],"prefix":"10.1142","volume":"25","author":[{"given":"MARTIN","family":"KUTRIB","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]},{"given":"ANDREAS","family":"MALCHER","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]},{"given":"MATTHIAS","family":"WENDLANDT","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2015,2,24]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01752387"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90093-9"},{"key":"p_3","first-page":"178","volume":"5635","author":"Ibarra O. H.","year":"2009","journal-title":"LNCS"},{"key":"p_4","first-page":"240","volume":"5583","author":"Frisco P.","year":"2009","journal-title":"LNCS"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.08.024"},{"key":"p_8","first-page":"408","volume":"5609","author":"Ibarra O. H.","year":"2009","journal-title":"LNCS"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.001"},{"key":"p_12","first-page":"214","volume":"7410","author":"Kutrib M.","year":"2012","journal-title":"H.-C. Yen and O. H. Ibarra LNCS"},{"key":"p_13","first-page":"313","volume":"7907","author":"Kutrib M.","year":"2013","journal-title":"M.-P. B\u00e9al and O. Carton LNCS"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-010-0125-4"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007556"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1007\/BF02090769"},{"key":"p_18","first-page":"549","volume":"7","author":"Malcher A.","year":"2002","journal-title":"Lang. Comb."},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1147\/rd.32.0114"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(72)90205-7"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1147\/rd.105.0388"},{"key":"p_23","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(76)90426-5"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108006261"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1145\/322063.322076"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054114400292","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T11:14:19Z","timestamp":1565176459000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054114400292"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12]]},"references-count":19,"journal-issue":{"issue":"08","published-online":{"date-parts":[[2015,2,24]]},"published-print":{"date-parts":[[2014,12]]}},"alternative-id":["10.1142\/S0129054114400292"],"URL":"https:\/\/doi.org\/10.1142\/s0129054114400292","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12]]}}}