On Calculating the Krohn–Rhodes Decomposition of Automata

✍ Scribed by Sunil Talwar

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 336 KB
• Volume: 19
• Category: Article
• ISSN: 0196-8858
• DOI: 10.1006/aama.1997.0547

✦ Synopsis

DEDICATED TO M.-P. SCHUTZENBERGER

The Krohn᎐Rhodes prime decomposition theorem determines the building blocks and their combination so as to mimic any given automaton. This result 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 complexity 1 is decidable. We exhibit an application to game theory. ᮊ 1997 Academic Press 1 m set of states, q 1 g Q is the initial state, : Q ª B is the output function, and

M on the same sequence of inputs. An automaton is said to be a group 2 automaton if each input induces a permutation of states. The two state reset automaton is simply an on᎐off switch, with the addition of the Ž . identity transformation see Fig. 1 . By series and parallel we mean the w x usual as in Fig. 2. The proof of Krohn and Rhodes 14 is algorithmic. A 251