On Krohn-Rhodes theory for semiautomata

Publikationstyp
Preprint
Date Issued
2020-10-30
Sprache
English
Author(s)
Zimmermann, Karl-Heinz  
Institut
Eingebettete Systeme E-13  
TORE-URI
http://hdl.handle.net/11420/8285
Citation
arXiv: 2010.16235 (2020)
Publisher DOI
10.48550/arXiv.2010.16235
ArXiv ID
2010.16235
Krohn-Rhodes theory encompasses the techniques for the study of finite automata and their decomposition into elementary automata. The famous result of Krohn and Rhodes roughly states that each finite automaton can be decomposed into elementary components which correspond to permutation and reset automata connected by a cascade product. However, this outcome is not easy to access for the working computer scientist. This paper provides a short introduction into Krohn-Rhodes theory based on the valuable work of Ginzburg.
Subjects
cs.FL
cs.FL
68Q70, 20M35, 20A05