{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:38:04Z","timestamp":1759639084114},"reference-count":9,"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":[[2018,6]]},"abstract":"<jats:p> While (stateless) deterministic ordered restarting automata accept exactly the regular languages, it has been observed that nondeterministic ordered restarting automata (ORWW-automata for short) are more expressive. Here we show that the class of languages accepted by the latter automata is an abstract family of languages that is incomparable to the linear, the context-free, and the growing context-sensitive languages with respect to inclusion, and that the emptiness problem is decidable for these languages. In addition, we give a construction that turns a stateless ORWW-automaton into a nondeterministic finite-state acceptor for the same language. <\/jats:p>","DOI":"10.1142\/s0129054118410101","type":"journal-article","created":{"date-parts":[[2018,6,29]],"date-time":"2018-06-29T07:14:49Z","timestamp":1530256489000},"page":"663-685","source":"Crossref","is-referenced-by-count":4,"title":["Nondeterministic Ordered Restarting Automata"],"prefix":"10.1142","volume":"29","author":[{"given":"Kent","family":"Kwee","sequence":"first","affiliation":[{"name":"Fachbereich Elektrotechnik\/Informatik, Universit\u00e4t Kassel, 34109 Kassel, Germany"}]},{"given":"Friedrich","family":"Otto","sequence":"additional","affiliation":[{"name":"Fachbereich Elektrotechnik\/Informatik, Universit\u00e4t Kassel, 34109 Kassel, Germany"}]}],"member":"219","published-online":{"date-parts":[[2018,6,29]]},"reference":[{"key":"S0129054118410101BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59136-5_3"},{"key":"S0129054118410101BIB002","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00009-1"},{"key":"S0129054118410101BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90062-0"},{"key":"S0129054118410101BIB004","volume-title":"Computers and Intractability. A Guide to the Theory of NP-Completeness","author":"Garey M.","year":"1979"},{"key":"S0129054118410101BIB005","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"S0129054118410101BIB006","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J.","year":"1979"},{"key":"S0129054118410101BIB009","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42284"},{"key":"S0129054118410101BIB011","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.09.003"},{"key":"S0129054118410101BIB012","series-title":"Studies in Computational Intelligence","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/978-3-540-33461-3_11","volume-title":"Recent Advances in Formal Languages and Applications","volume":"25","author":"Otto F.","year":"2006"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054118410101","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T19:44:22Z","timestamp":1565120662000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054118410101"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6]]},"references-count":9,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2018,6,29]]},"published-print":{"date-parts":[[2018,6]]}},"alternative-id":["10.1142\/S0129054118410101"],"URL":"https:\/\/doi.org\/10.1142\/s0129054118410101","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6]]}}}