{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,1]],"date-time":"2023-02-01T21:12:38Z","timestamp":1675285958343},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p> The simulation of weak restarting automata, i.e., classical restarting automata accepting exactly the regular languages, by finite automata is studied. Some of the trade-offs in the number of states when changing the representation are known. Here we continue the investigation in order to draw an almost complete picture of the descriptional power gained in the additional structural resources of weak restarting automata. In particular, for det-RR(1)-simulations of nondeterministic finite automata we obtain the same tight bounds as for simulations of R(1)-automata, though in some cases the latter class is much more efficient than the former. Moreover, the DFA-simulation of det-RR(1)-automata is considered. The shown bounds are of factorial order and are tight. The constructions are via alternating finite automata to DFAs. So, in addition, an upper bound for the AFA-simulation is obtained. <\/jats:p>","DOI":"10.1142\/s0129054108005966","type":"journal-article","created":{"date-parts":[[2008,8,6]],"date-time":"2008-08-06T10:30:40Z","timestamp":1218018640000},"page":"795-811","source":"Crossref","is-referenced-by-count":2,"title":["OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA"],"prefix":"10.1142","volume":"19","author":[{"given":"MARTIN","family":"KUTRIB","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]},{"given":"JENS","family":"REIMANN","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01371727"},{"key":"rf2","first-page":"114","volume":"21","author":"Chandra A. K.","journal-title":"J. ACM"},{"key":"rf3","first-page":"193","volume":"8","author":"Goldstine J.","journal-title":"J. UCS"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62844-4_8"},{"key":"rf7","first-page":"287","volume":"4","author":"Jan\u010dar P.","journal-title":"J. Autom., Lang. Comb."},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003406"},{"key":"rf10","first-page":"493","volume":"6","author":"Mr\u00e1z F.","journal-title":"J. Autom., Lang. Comb."},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1142\/9789812792464_0009"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1142\/9789812704979_0027"},{"key":"rf14","unstructured":"F.\u00a0Otto, Recent Advances in Formal Languages and Applications, Studies in Computational Intelligence\u00a025 (Springer, 2006)\u00a0pp. 269\u2013303."},{"key":"rf15","first-page":"177","volume":"2","author":"Salomaa K.","journal-title":"J. Autom., Lang. Comb."},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"rf17","first-page":"221","volume":"6","author":"Yu S.","journal-title":"J. Autom., Lang. Comb."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054108005966","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:23:45Z","timestamp":1565191425000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054108005966"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":13,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.1142\/S0129054108005966"],"URL":"https:\/\/doi.org\/10.1142\/s0129054108005966","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}