{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:43:01Z","timestamp":1740109381784,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T00:00:00Z","timestamp":1725926400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T00:00:00Z","timestamp":1725926400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006260","name":"Technion - Israel Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006260","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Jumping automata are finite automata that read their input in a non-consecutive manner, disregarding the order of the letters in the word. We introduce and study jumping automata over infinite words. Unlike the setting of finite words, which has been well studied, for infinite words it is not clear how words can be reordered. To this end, we consider three semantics: automata that read the infinite word in some order so that no letter is overlooked, automata that can permute the word in windows of a given size k, and automata that can permute the word in windows of an existentially-quantified bound. We study expressiveness, closure properties and algorithmic properties of these models.<\/jats:p>","DOI":"10.1007\/s00224-024-10192-w","type":"journal-article","created":{"date-parts":[[2024,9,10]],"date-time":"2024-09-10T11:20:16Z","timestamp":1725967216000},"page":"1572-1600","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Jumping Automata over Infinite Words"],"prefix":"10.1007","volume":"68","author":[{"given":"Shaull","family":"Almagor","sequence":"first","affiliation":[]},{"given":"Omer","family":"Yizhaq","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,10]]},"reference":[{"issue":"07","key":"10192_CR1","doi-asserted-by":"publisher","first-page":"1555","DOI":"10.1142\/S0129054112500244","volume":"23","author":"A Meduna","year":"2012","unstructured":"Meduna, A., Zemek, P.: Jumping finite automata. Int. J. Found. Comput. Sci. 23(07), 1555\u20131578 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10192_CR2","doi-asserted-by":"crossref","unstructured":"Fernau, H., Paramasivan, M., Schmid, M.L.: Jumping finite automata: characterizations and complexity. In: International Conference on Implementation and Application of Automata, pp. 89\u2013101 (2015). Springer","DOI":"10.1007\/978-3-319-22360-5_8"},{"key":"10192_CR3","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/j.tcs.2016.07.006","volume":"679","author":"H Fernau","year":"2017","unstructured":"Fernau, H., Paramasivan, M., Schmid, M.L., Vorel, V.: Characterization and complexity results on jumping finite automata. Theor. Comput. Sci. 679, 31\u201352 (2017)","journal-title":"Theor. Comput. Sci."},{"issue":"01","key":"10192_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0129054118500016","volume":"29","author":"V Vorel","year":"2018","unstructured":"Vorel, V.: On basic properties of jumping finite automata. Int. J. Found. Comput. Sci. 29(01), 1\u201315 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"10192_CR5","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1016\/j.tcs.2021.02.030","volume":"864","author":"SZ Fazekas","year":"2021","unstructured":"Fazekas, S.Z., Hoshi, K., Yamamura, A.: Two-way deterministic automata with jumping mode. Theor. Comput. Sci. 864, 92\u2013102 (2021)","journal-title":"Theor. Comput. Sci."},{"key":"10192_CR6","doi-asserted-by":"crossref","unstructured":"Lavado, G.J., Pighizzini, G., Seki, S.: Operational state complexity under parikh equivalence. In: Descriptional Complexity of Formal Systems: 16th International Workshop, DCFS 2014, Turku, Finland, August 5-8, 2014. Proceedings 16, pp. 294\u2013305 (2014). Springer","DOI":"10.1007\/978-3-319-09704-6_26"},{"key":"10192_CR7","doi-asserted-by":"crossref","unstructured":"B\u00fcchi, J.R.: Symposium on decision problems: On a decision method in restricted second order arithmetic. In: Studies in Logic and the Foundations of Mathematics vol. 44, pp. 1\u201311. (1966). Elsevier","DOI":"10.1016\/S0049-237X(09)70564-6"},{"issue":"5","key":"10192_CR8","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/S0019-9958(66)80013-X","volume":"9","author":"R McNaughton","year":"1966","unstructured":"McNaughton, R.: Testing and generating infinite sequences by a finite automaton. Inf. Control 9(5), 521\u2013530 (1966)","journal-title":"Inf. Control"},{"key":"10192_CR9","doi-asserted-by":"crossref","unstructured":"Kupferman, O.: Automata theory and model checking. Handbook of model checking, 107\u2013151 (2018)","DOI":"10.1007\/978-3-319-10575-8_4"},{"key":"10192_CR10","unstructured":"Landweber, L.H.: Decision problems for w-automata. Technical report, University of Wisconsin-Madison Department of Computer Sciences (1968)"},{"key":"10192_CR11","doi-asserted-by":"crossref","unstructured":"Safra, S.: On the complexity of $$\\omega $$-automata. In: Proc. 29th IEEE Symp. Found. of Comp. Sci, pp. 319\u2013327 (1988)","DOI":"10.1109\/SFCS.1988.21948"},{"issue":"4","key":"10192_CR12","doi-asserted-by":"publisher","first-page":"570","DOI":"10.1145\/321356.321364","volume":"13","author":"RJ Parikh","year":"1966","unstructured":"Parikh, R.J.: On context-free languages. Journal of the ACM (JACM) 13(4), 570\u2013581 (1966)","journal-title":"Journal of the ACM (JACM)"},{"key":"10192_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.4204\/EPTCS.252.8","volume":"252","author":"S Beier","year":"2017","unstructured":"Beier, S., Holzer, M., Kutrib, M.: On the descriptional complexity of operations on semilinear sets. EPTCS 252, 41 (2017)","journal-title":"EPTCS"},{"key":"10192_CR14","unstructured":"Chistikov, D., Haase, C.: The taming of the semi-linear set. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) (2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik"},{"key":"10192_CR15","unstructured":"To, A.W.: Parikh images of regular languages: Complexity and applications. arXiv:1002.1464 (2010)"},{"key":"10192_CR16","doi-asserted-by":"crossref","unstructured":"Klaedtke, F., Rue\u00df, H.: Monadic second-order logics with cardinalities. In: Automata, Languages and Programming: 30th International Colloquium, ICALP 2003 Eindhoven, The Netherlands, June 30\u2013July 4, 2003 Proceedings 30, pp. 681\u2013696 (2003). Springer","DOI":"10.1007\/3-540-45061-0_54"},{"issue":"08","key":"10192_CR17","doi-asserted-by":"publisher","first-page":"1691","DOI":"10.1142\/S0129054112400709","volume":"23","author":"M Cadilhac","year":"2012","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Bounded parikh automata. Int. J. Found. Comput. Sci. 23(08), 1691\u20131709 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"4","key":"10192_CR18","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1051\/ita\/2012013","volume":"46","author":"M Cadilhac","year":"2012","unstructured":"Cadilhac, M., Finkel, A., McKenzie, P.: Affine parikh automata. RAIRO-Theor. Inf. Appl. 46(4), 511\u2013545 (2012)","journal-title":"RAIRO-Theor. Inf. Appl."},{"key":"10192_CR19","unstructured":"Guha, S., Jecker, I., Lehtinen, K., Zimmermann, M.: Parikh automata over infinite words. In: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2022)"},{"key":"10192_CR20","unstructured":"Almagor, S.: Process symmetry in probabilistic transducers. In: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2020)"},{"key":"10192_CR21","doi-asserted-by":"crossref","unstructured":"Abu\u00a0Nassar, A., Almagor, S.: Simulation by rounds of letter-to-letter transducers. In: 30th EACSL Annual Conference on Computer Science Logic (2022)","DOI":"10.46298\/lmcs-19(4:19)2023"},{"key":"10192_CR22","unstructured":"Perrin, D., Pin, J.-\u00c9.: Infinite Words: Automata, Semigroups, Logic and Games. Academic Press, (2004)"},{"key":"10192_CR23","doi-asserted-by":"crossref","unstructured":"Kopczynski, E., To, A.W.: Parikh images of grammars: Complexity and applications. In: 2010 25th Annual IEEE Symposium on Logic in Computer Science, pp. 80\u201389 (2010). IEEE","DOI":"10.1109\/LICS.2010.21"},{"key":"10192_CR24","doi-asserted-by":"crossref","unstructured":"Emerson, E.A., Lei, C.-L.: Modalities for model checking (extended abstract) branching time strikes back. In: Proceedings of the 12th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, pp. 84\u201396 (1985)","DOI":"10.1145\/318593.318620"},{"issue":"4","key":"10192_CR25","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1287\/moor.8.4.538","volume":"8","author":"HW Lenstra Jr","year":"1983","unstructured":"Lenstra, H.W., Jr.: Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538\u2013548 (1983)","journal-title":"Math. Oper. Res."},{"key":"10192_CR26","doi-asserted-by":"crossref","unstructured":"Kopczynski, E.: Complexity of problems of commutative grammars. Log. Methods Comput. Sci. 11 (2015)","DOI":"10.2168\/LMCS-11(1:9)2015"},{"issue":"3","key":"10192_CR27","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/3242953.3242964","volume":"5","author":"C Haase","year":"2018","unstructured":"Haase, C.: A survival guide to presburger arithmetic. ACM SIGLOG News 5(3), 67\u201382 (2018)","journal-title":"ACM SIGLOG News"},{"issue":"2","key":"10192_CR28","first-page":"333","volume":"113","author":"S Ginsburg","year":"1964","unstructured":"Ginsburg, S., Spanier, E.H.: Bounded algol-like languages. Trans. Amer. Math. Soc. 113(2), 333\u2013368 (1964)","journal-title":"Trans. Amer. Math. Soc."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10192-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10192-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10192-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,14]],"date-time":"2024-12-14T06:02:40Z","timestamp":1734156160000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10192-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,10]]},"references-count":28,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["10192"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10192-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2024,9,10]]},"assertion":[{"value":"5 August 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interest"}}]}}