The permutation rank of an automaton i

Abstract

The p ₁-permutation rank r ₁(A) of an automaton A is defined as the number of states in its maximal homomorphic image which is a permutation automaton (maximal refers to the number of states in the automaton). The p ₁-permutation rank of a permutation automaton will then always be equal to the number of states of the automaton. It is shown that if r ₁(A) = k then a homomorphism exists from the semigroup of A onto a group of order at most k! It is well known that the semigroup of a permutation automaton is a group. One would expect that certain group properties will be preserved in the semigroup of an automaton A of which r ₁(A) differs with only one from the number of states of A. In this case it is shown that the semigroup of A is the union of at most three mutually disjoint groups. It follows that the P ₁-permutation rank may be considered as an indication of the degree of deviance of an automaton from a permutation automaton.

Keywords:

• Finite automata
• permutation automata
• permutation rank
• semi-group of an automaton

C.R. Categories:

• F.1.1.