{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:17Z","timestamp":1759638977178,"version":"3.40.3"},"publisher-location":"Cham","reference-count":18,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319223599"},{"type":"electronic","value":"9783319223605"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-22360-5_8","type":"book-chapter","created":{"date-parts":[[2015,7,27]],"date-time":"2015-07-27T08:24:42Z","timestamp":1437985482000},"page":"89-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Jumping Finite Automata: Characterizations and Complexity"],"prefix":"10.1007","author":[{"given":"Henning","family":"Fernau","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meenakshi","family":"Paramasivan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Markus L.","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,7,28]]},"reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Crespi-Reghizzi, S., San Pietro, P.: Commutative languages and their composition by consensual methods. In: \u00c9sik, V., F\u00fcl\u00f6p, Z. (eds.) Proceedings 14th International Conference on Automata and Formal Languages (AFL), vol. 151 of EPTCS, pp. 216\u2013230 (2014)","DOI":"10.4204\/EPTCS.151.15"},{"key":"8_CR2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"RG Downey","year":"2013","unstructured":"Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Heidelberg (2013)"},{"issue":"4","key":"8_CR3","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1307\/mmj\/1028998975","volume":"10","author":"LC Eggan","year":"1963","unstructured":"Eggan, L.C.: Transition graphs and the star-height of regular events. Mich. Math. J. 10(4), 385\u2013397 (1963)","journal-title":"Mich. Math. J."},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/0304-3975(82)90124-4","volume":"27","author":"A Ehrenfeucht","year":"1983","unstructured":"Ehrenfeucht, A., Haussler, D., Rozenberg, G.: On regularity of context-free languages. Theor. Comput. Sci. 27, 311\u2013332 (1983)","journal-title":"Theor. Comput. Sci."},{"issue":"12","key":"8_CR5","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1016\/j.ipl.2011.03.019","volume":"111","author":"J Esparza","year":"2011","unstructured":"Esparza, J., Ganty, P., Kiefer, S., Luttenberger, M.: Parikh\u2019s theorem: A simple and direct automaton construction. Inf. Process. Lett. 111(12), 614\u2013619 (2011)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/0890-5401(88)90033-8","volume":"78","author":"K Hashiguchi","year":"1988","unstructured":"Hashiguchi, K.: Algorithms for determining relative star height and star height. Inf. Comput. 78(2), 124\u2013169 (1988)","journal-title":"Inf. Comput."},{"key":"8_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/3-540-07854-1_196","volume-title":"Mathematical Foundations of Computer Science 1976","author":"M H\u00f6pner","year":"1976","unstructured":"H\u00f6pner, M., Opp, M.: About three equations classes of languages built up by shuffle operations. In: Mazurkiewicz, A.W. (ed.) MFCS 1976. LNCS, vol. 45, pp. 337\u2013344. Springer, Heidelberg (1976)"},{"key":"8_CR8","unstructured":"Jantzen, M.: Eigenschaften von Petrinetzsprachen. Technical report IFI-HH-B-64, Fachbereich Informatik, Universit\u00e4t Hamburg, Germany (1979)"},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0304-3975(81)90054-2","volume":"14","author":"M Jantzen","year":"1981","unstructured":"Jantzen, M.: The power of synchronizing operations on strings. Theor. Comput. Sci. 14, 127\u2013154 (1981)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0304-3975(85)90221-X","volume":"38","author":"M Jantzen","year":"1985","unstructured":"Jantzen, M.: Extending regular expressions with iterated shuffle. Theor. Comput. Sci. 38, 223\u2013247 (1985)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20132","key":"8_CR11","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0304-3975(99)00109-7","volume":"250","author":"J Jedrzejowicz","year":"2001","unstructured":"Jedrzejowicz, J., Szepietowski, A.: Shuffle languages are in P. Theor. Comput. Sci. 250(1\u20132), 31\u201353 (2001)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1007\/978-3-319-07956-1_2","volume-title":"Algorithmic Aspects in Information and Management","author":"H Jiang","year":"2014","unstructured":"Jiang, H., Su, B., Xiao, M., Xu, Y., Zhong, F., Zhu, B.: On the exact block cover problem. In: Gu, Q., Hell, P., Yang, B. (eds.) AAIM 2014. LNCS, vol. 8546, pp. 13\u201322. Springer, Heidelberg (2014)"},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"573","DOI":"10.1051\/ita\/2012014","volume":"46","author":"O Kl\u00edma","year":"2012","unstructured":"Kl\u00edma, O., Pol\u00e1k, L.: On biautomata. RAIRO Informatique th\u00e9orique et Appl. Theor. Inf. Appl. 46, 573\u2013592 (2012)","journal-title":"RAIRO Informatique th\u00e9orique et Appl. Theor. Inf. Appl."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/0022-0000(84)90013-8","volume":"1","author":"M Latteux","year":"1984","unstructured":"Latteux, M., Rozenberg, G.: Commutative one-counter languages are regular. J. Comput. Sys. Sci. 1, 54\u201357 (1984)","journal-title":"J. Comput. Sys. Sci."},{"issue":"7","key":"8_CR15","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(7), 1555\u20131578 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"8_CR16","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/978-1-4939-0369-6_17","volume-title":"Regulated Grammars and Automata","author":"A Meduna","year":"2014","unstructured":"Meduna, A., Zemek, P.: Chapter 17: Jumping finite automata. In: Meduna, A., Zemek, P. (eds.) Regulated Grammars and Automata, pp. 567\u2013585. Springer, New York (2014)"},{"key":"8_CR17","first-page":"269","volume-title":"Formal Languages and Applications, volume 25 of Studies in Computational Intelligence","author":"F Otto","year":"2006","unstructured":"Otto, F.: Restarting automata. In: \u00c9sik, Z., Mart\u00edn-Vide, C., Mitrana, V. (eds.) FCT 1995, vol. 965, pp. 269\u2013303. Springer, Heidelberg (2006)"},{"issue":"4","key":"8_CR18","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. J. ACM 13(4), 570\u2013581 (1966)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Implementation and Application of Automata"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-22360-5_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T06:21:42Z","timestamp":1676960502000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-22360-5_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319223599","9783319223605"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-22360-5_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"28 July 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}