{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:25:31Z","timestamp":1740108331257,"version":"3.37.3"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,5,24]],"date-time":"2021-05-24T00:00:00Z","timestamp":1621814400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,5,24]],"date-time":"2021-05-24T00:00:00Z","timestamp":1621814400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Justus-Liebig-Universit\u00e4t Gie\u00dfen"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2022,2]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate finite automata whose state graphs are undirected. This means that for any transition from state <jats:italic>p<\/jats:italic> to <jats:italic>q<\/jats:italic> consuming some letter <jats:italic>a<\/jats:italic> from the input there exists a symmetric transition from state <jats:italic>q<\/jats:italic> to <jats:italic>p<\/jats:italic> consuming a letter <jats:italic>a<\/jats:italic> as well. So, the corresponding language families are subregular, and in particular in the deterministic case, subreversible. In detail, we study the operational descriptional complexity of deterministic and nondeterministic undirected finite automata. To this end, the different types of automata on alphabets with few letters are characterized. Then, the operational state complexity of the Boolean operations as well as the operations concatenation and iteration is investigated, where tight upper and lower bounds are derived for unary as well as arbitrary alphabets under the condition that the corresponding language classes are closed under the operation considered.<\/jats:p>","DOI":"10.1007\/s00236-021-00402-0","type":"journal-article","created":{"date-parts":[[2021,5,24]],"date-time":"2021-05-24T19:02:27Z","timestamp":1621882947000},"page":"163-181","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Finite automata with undirected state graphs"],"prefix":"10.1007","volume":"59","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9564-2625","authenticated-orcid":false,"given":"Martin","family":"Kutrib","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9589-5833","authenticated-orcid":false,"given":"Andreas","family":"Malcher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christian","family":"Schneider","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,5,24]]},"reference":[{"key":"402_CR1","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":"402_CR2","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1006\/inco.1997.2688","volume":"140","author":"A Br\u00fcggemann-Klein","year":"1998","unstructured":"Br\u00fcggemann-Klein, A., Wood, D.: One-unambiguous regular languages. Inform. Comput. 140, 229\u2013253 (1998)","journal-title":"Inform. Comput."},{"key":"402_CR3","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1016\/j.jcss.2012.01.006","volume":"78","author":"A Gajardo","year":"2012","unstructured":"Gajardo, A., Kari, J., Moreira, A.: On time-symmetry in cellular automata. J. Comput. Syst. Sci. 78, 1115\u20131126 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"402_CR4","first-page":"251","volume":"21","author":"Y Gao","year":"2016","unstructured":"Gao, Y., Moreira, N., Reis, R., Yu, S.: A survey on operational state complexity. J. Autom. Lang. Comb. 21, 251\u2013310 (2016)","journal-title":"J. Autom. Lang. Comb."},{"key":"402_CR5","first-page":"400","volume":"5","author":"IM Havel","year":"1969","unstructured":"Havel, I.M.: The theory of regular events I. Kybernetica 5, 400\u2013419 (1969)","journal-title":"Kybernetica"},{"key":"402_CR6","first-page":"520","volume":"6","author":"IM Havel","year":"1969","unstructured":"Havel, I.M.: The theory of regular events II. Kybernetica 6, 520\u2013544 (1969)","journal-title":"Kybernetica"},{"key":"402_CR7","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1142\/S0129054118400063","volume":"29","author":"M Holzer","year":"2018","unstructured":"Holzer, M., Jakobi, S., Kutrib, M.: Minimal reversible deterministic finite automata. Int. J. Found. Comput. Sci. 29, 251\u2013270 (2018)","journal-title":"Int. J. Found. Comput. Sci."},{"key":"402_CR8","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/978-3-319-59936-6_3","volume-title":"Reversible Computation (RC 2017)","author":"M Holzer","year":"2017","unstructured":"Holzer, M., Kutrib, M.: Reversible nondeterministic finite automata. In: Phillips, I., Rahaman, H. (eds.) Reversible Computation (RC 2017). LNCS, vol. 10301, pp. 35\u201351. Springer, Berlin (2017)"},{"key":"402_CR9","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/978-3-662-48057-1_3","volume-title":"Mathematical Foundations of Computer Science (MFCS 2015)","author":"M Kutrib","year":"2015","unstructured":"Kutrib, M.: Reversible and irreversible computations of deterministic finite-state devices. In: Italiano, G.F., Pighizzini, G., Sannella, D. (eds.) Mathematical Foundations of Computer Science (MFCS 2015). LNCS, vol. 9234, pp. 38\u201352. Springer, Berlin (2015)"},{"key":"402_CR10","series-title":"LNCS","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-319-94631-3_18","volume-title":"Descriptional Complexity of Formal Systems (DCFS 2018)","author":"M Kutrib","year":"2018","unstructured":"Kutrib, M., Malcher, A., Schneider, C.: Finite automata with undirected state graphs. In: Konstantinidis, S., Pighizzini, G. (eds.) Descriptional Complexity of Formal Systems (DCFS 2018). LNCS, vol. 10952, pp. 212\u2013223. Springer, Berlin (2018)"},{"key":"402_CR11","doi-asserted-by":"crossref","unstructured":"Kutrib, M., Worsch, T.: Time-symmetric machines. In: Dueck, G.W., Miller, D.M. (eds.) Reversible Computation (RC 2013), LNCS, vol. 7948, pp. 168\u2013181. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-38986-3_14"},{"key":"402_CR12","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1147\/rd.53.0183","volume":"5","author":"R Landauer","year":"1961","unstructured":"Landauer, R.: Irreversibility and heat generation in the computing process. IBM J. Res. Dev. 5, 183\u2013191 (1961)","journal-title":"IBM J. Res. Dev."},{"key":"402_CR13","doi-asserted-by":"crossref","unstructured":"Lavado, G.J., Pighizzini, G., Prigioniero, L.: Weakly and strongly irreversible regular languages. In: Csuhaj-Varj\u00fa, E., D\u00f6m\u00f6si, P., Vaszil, G. (eds.) Automata and Formal Languages (AFL 2017). EPTCS, vol. 252, pp. 143\u2013156 (2017)","DOI":"10.4204\/EPTCS.252.15"},{"key":"402_CR14","doi-asserted-by":"crossref","unstructured":"Yu, S.: Regular languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, vol. 1, Chapter 2, pp. 41\u2013110. Springer, Berlin (1997)","DOI":"10.1007\/978-3-642-59136-5_2"},{"key":"402_CR15","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."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00402-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-021-00402-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-021-00402-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,17]],"date-time":"2022-02-17T11:10:17Z","timestamp":1645096217000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-021-00402-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,24]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["402"],"URL":"https:\/\/doi.org\/10.1007\/s00236-021-00402-0","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2021,5,24]]},"assertion":[{"value":"13 February 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 May 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}