# Krohn-Rhodes

Algebraic hierarchical decomposition of finite state automata: Comparison of implementations for Krohn-Rhodes theory. The hierarchical algebraic decomposition of finite state automata (Krohn-Rhodes Theory) has been a mathematical theory without any computational implementations until the present paper, although several possible and promising practical applications, such as automated object-oriented programming in software development, formal methods for understanding in artificial intelligence, and a widely applicable integer-valued complexity measure, have been described. As a remedy for the situation, our new implementation, described here, is freely available as open-source software. We also present two different computer algebraic implementations of the Krohn-Rhodes decomposition, the V∪T and holonomy decompositions, and compare their efficiency in terms of the number of hierarchical levels in the resulting cascade decompositions.

## References in zbMATH (referenced in 4 articles )

Showing results 1 to 4 of 4.

Sorted by year (- Egri-Nagy, Attila; Nehaniv, Chrystopher L.: On straight words and minimal permutators in finite transformation semigroups (2011)
- Egri-Nagy, Attila; Nehaniv, Chrystopher L.: On the skeleton of a finite transformation semigroup. (2010)
- Egri-Nagy, Attila; Nehaniv, Chrystopher L.: Finite residue class rings of integers modulo $n$ from the viewpoint of global semigroup theory (2007)
- Egri-Nagy, Attila; Nehaniv, Chrystopher L.: Algebraic hierarchical decomposition of finite state automata: Comparison of implementations for Krohn-Rhodes theory (2005)