{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,31]],"date-time":"2022-03-31T09:48:15Z","timestamp":1648720095425},"reference-count":18,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p> The restarting automaton was inspired by the technique of \u2018analysis by reduction\u2019 from linguistics. A restarting automaton processes a given input word through a sequence of cycles. In each cycle the current word on the tape is scanned from left to right and a single local simplification (a rewrite) is executed. One of the essential parameters of a restarting automaton is the size of its read\/write window. Here we study the impact of the window size on the descriptional complexity of several types of deterministic and nondeterministic restarting automata. For all k \u2265 4, we show that the savings in the economy of descriptions of restarting automata that can only delete symbols but not rewrite them (that is, the so-called R- and RR-automata) cannot be bounded by any recursive function, when changing from window size k to window size k + 1. This holds for deterministic as well as for nondeterministic automata, and for k \u2265 5, it even holds for the stateless variants of these automata. However, the trade-off between window sizes two and one is recursive for deterministic devices. In addition, a polynomial upper bound is given for the trade-off between RRWW-automata with window sizes k + 1 and k for all k \u2265 2. <\/jats:p>","DOI":"10.1142\/s0129054113400212","type":"journal-article","created":{"date-parts":[[2013,12,27]],"date-time":"2013-12-27T08:17:54Z","timestamp":1388132274000},"page":"831-846","source":"Crossref","is-referenced-by-count":2,"title":["ON THE DESCRIPTIONAL COMPLEXITY OF THE WINDOW SIZE FOR DELETING RESTARTING AUTOMATA"],"prefix":"10.1142","volume":"24","author":[{"given":"MARTIN","family":"KUTRIB","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen Arndtstr. 2, 35392 Giessen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"FRIEDRICH","family":"OTTO","sequence":"additional","affiliation":[{"name":"Fachbereich Elektrotechnik\/Informatik, Universit\u00e4t Kassel, 34109 Kassel, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2013,12,27]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90016-6"},{"key":"p_3","first-page":"195","volume":"12","author":"Holzer M.","year":"2007","journal-title":"J. Autom. Lang. Comb."},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60249-6_60"},{"key":"p_5","first-page":"287","volume":"4","author":"Jan\u010dar P.","year":"1999","journal-title":"J. Autom. Lang. Comb."},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003406"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054107005339"},{"key":"p_8","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054110007556"},{"key":"p_9","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-010-0125-4"},{"key":"p_10","first-page":"253","volume":"7381","author":"Kutrib M.","year":"2012","journal-title":"LNCS"},{"key":"p_11","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054108005966"},{"key":"p_12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.03.016"},{"key":"p_14","first-page":"493","volume":"6","author":"Mr\u00e1z F.","year":"2001","journal-title":"J. Autom. Lang. Comb."},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(85)90051-0"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-33461-3_11"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.2307\/2267170"},{"key":"p_20","first-page":"499","volume":"6638","author":"Schluter N.","year":"2011","journal-title":"LNCS"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)90591-8"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1145\/321864.321865"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113400212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:10:46Z","timestamp":1565122246000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400212"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":18,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2013,12,27]]},"published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1142\/S0129054113400212"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400212","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}