Journalartikel

Jahr der Veröffentlichung: 2022

Seiten: 163-181

Zeitschrift: Acta Informatica

Bandnummer: 59

Heftnummer: 1

ISSN: 0001-5903

eISSN: 1432-0525

Open Access Status: Hybrid

DOI Link: https://doi.org/10.1007/s00236-021-00402-0

Verlag: Springer

Abstract: 
We investigate finite automata whose state graphs are undirected. This means that for any transition from state p to q consuming some letter a from the input there exists a symmetric transition from state q to p consuming a letter a 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.

Harvard-Zitierstil: Kutrib, M., Malcher, A. and Schneider, C. (2022) Finite automata with undirected state graphs, Acta Informatica, 59(1), pp. 163-181. https://doi.org/10.1007/s00236-021-00402-0

APA-Zitierstil: Kutrib, M., Malcher, A., & Schneider, C. (2022). Finite automata with undirected state graphs. Acta Informatica. 59(1), 163-181. https://doi.org/10.1007/s00236-021-00402-0