Equational axioms associated with finite automatarnfor fixed point operations in cartesian categories

摘要

The axioms of iteration theories, or iteration categories, capture the equational properties ofrnfixed point operations in several computationally significant categories. Iteration categoriesrnmay be axiomatized by the Conway identities and identities associated with finite automata.rnWe show that the Conway identities and the identities associated with the members of arnsubclass Q of finite automata is complete for iteration categories iff for every finite simplerngroup G there is an automaton Q ∈ Q such that G is a quotient of a group in the monoidrnM(Q) of the automaton Q. We also prove a stronger result that concerns identitiesrnassociated with finite automata with a distinguished initial state.