ON CALCULATING THE KROHN-RHODES DECOMPOSITION OF AUTOMATA

The Krohn-Rhodes prime decomposition theorem determines the building b lock and their combination so as to mimic any given automaton. This re sult leads to an intuitively appealing, integer valued measure of the complexity of an automaton. It is a long-standing open question as to whether complexity is decidable. In this article, we show that complex ity 1 is decidable. We exhibit an application to game theory. (C) 1997 Academic Press.