Congruences et Automorphismes des Automates Finis |
| |
Authors: | D. Perrin J. F. Perrot |
| |
Affiliation: | (1) Départment de Mathématiques, Université de Paris VII, France;(2) Institut de Programmation, Université de Paris VI, F-75 Paris V, France |
| |
Abstract: | Summary We study a class of congruences of strongly connected finite automata, called the group congruences, which may be defined in this way: every element fixing any class of the congruence induces a permutation on this class. These congruences form an ideal of the lattice of all congruences of the automaton and we study the group associated with the maximal group congruence (maximal induced group) with respect to the Suschkevitch group of the transition monoid of . The transitivity equivalence of the subgroups of the automorphism group of are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of . We then characterize the automorphism group of with respect to the maximal induced group. As an application, we show that, given a group G and an automaton , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|