{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,12]],"date-time":"2024-09-12T05:49:47Z","timestamp":1726120187370},"reference-count":19,"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":[[2020,9]]},"abstract":"<jats:p> We continue our investigation [S. Beier, M. Holzer: Properties of right one-way jumping finite automata. In Proc. 20th DCFS, LNCS, 2018] on (right) one-way jumping finite automata (ROWJFAs), a variant of jumping automata, which is an automaton model for discontinuous information processing. Here we focus on decision problems for ROWJFAs. It turns out that most problems such as, e.g., emptiness, finiteness, universality, the word problem and variants thereof, closure under permutation, etc., are decidable. Moreover, we show that the containment of a language within the strict hierarchy of ROWJFA permutation closed languages induced by the number of accepting states as well as whether permutation closed regular or jumping finite automata languages can be accepted by ROWJFAs is decidable, too. On the other hand, we prove that for (linear) context-free languages the corresponding ROWJFA acceptance problem becomes undecidable. Moreover, we discuss also some complexity results for the considered decision problems. <\/jats:p>","DOI":"10.1142\/s0129054120410063","type":"journal-article","created":{"date-parts":[[2020,10,20]],"date-time":"2020-10-20T09:30:40Z","timestamp":1603186240000},"page":"805-825","source":"Crossref","is-referenced-by-count":2,"title":["Decidability of Right One-Way Jumping Finite Automata"],"prefix":"10.1142","volume":"31","author":[{"given":"Simon","family":"Beier","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstr. 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2020,10,19]]},"reference":[{"key":"S0129054120410063BIB001","first-page":"143","volume":"14","author":"Bar-Hillel Y.","year":"1961","journal-title":"Zeitschrift f\u00fcr Phonetik, Sprachwissenschaft und Kommunikationsforschung"},{"key":"S0129054120410063BIB002","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/978-3-319-94631-3_2","volume-title":"Proceedings of the th International Workshop on Descriptional Complexity of Formal Systems","volume":"10952","author":"Beier S.","year":"2018"},{"key":"S0129054120410063BIB003","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1007\/978-3-319-62809-7_6","volume-title":"Proceedings of the st International Conference on Developments in Language Theory","volume":"10396","author":"Beier S.","year":"2017"},{"key":"S0129054120410063BIB004","volume-title":"Grundlagen der Mathematik","author":"Bernays P.","year":"1944"},{"key":"S0129054120410063BIB005","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054116400165"},{"key":"S0129054120410063BIB007","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-319-22360-5_8","volume-title":"Proceedings of the th Conference on Implementation and Application of Automata","volume":"9223","author":"Fernau H.","year":"2015"},{"key":"S0129054120410063BIB008","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.tcs.2016.07.006","volume":"679","author":"Fernau H.","year":"2017","journal-title":"Theoret. Comput. Sci."},{"key":"S0129054120410063BIB009","first-page":"333","volume":"113","author":"Ginsburg S.","year":"1964","journal-title":"Trans. AMS"},{"issue":"5","key":"S0129054120410063BIB010","doi-asserted-by":"crossref","first-page":"1043","DOI":"10.1090\/S0002-9939-1966-0201310-3","volume":"17","author":"Ginsburg S.","year":"1966","journal-title":"Proc. Amer. Math. Soc."},{"issue":"2","key":"S0129054120410063BIB011","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"Ginsburg S.","year":"1966","journal-title":"Pacific Journal of Mathematics"},{"key":"S0129054120410063BIB012","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"issue":"5","key":"S0129054120410063BIB013","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"Immerman N.","year":"1988","journal-title":"SIAM J. Comput."},{"issue":"1","key":"S0129054120410063BIB014","doi-asserted-by":"crossref","DOI":"10.2168\/LMCS-11(1:9)2015","volume":"11","author":"Kopczy\u0144ski E.","year":"2015","journal-title":"Logical Methods in Computer Science"},{"key":"S0129054120410063BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112500244"},{"key":"S0129054120410063BIB016","doi-asserted-by":"crossref","unstructured":"A. Meduna and  P. Zemek,  Regulated Grammars and Automata  (Springer, 2014),  ch. 17: Jumping Finite Automata,  pp. 567\u2013585.","DOI":"10.1007\/978-1-4939-0369-6_17"},{"issue":"4","key":"S0129054120410063BIB017","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"Parikh R. J.","year":"1966","journal-title":"J. ACM"},{"key":"S0129054120410063BIB018","first-page":"92","volume":"395","author":"Presburger M.","year":"1930","journal-title":"Sprawozdanie z I Kongresu metematyk\u00f3w slowia\u0144skich"},{"issue":"3","key":"S0129054120410063BIB019","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"Szelepcs\u00e9nyi R.","year":"1988","journal-title":"Acta Inform."},{"issue":"1","key":"S0129054120410063BIB020","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0129054118500016","volume":"29","author":"Vorel V.","year":"2018","journal-title":"Internat. J. Found. Comput. Sci."}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120410063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,13]],"date-time":"2020-11-13T08:58:25Z","timestamp":1605257905000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120410063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":19,"journal-issue":{"issue":"06","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.1142\/S0129054120410063"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120410063","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}