{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:31:51Z","timestamp":1758274311654},"reference-count":14,"publisher":"World Scientific Pub Co Pte Lt","issue":"01","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p> We consider jumping finite automata and their operational state complexity and decidability status. Roughly speaking, a jumping automaton is a finite automaton with a non-continuous input. This device has nice relations to semilinear sets and thus to Parikh images of regular sets, which will be exhaustively used in our proofs. In particular, we prove upper bounds on the intersection and complementation. The latter result on the complementation upper bound answers an open problem from [G. J. Lavado, G. Pighizzini, S. Seki: Operational State Complexity of Parikh Equivalence, 2014]. Moreover, we correct an erroneous result on the inverse homomorphism closure. Finally, we also consider the decidability status of standard problems as regularity, disjointness, universality, inclusion, etc. for jumping finite automata. <\/jats:p>","DOI":"10.1142\/s012905411940001x","type":"journal-article","created":{"date-parts":[[2019,3,5]],"date-time":"2019-03-05T09:13:14Z","timestamp":1551777194000},"page":"5-27","source":"Crossref","is-referenced-by-count":2,"title":["Operational State Complexity and Decidability of Jumping Finite Automata"],"prefix":"10.1142","volume":"30","author":[{"given":"Simon","family":"Beier","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]},{"given":"Markus","family":"Holzer","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]},{"given":"Martin","family":"Kutrib","sequence":"additional","affiliation":[{"name":"Institut f\u00fcr Informatik, Universit\u00e4t Giessen, Arndtstrasse 2, 35392 Giessen, Germany"}]}],"member":"219","published-online":{"date-parts":[[2019,3,5]]},"reference":[{"key":"S012905411940001XBIB001","volume-title":"Modern Information Retrieval \u2014 The Concepts and Technology Behind Search","author":"Baeza-Yates R. A.","year":"2011"},{"key":"S012905411940001XBIB003","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90002-W"},{"key":"S012905411940001XBIB004","doi-asserted-by":"publisher","DOI":"10.2307\/2370405"},{"key":"S012905411940001XBIB006","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.07.006"},{"key":"S012905411940001XBIB007","first-page":"333","volume":"113","author":"Ginsburg S.","year":"1964","journal-title":"Trans. Amer. Math. Soc."},{"key":"S012905411940001XBIB008","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"Hopcroft J. E.","year":"1979"},{"key":"S012905411940001XBIB009","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90092-6"},{"key":"S012905411940001XBIB010","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80015-2"},{"key":"S012905411940001XBIB011","first-page":"147","volume":"22","author":"Huynh D. T.","year":"1986","journal-title":"J. Inform. Process. Cybern."},{"key":"S012905411940001XBIB012","first-page":"291","volume":"18","author":"Huynh T.","year":"1982","journal-title":"J. Inform. Process. Cybern."},{"key":"S012905411940001XBIB013","first-page":"paper 9","volume":"11","author":"Kopczy\u0144ki E.","year":"2015","journal-title":"Log. Methods Comput. Sci."},{"key":"S012905411940001XBIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2013.06.003"},{"key":"S012905411940001XBIB017","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054112500244"},{"key":"S012905411940001XBIB020","first-page":"189","volume":"22","author":"Vorel V.","year":"2017","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\/S012905411940001X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T18:35:24Z","timestamp":1565116524000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905411940001X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1]]},"references-count":14,"journal-issue":{"issue":"01","published-online":{"date-parts":[[2019,3,5]]},"published-print":{"date-parts":[[2019,1]]}},"alternative-id":["10.1142\/S012905411940001X"],"URL":"https:\/\/doi.org\/10.1142\/s012905411940001x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1]]}}}