{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T22:40:01Z","timestamp":1754174401676,"version":"3.41.2"},"publisher-location":"Cham","reference-count":93,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030817008"},{"type":"electronic","value":"9783030817015"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"DOI":"10.1007\/978-3-030-81701-5_1","type":"book-chapter","created":{"date-parts":[[2021,8,3]],"date-time":"2021-08-03T15:16:19Z","timestamp":1628003779000},"page":"3-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hot Current Topics of Descriptional Complexity"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[]},{"given":"Nelma","family":"Moreira","sequence":"additional","affiliation":[]},{"given":"Giovanni","family":"Pighizzini","sequence":"additional","affiliation":[]},{"given":"Rog\u00e9rio","family":"Reis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,4]]},"reference":[{"issue":"2","key":"1_CR1","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2007.07.029","volume":"387","author":"M Almeida","year":"2007","unstructured":"Almeida, M., Moreira, N., Reis, R.: Enumeration and generation with a string automata representation. Theoret. Comput. Sci. 387(2), 93\u2013102 (2007)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1_CR2","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1142\/S0129054108005930","volume":"19","author":"M Almeida","year":"2008","unstructured":"Almeida, M., Moreira, N., Reis, R.: Exact generation of minimal acyclic deterministic finite automata. Int. J. Found. Comput. Sci. 19(4), 751\u2013765 (2008)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20133","key":"1_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.tcs.2007.04.001","volume":"381","author":"F Bassino","year":"2007","unstructured":"Bassino, F., Nicaud, C.: Enumeration and random generation of accessible automata. Theoret. Comput. Sci. 381(1\u20133), 86\u2013104 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-662-43951-7_1","volume-title":"Automata, Languages, and Programming","author":"J Bell","year":"2014","unstructured":"Bell, J., Brzozowski, J., Moreira, N., Reis, R.: Symmetric groups and quotient complexity of Boolean operations. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 1\u201312. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43951-7_1"},{"key":"1_CR5","doi-asserted-by":"publisher","unstructured":"Berman, P.: A note on sweeping automata. In: de Bakker, J.W., van Leeuwen, J. (eds.) Proceedings 7th ICALP 1980. LNCS, vol. 85, pp. 91\u201397. Springer (1980). https:\/\/doi.org\/10.1007\/3-540-10003-2_62","DOI":"10.1007\/3-540-10003-2_62"},{"key":"1_CR6","unstructured":"Berman, P., Lingas, A.: On the complexity of regular languages in terms of finite automata. Technical Report 304, Polish Academy of Sciences (1977)"},{"key":"1_CR7","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.tcs.2006.07.059","volume":"369","author":"H Bordihn","year":"2006","unstructured":"Bordihn, H., Fernau, H., Holzer, M., Manca, V., Martin-Vide, C.: Iterated sequential transducers as language generating devices. Theoret. Comput. Sci. 369, 67\u201381 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR8","doi-asserted-by":"publisher","first-page":"3209","DOI":"10.1016\/j.tcs.2009.05.019","volume":"410","author":"H Bordihn","year":"2009","unstructured":"Bordihn, H., Holzer, M., Kutrib, M.: Determinization of finite automata accepting subregular languages. Theoret. Comput. Sci. 410, 3209\u20133222 (2009)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR9","first-page":"167","volume":"116","author":"S Broda","year":"2015","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Average size of automata constructions from regular expressions. Bull. EATCS 116, 167\u2013192 (2015)","journal-title":"Bull. EATCS"},{"issue":"6\u20137","key":"1_CR10","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1142\/S0129054119400227","volume":"30","author":"S Broda","year":"2019","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: On average behaviour of regular expressions in strong star normal form. Int. J. Found. Comput. Sci. 30(6\u20137), 899\u2013920 (2019)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"1_CR11","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1145\/3388392.3388401","volume":"51","author":"S Broda","year":"2020","unstructured":"Broda, S., Machiavelo, A., Moreira, N., Reis, R.: Analytic combinatorics and descriptional complexity of regular languages on average. ACM SIGACT News 51(1), 38\u201356 (2020)","journal-title":"ACM SIGACT News"},{"issue":"6","key":"1_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1142\/S0129054113400133","volume":"24","author":"J Brzozowski","year":"2013","unstructured":"Brzozowski, J.: In search of most complex regular languages. Int. J. Found. Comput. Sci. 24(6), 691\u2013708 (2013)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20133","key":"1_CR13","first-page":"67","volume":"23","author":"JA Brzozowski","year":"2018","unstructured":"Brzozowski, J.A.: Towards a theory of complexity of regular languages. J. Autom. Lang. Comb. 23(1\u20133), 67\u2013101 (2018)","journal-title":"J. Autom. Lang. Comb."},{"key":"1_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/3-540-45526-4_6","volume-title":"Automata Implementation","author":"C C\u00e2mpeanu","year":"2001","unstructured":"C\u00e2mpeanu, C., Culik, K., Salomaa, K., Yu, S.: State complexity of basic operations on finite languages. In: Boldt, O., J\u00fcrgensen, H. (eds.) WIA 1999. LNCS, vol. 2214, pp. 60\u201370. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-45526-4_6"},{"key":"1_CR15","doi-asserted-by":"crossref","unstructured":"Caron, P., le Court, E.H., Luque, J., Patrou, B.: New tools for state complexity. Discret. Math. Theor. Comput. Sci. 22(1) (2020)","DOI":"10.23638\/DMTCS-22-1-9"},{"issue":"2","key":"1_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/j.tcs.2004.03.072","volume":"330","author":"JM Champarnaud","year":"2005","unstructured":"Champarnaud, J.M., Parantho\u00ebn, T.: Random generation of DFAs. Theoret. Comput. Sci. 330(2), 221\u2013235 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"1_CR17","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/0304-3975(86)90142-8","volume":"47","author":"M Chrobak","year":"1986","unstructured":"Chrobak, M.: Finite automata and unary languages. Theoret. Comput. Sci. 47(3), 149\u2013158 (1986)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR18","doi-asserted-by":"publisher","first-page":"668","DOI":"10.1137\/0215049","volume":"15","author":"C Citrini","year":"1986","unstructured":"Citrini, C., Crespi-Reghizzi, S., Mandrioli, D.: On deterministic multi-pass analysis. SIAM J. Comput. 15, 668\u2013693 (1986)","journal-title":"SIAM J. Comput."},{"key":"1_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/978-3-319-98654-8_21","volume-title":"Developments in Language Theory","author":"S Davies","year":"2018","unstructured":"Davies, S.: A general approach to state complexity of operations: formalization and limitations. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 256\u2013268. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_21"},{"issue":"8","key":"1_CR20","doi-asserted-by":"publisher","first-page":"1952","DOI":"10.1007\/s00224-018-9859-0","volume":"62","author":"S Davies","year":"2018","unstructured":"Davies, S.: Primitivity, uniform minimality, and state complexity of Boolean operations. Theory Comput. Syst. 62(8), 1952\u20132005 (2018)","journal-title":"Theory Comput. Syst."},{"key":"1_CR21","unstructured":"Davies, S.: Algebraic Approaches to State Complexity of Regular Operations. Ph.D. thesis, University of Waterloo, Ontario, Canada (2019)"},{"key":"1_CR22","unstructured":"Domaratzki, M.: Enumeration of formal languages. Bull. EATCS 89, 113\u2013133 (2006)"},{"key":"1_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/11821069_28","volume-title":"Mathematical Foundations of Computer Science 2006","author":"M Domaratzki","year":"2006","unstructured":"Domaratzki, M., Salomaa, K.: Lower bounds for the transition complexity of NFAs. In: Kr\u00e1lovi\u010d, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 315\u2013326. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11821069_28"},{"key":"1_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-642-38536-0_8","volume-title":"Computer Science \u2013 Theory and Applications","author":"S De Felice","year":"2013","unstructured":"De Felice, S., Nicaud, C.: Random generation of deterministic acyclic automata using the recursive method. In: Bulatov, A.A., Shur, A.M. (eds.) CSR 2013. LNCS, vol. 7913, pp. 88\u201399. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38536-0_8"},{"key":"1_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/978-3-319-94631-3_8","volume-title":"Descriptional Complexity of Formal Systems","author":"M Ferreira","year":"2018","unstructured":"Ferreira, M., Moreira, N., Reis, R.: Forward injective finite automata: exact and random generation of nonisomorphic NFAs. In: Konstantinidis, S., Pighizzini, G. (eds.) DCFS 2018. LNCS, vol. 10952, pp. 88\u2013100. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-94631-3_8"},{"key":"1_CR26","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.tcs.2003.10.007","volume":"313","author":"N Friburger","year":"2004","unstructured":"Friburger, N., Maurel, D.: Finite-state transducer cascades to extract named entities in texts. Theoret. Comput. Sci. 313, 93\u2013104 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"1_CR27","first-page":"251","volume":"21","author":"Y Gao","year":"2017","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. J. Autom. Lang. Comb. 21(4), 251\u2013310 (2017)","journal-title":"J. Autom. Lang. Comb."},{"key":"1_CR28","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ic.2014.08.009","volume":"239","author":"V Geffert","year":"2014","unstructured":"Geffert, V., Guillon, B., Pighizzini, G.: Two-way automata making choices only at the endmarkers. Inf. Comput. 239, 71\u201386 (2014)","journal-title":"Inf. Comput."},{"key":"1_CR29","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/S0304-3975(02)00403-6","volume":"295","author":"V Geffert","year":"2003","unstructured":"Geffert, V., Mereghetti, C., Pighizzini, G.: Converting two-way nondeterministic unary automata into simpler automata. Theoret. Comput. Sci. 295, 189\u2013203 (2003)","journal-title":"Theoret. Comput. Sci."},{"issue":"7","key":"1_CR30","doi-asserted-by":"publisher","first-page":"1016","DOI":"10.1016\/j.ic.2011.03.003","volume":"209","author":"V Geffert","year":"2011","unstructured":"Geffert, V., Pighizzini, G.: Two-way unary automata versus logarithmic space. Inf. Comput. 209(7), 1016\u20131025 (2011)","journal-title":"Inf. Comput."},{"key":"1_CR31","doi-asserted-by":"crossref","unstructured":"Ginzburg, A.: Algebraic Theory of Automata. Academic Press, Cambridge (1968)","DOI":"10.1016\/B978-1-4832-0013-2.50009-6"},{"key":"1_CR32","first-page":"193","volume":"8","author":"J Goldstine","year":"2002","unstructured":"Goldstine, J., et al.: Descriptional complexity of machines with limited resources. J. UCS 8, 193\u2013234 (2002)","journal-title":"J. UCS"},{"key":"1_CR33","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2007.07.035","volume":"387","author":"H Gruber","year":"2007","unstructured":"Gruber, H., Holzer, M.: On the average state and transition complexity of finite languages. Theoret. Comput. Sci. 387, 155\u2013166 (2007)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-319-98654-8_30","volume-title":"Developments in Language Theory","author":"B Guillon","year":"2018","unstructured":"Guillon, B., Pighizzini, G., Prigioniero, L., Pr\u016f\u0161a, D.: Two-way automata and one-tape machines. In: Hoshi, M., Seki, S. (eds.) DLT 2018. LNCS, vol. 11088, pp. 366\u2013378. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-98654-8_30"},{"key":"1_CR35","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. Theoret. Comput. Sci. 798, 95\u2013108 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR36","volume-title":"Algebraic Structure Theory of Sequential Machines","author":"J Hartmanis","year":"1966","unstructured":"Hartmanis, J., Stearns, R.E.: Algebraic Structure Theory of Sequential Machines. Prentice-Hall, Hoboken (1966)"},{"key":"1_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-319-22360-5_12","volume-title":"Implementation and Application of Automata","author":"P-C H\u00e9am","year":"2015","unstructured":"H\u00e9am, P.-C., Joly, J.-L.: On the uniform random generation of non deterministic automata up\u00a0to isomorphism. In: Drewes, F. (ed.) CIAA 2015. LNCS, vol. 9223, pp. 140\u2013152. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-22360-5_12"},{"issue":"6","key":"1_CR38","doi-asserted-by":"publisher","first-page":"553","DOI":"10.1016\/S0019-9958(65)90399-2","volume":"8","author":"FC Hennie","year":"1965","unstructured":"Hennie, F.C.: One-tape, off-line Turing machine computations. Inform. Control 8(6), 553\u2013578 (1965)","journal-title":"Inform. Control"},{"issue":"1\/2","key":"1_CR39","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. Inform. Control 11(1\/2), 196\u2013238 (1967)","journal-title":"Inform. Control"},{"key":"1_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1007\/3-540-44977-9_14","volume-title":"Implementation and Application of Automata","author":"M Holzer","year":"2003","unstructured":"Holzer, M., Kutrib, M.: State complexity of basic operations on nondeterministic finite automata. In: Champarnaud, J.-M., Maurel, D. (eds.) CIAA 2002. LNCS, vol. 2608, pp. 148\u2013157. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-44977-9_14"},{"key":"1_CR41","doi-asserted-by":"crossref","unstructured":"Holzer, M., Kutrib, M.: Descriptional complexity - an introductory survey. In: Martin-Vide, C. (ed.) Scientific Applications of Language Methods, pp. 1\u201358. Imperial College Press (2010)","DOI":"10.1142\/9781848165458_0001"},{"key":"1_CR42","doi-asserted-by":"publisher","first-page":"456","DOI":"10.1016\/j.ic.2010.11.013","volume":"209","author":"M Holzer","year":"2011","unstructured":"Holzer, M., Kutrib, M.: Descriptional and computational complexity of finite automata - a survey. Inform. Comput. 209, 456\u2013470 (2011)","journal-title":"Inform. Comput."},{"key":"1_CR43","unstructured":"Holzer, M., Kutrib, M.: Automata that may change their mind. In: Freund, R., Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Pighizzini, G. (eds.) Non-Classical Models of Automata and Applications (NCMA 2018). books@ocg.at, vol. 332, pp. 83\u201398. Austrian Computer Society, Vienna (2018)"},{"key":"1_CR44","doi-asserted-by":"publisher","first-page":"1069","DOI":"10.1142\/S012905411940029X","volume":"30","author":"M Holzer","year":"2019","unstructured":"Holzer, M., Kutrib, M.: One-time nondeterministic computations. Int. J. Found. Comput. Sci. 30, 1069\u20131089 (2019)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/3-540-45061-0_36","volume-title":"Automata, Languages and Programming","author":"J Hromkovi\u010d","year":"2003","unstructured":"Hromkovi\u010d, J., Schnitger, G.: Nondeterminism versus determinism for two-way finite automata: generalizations of Sipser\u2019s separation. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 439\u2013451. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-45061-0_36"},{"key":"1_CR46","doi-asserted-by":"publisher","unstructured":"Hromkovi\u010d, J., Schnitger, G.: NFAs with and without $$\\epsilon $$-transitions. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 385\u2013396. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11523468_32","DOI":"10.1007\/11523468_32"},{"key":"1_CR47","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1006\/jcss.2001.1748","volume":"62","author":"J Hromkovi\u010d","year":"2001","unstructured":"Hromkovi\u010d, J., Seibert, S., Wilke, T.: Translating regular expressions into small $$\\epsilon $$-free nondeterministic finite automata. J. Comput. System Sci. 62, 565\u2013588 (2001)","journal-title":"J. Comput. System Sci."},{"key":"1_CR48","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1016\/S0304-3975(00)00029-3","volume":"237","author":"K Iwama","year":"2000","unstructured":"Iwama, K., Kambayashi, Y., Takaki, K.: Tight bounds on the number of states of DFAs that are equivalent to n-state NFAs. Theoret. Comput. Sci. 237, 485\u2013494 (2000)","journal-title":"Theoret. Comput. Sci."},{"key":"1_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/978-3-642-31623-4_2","volume-title":"Descriptional Complexity of Formal Systems","author":"CA Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.A.: Minicomplexity. In: Kutrib, M., Moreira, N., Reis, R. (eds.) DCFS 2012. LNCS, vol. 7386, pp. 20\u201342. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31623-4_2"},{"issue":"2\u20134","key":"1_CR50","first-page":"205","volume":"17","author":"CA Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.A.: Minicomplexity. J. Autom. Lang. Comb. 17(2\u20134), 205\u2013224 (2012)","journal-title":"J. Autom. Lang. Comb."},{"key":"1_CR51","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1016\/j.ic.2012.11.001","volume":"222","author":"CA Kapoutsis","year":"2013","unstructured":"Kapoutsis, C.A.: Nondeterminism is essential in small two-way finite automata with few reversals. Inf. Comput. 222, 208\u2013227 (2013)","journal-title":"Inf. Comput."},{"issue":"2","key":"1_CR52","doi-asserted-by":"publisher","first-page":"421","DOI":"10.1007\/s00224-013-9465-0","volume":"55","author":"CA Kapoutsis","year":"2014","unstructured":"Kapoutsis, C.A.: Two-way automata versus logarithmic space. Theory Comput. Syst. 55(2), 421\u2013447 (2014)","journal-title":"Theory Comput. Syst."},{"key":"1_CR53","doi-asserted-by":"crossref","unstructured":"Kapoutsis, C.A.: Minicomplexity - some motivation, some history, and some structure (invited talk extended abstract). In: Catania, B., Kr\u00e1lovic, R., Nawrocki, J.R., Pighizzini, G. (eds.) SOFSEM 2019. LNCS, vol. 11376, pp. 28\u201338. Springer (2019)","DOI":"10.1007\/978-3-030-10801-4_3"},{"issue":"2","key":"1_CR54","doi-asserted-by":"publisher","first-page":"537","DOI":"10.1016\/j.jcss.2011.06.004","volume":"78","author":"CA Kapoutsis","year":"2012","unstructured":"Kapoutsis, C.A., Kr\u00e1lovic, R., M\u00f6mke, T.: Size complexity of rotating and sweeping automata. J. Comput. Syst. Sci. 78(2), 537\u2013558 (2012)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"1_CR55","doi-asserted-by":"publisher","first-page":"662","DOI":"10.1007\/s00224-014-9560-x","volume":"56","author":"CA Kapoutsis","year":"2015","unstructured":"Kapoutsis, C.A., Pighizzini, G.: Two-way automata characterizations of L\/poly versus NL. Theory Comput. Syst. 56(4), 662\u2013685 (2015)","journal-title":"Theory Comput. Syst."},{"key":"1_CR56","unstructured":"Koechlin, F., Nicaud, C., Rotondo, P.: Uniform random expressions lack expressivity. In: Rossmanith, P., Heggernes, P., Katoen, J. (eds.) MFCS 2019. LIPIcs, vol. 138, pp. 51:1\u201351:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"1_CR57","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1142\/S0129054105003406","volume":"16","author":"M Kutrib","year":"2005","unstructured":"Kutrib, M.: The phenomenon of non-recursive trade-offs. Int. J. Found. Comput. Sci. 16, 957\u2013973 (2005)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1_CR58","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/978-3-030-23247-4_17","volume-title":"Descriptional Complexity of Formal Systems","author":"M Kutrib","year":"2019","unstructured":"Kutrib, M., Malcher, A., Mereghetti, C., Palano, B.: Descriptional complexity of iterated uniform finite-state transducers. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Konstantinidis, S. (eds.) DCFS 2019. LNCS, vol. 11612, pp. 223\u2013234. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-23247-4_17"},{"key":"1_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/978-3-030-51466-2_8","volume-title":"Beyond the Horizon of Computability","author":"M Kutrib","year":"2020","unstructured":"Kutrib, M., Malcher, A., Mereghetti, C., Palano, B.: Deterministic and nondeterministic iterated uniform finite-state transducers: computational and descriptional power. In: Anselmo, M., Della Vedova, G., Manea, F., Pauly, A. (eds.) CiE 2020. LNCS, vol. 12098, pp. 87\u201399. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-51466-2_8"},{"key":"1_CR60","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.ic.2014.04.001","volume":"237","author":"M Kutrib","year":"2014","unstructured":"Kutrib, M., Malcher, A., Pighizzini, G.: Oblivious two-way finite automata: decidability and complexity. Inf. Comput. 237, 294\u2013302 (2014)","journal-title":"Inf. Comput."},{"issue":"2","key":"1_CR61","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ic.2017.09.005","volume":"259","author":"M Kutrib","year":"2018","unstructured":"Kutrib, M., Pighizzini, G., Wendlandt, M.: Descriptional complexity of limited automata. Inf. Comput. 259(2), 259\u2013276 (2018)","journal-title":"Inf. Comput."},{"key":"1_CR62","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-319-19225-3_13","volume-title":"Descriptional Complexity of Formal Systems","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M., Wendlandt, M.: On simulation cost of unary limited automata. In: Shallit, J., Okhotin, A. (eds.) DCFS 2015. LNCS, vol. 9118, pp. 153\u2013164. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-19225-3_13"},{"issue":"6","key":"1_CR63","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/S0020-0190(02)00436-2","volume":"85","author":"Y Lifshits","year":"2003","unstructured":"Lifshits, Y.: A lower bound on the size of $$\\epsilon $$-free NFA corresponding to a regular expression. Inform. Process. Lett. 85(6), 293\u2013299 (2003)","journal-title":"Inform. Process. Lett."},{"key":"1_CR64","unstructured":"Lupanov, O.B.: A comparison of two types of finite sources. Problemy Kybernetiki 9, 321\u2013326 (1963). (in Russian), German translation: \u00dcber den Vergleich zweier Typen endlicher Quellen. Probleme der Kybernetik 6 (1966), 328\u2013335"},{"key":"1_CR65","doi-asserted-by":"crossref","unstructured":"Manca, V.: On the generative power of iterated transductions. In: Ito, M., P\u0103un, G., Yu, S. (eds.) Words, Semigroups, and Transductions - Festschrift in Honor of Gabriel Thierrin, pp. 315\u2013327. World Scientific (2001)","DOI":"10.1142\/9789812810908_0024"},{"key":"1_CR66","unstructured":"Maslov, A.N.: Estimates of the number of states of finite automata. Dokllady Akademii Nauk SSSR 194, 1266\u20131268 (1970). (in Russian). English translation in Soviet Mathematics Doklady, 11, 1373\u20131375 (1970)"},{"key":"1_CR67","doi-asserted-by":"publisher","first-page":"1045","DOI":"10.1002\/j.1538-7305.1955.tb03788.x","volume":"34","author":"GH Mealy","year":"1955","unstructured":"Mealy, G.H.: A method for synthesizing sequential circuits. Bell Syst. Tech. J. 34, 1045\u20131079 (1955)","journal-title":"Bell Syst. Tech. J."},{"key":"1_CR68","doi-asserted-by":"crossref","unstructured":"Meyer, A.R., Fischer, M.J.: Economy of description by automata, grammars, and formal systems. In: Symposium on Switching and Automata Theory (SWAT 1971), pp. 188\u2013191. IEEE (1971)","DOI":"10.1109\/SWAT.1971.11"},{"issue":"2","key":"1_CR69","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1016\/0020-0190(81)90012-0","volume":"12","author":"S Micali","year":"1981","unstructured":"Micali, S.: Two-way deterministic finite automata are exponentially more succinct than sweeping automata. Inf. Process. Lett. 12(2), 103\u2013105 (1981)","journal-title":"Inf. Process. Lett."},{"issue":"10","key":"1_CR70","doi-asserted-by":"publisher","first-page":"1211","DOI":"10.1109\/T-C.1971.223108","volume":"20","author":"FR Moore","year":"1971","unstructured":"Moore, F.R.: On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 20(10), 1211\u20131214 (1971)","journal-title":"IEEE Trans. Comput."},{"key":"1_CR71","unstructured":"Nicaud, C.: \u00c9tude du comportement en moyenne des automates finis et des langages rationnels. Ph.D. thesis, Universit\u00e9 de Paris 7 (2000)"},{"key":"1_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-00982-2_53","volume-title":"Language and Automata Theory and Applications","author":"C Nicaud","year":"2009","unstructured":"Nicaud, C.: On the average size of Glushkov\u2019s automata. In: Dediu, A.H., Ionescu, A.M., Mart\u00edn-Vide, C. (eds.) LATA 2009. LNCS, vol. 5457, pp. 626\u2013637. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-00982-2_53"},{"key":"1_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/978-3-662-44522-8_2","volume-title":"Mathematical Foundations of Computer Science 2014","author":"C Nicaud","year":"2014","unstructured":"Nicaud, C.: Random deterministic automata. In: Csuhaj-Varj\u00fa, E., Dietzfelbinger, M., \u00c9sik, Z. (eds.) MFCS 2014. LNCS, vol. 8634, pp. 5\u201323. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-44522-8_2"},{"key":"1_CR74","unstructured":"Pierce, A.: Decision Problems on Iterated Length-Preserving Transducers. Bachelor\u2019s thesis, SCS Carnegie Mellon University, Pittsburgh (2011)"},{"issue":"2\u20133","key":"1_CR75","doi-asserted-by":"publisher","first-page":"225","DOI":"10.3233\/FI-2013-879","volume":"126","author":"G Pighizzini","year":"2013","unstructured":"Pighizzini, G.: Two-way finite automata: old and recent results. Fundam. Inform. 126(2\u20133), 225\u2013246 (2013)","journal-title":"Fundam. Inform."},{"key":"1_CR76","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-030-23247-4_4","volume-title":"Descriptional Complexity of Formal Systems","author":"G Pighizzini","year":"2019","unstructured":"Pighizzini, G.: Limited automata: properties, complexity and variants. In: Hospod\u00e1r, M., Jir\u00e1skov\u00e1, G., Konstantinidis, S. (eds.) DCFS 2019. LNCS, vol. 11612, pp. 57\u201373. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-23247-4_4"},{"issue":"7","key":"1_CR77","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)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1\u20132","key":"1_CR78","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)","journal-title":"Fundam. Inform."},{"key":"1_CR79","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)","journal-title":"Inf. Comput."},{"key":"1_CR80","doi-asserted-by":"crossref","unstructured":"Priez, J.B.: Enumeration of minimal acyclic automata via generalized parking functions. In: FPSAC 2015. DMTCS, January 2015","DOI":"10.46298\/dmtcs.2471"},{"key":"1_CR81","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, 114\u2013125 (1959)","journal-title":"IBM J. Res. Dev."},{"key":"1_CR82","doi-asserted-by":"crossref","unstructured":"Sakoda, W.J., Sipser, M.: Nondeterminism and the size of two way finite automata. In: Lipton, R.J., Burkhard, W.A., Savitch, W.J., Friedman, E.P., Aho, A.V. (eds.) Proceedings of the 10th Annual ACM Symposium on Theory of Computing, 1\u20133 May 1978, San Diego, California, USA, pp. 275\u2013286. ACM (1978)","DOI":"10.1145\/800133.804357"},{"issue":"3","key":"1_CR83","first-page":"177","volume":"2","author":"K Salomaa","year":"1997","unstructured":"Salomaa, K., Yu, S.: NFA to DFA transformation for finite languages over arbitrary alphabets. J. Autom. Lang. Comb. 2(3), 177\u2013186 (1997)","journal-title":"J. Autom. Lang. Comb."},{"key":"1_CR84","volume-title":"Analysis of Algorithms","author":"R Sedgewick","year":"1996","unstructured":"Sedgewick, R., Flajolet, P.: Analysis of Algorithms. Addision-Wesley, Boston (1996)"},{"issue":"2","key":"1_CR85","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)","journal-title":"IBM J. Res. Dev."},{"issue":"2","key":"1_CR86","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)","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR87","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0019-9958(67)90591-8","volume":"11","author":"RE Stearns","year":"1967","unstructured":"Stearns, R.E.: A regularity test for pushdown machines. Inform. Control 11, 323\u2013340 (1967)","journal-title":"Inform. Control"},{"key":"1_CR88","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/321864.321865","volume":"22","author":"LG Valiant","year":"1975","unstructured":"Valiant, L.G.: Regularity and related problems for deterministic pushdown automata. J. ACM 22, 1\u201310 (1975)","journal-title":"J. ACM"},{"issue":"5","key":"1_CR89","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0020-0190(89)90205-6","volume":"30","author":"MY Vardi","year":"1989","unstructured":"Vardi, M.Y.: A note on the reduction of two-way automata to one-way automata. Inf. Process. Lett. 30(5), 261\u2013264 (1989)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"1_CR90","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0020-0190(90)90063-4","volume":"35","author":"MY Vardi","year":"1990","unstructured":"Vardi, M.Y.: Endmarkers can make a difference. Inf. Process. Lett. 35(3), 145\u2013148 (1990)","journal-title":"Inf. Process. Lett."},{"key":"1_CR91","volume-title":"Computational Complexity","author":"KW Wagner","year":"1986","unstructured":"Wagner, K.W., Wechsung, G.: Computational Complexity. D. Reidel Publishing Company, Dordrecht (1986)"},{"key":"1_CR92","first-page":"221","volume":"6","author":"S Yu","year":"2001","unstructured":"Yu, S.: State complexity of regular languages. J. Autom. Lang. Comb. 6, 221\u2013234 (2001)","journal-title":"J. Autom. Lang. Comb."},{"issue":"2","key":"1_CR93","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. Theoret. Comput. Sci. 125(2), 315\u2013328 (1994)","journal-title":"Theoret. Comput. Sci."}],"container-title":["IFIP Advances in Information and Communication Technology","Advancing Research in Information and Communication Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-81701-5_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T22:02:31Z","timestamp":1754172151000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-81701-5_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030817008","9783030817015"],"references-count":93,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-81701-5_1","relation":{},"ISSN":["1868-4238","1868-422X"],"issn-type":[{"type":"print","value":"1868-4238"},{"type":"electronic","value":"1868-422X"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"4 August 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}