On simplicity-critical Moore automata. I (Q1112614)

The paper contains some contributions to the problem of simplicity of finite Moore automata. The main result is as follows: An automaton A is not simple iff A has a (possibly non-proper) subautomaton B such that one of the three statements (A), (B) and (C) is valid for B: (A) B is strongly connected and non-simple. (B) B is strongly simplicity-critical, i.e., (1) B is not strongly connected; (2) B is not simple; (3) each maximal subautomaton of B is simple; (4) the subautomata of B are pairwise non-isomorphic. (C) B is weakly simplicity-critical, i.e., (3) is valid for B; (5) the number of maximal subautomata of B equals two; (6) the maximal subautomata of B are isomorphic.