×

zbMATH — the first resource for mathematics

Algebraic hierarchical decomposition of finite state automata: Comparison of implementations for Krohn-Rhodes theory. (English) Zbl 1115.68429
Domaratzki, Michael (ed.) et al., Implementation and application of automata. 9th international conference, CIAA 2004, Kingston, Canada, July 22–24, 2004. Revised selected papers. Berlin: Springer (ISBN 3-540-24318-6/pbk). Lecture Notes in Computer Science 3317, 315-316 (2005).
Summary: 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\cup T\) and holonomy decompositions, and compare their efficiency in terms of the number of hierarchical levels in the resulting cascade decompositions.
For the entire collection see [Zbl 1063.68004].

MSC:
68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
68W30 Symbolic computation and algebraic computation
Software:
GAP; Krohn-Rhodes
PDF BibTeX XML Cite
Full Text: DOI