Abstract
This paper is a continuation of the study of the permutation rank of an automaton as was initiated in Smit [2]. The p 2 permutation r 2(A) of an automaton A is defined as the largest integer k such that (i) every subset of the state set of A consisting of k different states can be distinguished by an input; (ii) every input to A distinguishes k states of A. If x is an input string the expression “x distinguishes k states” means that k different states change to k different states which need not be the same as the original k states under the input x. The p 2 -permutation rank of a permutation automaton will always be equal to the number of states of the automaton. The semigroup of a permutation automaton is a group. It is shown that certain group properties are preserved in the semigroup of an automaton A of which r 2 (A) is restricted. The role of r 2 (A) in the semigroup of a strictly connected automaton is considered. As is in the case of Smit [2], it is shown that if r 2 (A) differs with only one from the number of states of A, then the semigroup of A is also the union of a finite number of mutually disjoint groups where the maximum number of groups depends on the number of states of A. In conclusion a comparison is made between the p 2-permutation rank (Smit [2]) and the p 2-permutation rank of an automaton.
C.R. Categories: