{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:19:58Z","timestamp":1772119198995,"version":"3.50.1"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T00:00:00Z","timestamp":1710374400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Slovak Scientific Grant Agency VEGA","award":["1\/0601\/20"],"award-info":[{"award-number":["1\/0601\/20"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limited automata, the sizes of the resulting devices are polynomial in the sizes of the simulated machines. The situation is different when the operations are applied to deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. The costs for product and star do not reduce if the given machines are sweeping two-way deterministic finite automata. These bounds are tight.<\/jats:p>","DOI":"10.1007\/s00224-024-10163-1","type":"journal-article","created":{"date-parts":[[2024,3,14]],"date-time":"2024-03-14T07:02:38Z","timestamp":1710399758000},"page":"465-486","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Performing Regular Operations with 1-Limited Automata"],"prefix":"10.1007","volume":"68","author":[{"given":"Giovanni","family":"Pighizzini","sequence":"first","affiliation":[]},{"given":"Luca","family":"Prigioniero","sequence":"additional","affiliation":[]},{"given":"\u0160imon","family":"S\u00e1dovsk\u00fd","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,3,14]]},"reference":[{"key":"10163_CR1","doi-asserted-by":"publisher","unstructured":"Pighizzini, G., Prigioniero, L., S\u00e1dovsk\u00fd, S.: Performing regular operations with 1-limited automata. In: DLT 2022, Proceedings. Lecture Notes in Computer Science, vol. 13257, pp. 239\u2013250. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-05578-2_19","DOI":"10.1007\/978-3-031-05578-2_19"},{"key":"10163_CR2","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. In: Doklady Akademii Nauk, vol. 194, pp. 1266\u20131268 (1970). Russian Academy of Sciences"},{"key":"10163_CR3","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0304-3975(81)80005-9","volume":"13","author":"EL Leiss","year":"1981","unstructured":"Leiss, E.L.: Succint representation of regular languages by boolean automata. Theor. Comput. Sci. 13, 323\u2013330 (1981). https:\/\/doi.org\/10.1016\/S0304-3975(81)80005-9","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"10163_CR4","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/126537.126543","volume":"22","author":"S Yu","year":"1991","unstructured":"Yu, S., Zhuang, Q.: On the state complexity of intersection of regular languages. SIGACT News 22(3), 52\u201354 (1991). https:\/\/doi.org\/10.1145\/126537.126543","journal-title":"SIGACT News"},{"issue":"2","key":"10163_CR5","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1016\/0304-3975(92)00011-F","volume":"125","author":"S Yu","year":"1994","unstructured":"Yu, S., Zhuang, Q., Salomaa, K.: The state complexities of some basic operations on regular languages. Theor. Comput. Sci. 125(2), 315\u2013328 (1994). https:\/\/doi.org\/10.1016\/0304-3975(92)00011-F","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"10163_CR6","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev 3(2), 114\u2013125 (1959). https:\/\/doi.org\/10.1147\/rd.32.0114","journal-title":"IBM J. Res. Dev"},{"issue":"2","key":"10163_CR7","doi-asserted-by":"publisher","first-page":"198","DOI":"10.1147\/rd.32.0198","volume":"3","author":"JC Shepherdson","year":"1959","unstructured":"Shepherdson, J.C.: The reduction of two-way automata to one-way automata. IBM J. Res. Dev. 3(2), 198\u2013200 (1959). https:\/\/doi.org\/10.1147\/rd.32.0198","journal-title":"IBM J. Res. Dev."},{"issue":"1\u20134","key":"10163_CR8","doi-asserted-by":"publisher","first-page":"231","DOI":"10.3233\/FI-2011-540","volume":"110","author":"M Kunc","year":"2011","unstructured":"Kunc, M., Okhotin, A.: State complexity of union and intersection for two-way nondeterministic finite automata. Fundam. Informaticae 110(1\u20134), 231\u2013239 (2011). https:\/\/doi.org\/10.3233\/FI-2011-540","journal-title":"Fundam. Informaticae"},{"key":"10163_CR9","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1016\/j.ic.2016.12.007","volume":"253","author":"G Jir\u00e1skov\u00e1","year":"2017","unstructured":"Jir\u00e1skov\u00e1, G., Okhotin, A.: On the state complexity of operations on two-way finite automata. Inf. Comput. 253, 36\u201363 (2017). https:\/\/doi.org\/10.1016\/j.ic.2016.12.007","journal-title":"Inf. Comput."},{"issue":"1\/2","key":"10163_CR10","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1016\/S0019-9958(67)90513-X","volume":"11","author":"TN Hibbard","year":"1967","unstructured":"Hibbard, T.N.: A generalization of context-free determinism. Inf. Control 11(1\/2), 196\u2013238 (1967)","journal-title":"Inf. Control"},{"issue":"7","key":"10163_CR11","doi-asserted-by":"publisher","first-page":"897","DOI":"10.1142\/S0129054114400140","volume":"25","author":"G Pighizzini","year":"2014","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and regular languages. Int. J. Found. Comput. Sci. 25(7), 897\u2013916 (2014). https:\/\/doi.org\/10.1142\/S0129054114400140","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20132","key":"10163_CR12","doi-asserted-by":"publisher","first-page":"157","DOI":"10.3233\/FI-2015-1148","volume":"136","author":"G Pighizzini","year":"2015","unstructured":"Pighizzini, G., Pisoni, A.: Limited automata and context-free languages. Fundam. Inform. 136(1\u20132), 157\u2013176 (2015). https:\/\/doi.org\/10.3233\/FI-2015-1148","journal-title":"Fundam. Inform."},{"key":"10163_CR13","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/j.tcs.2019.03.037","volume":"798","author":"B Guillon","year":"2019","unstructured":"Guillon, B., Prigioniero, L.: Linear-time limited automata. Theor. Comput. Sci. 798, 95\u2013108 (2019). https:\/\/doi.org\/10.1016\/j.tcs.2019.03.037","journal-title":"Theor. Comput. Sci."},{"key":"10163_CR14","doi-asserted-by":"publisher","unstructured":"Pighizzini, G.: Limited automata: properties, complexity and variants. In: DCFS 2019, Proceedings. Lecture Notes in Computer Science, vol. 11612, pp. 57\u201373. Springer, Cham(2019). https:\/\/doi.org\/10.1007\/978-3-030-23247-4_4","DOI":"10.1007\/978-3-030-23247-4_4"},{"key":"10163_CR15","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1016\/j.ic.2019.01.002","volume":"266","author":"G Pighizzini","year":"2019","unstructured":"Pighizzini, G., Prigioniero, L.: Limited automata and unary languages. Inf. Comput. 266, 60\u201374 (2019). https:\/\/doi.org\/10.1016\/j.ic.2019.01.002","journal-title":"Inf. Comput."},{"key":"10163_CR16","doi-asserted-by":"publisher","unstructured":"Yamakami, T.: Behavioral strengths and weaknesses of various models of limited automata. In: SOFSEM 2019, Proceedings. Lecture Notes in Computer Science, vol. 11376, pp. 519\u2013530. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-10801-4_40","DOI":"10.1007\/978-3-030-10801-4_40"},{"issue":"1\u20133","key":"10163_CR17","doi-asserted-by":"publisher","first-page":"229","DOI":"10.25596\/jalc-2022-229","volume":"27","author":"G Pighizzini","year":"2022","unstructured":"Pighizzini, G., Prigioniero, L., S\u00e1dovsk\u00fd, S.: 1-Limited automata: Witness languages and techniques. J. Autom. Lang. Comb. 27(1\u20133), 229\u2013244 (2022). https:\/\/doi.org\/10.25596\/jalc-2022-229","journal-title":"J. Autom. Lang. Comb."},{"key":"10163_CR18","volume-title":"Computational Complexity","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W., Wechsung, G.: Computational Complexity. D. Reidel Publishing Company, Dordrecht (1986)"},{"key":"10163_CR19","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts (1979)"},{"issue":"2","key":"10163_CR20","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/0022-0000(80)90034-3","volume":"21","author":"M Sipser","year":"1980","unstructured":"Sipser, M.: Lower bounds on the size of sweeping automata. J. Comput. Syst. Sci. 21(2), 195\u2013202 (1980). https:\/\/doi.org\/10.1016\/0022-0000(80)90034-3","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10163-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10163-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10163-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T22:03:13Z","timestamp":1718920993000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10163-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,14]]},"references-count":20,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["10163"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10163-1","relation":{"has-preprint":[{"id-type":"doi","id":"10.21203\/rs.3.rs-2338203\/v1","asserted-by":"object"}]},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,14]]},"assertion":[{"value":"18 January 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}