Congruences et Automorphismes des Automates Finis期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

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 $\mathfrak{A}$ 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 $\mathfrak{A}$ . The transitivity equivalence of the subgroups of the automorphism group of $\mathfrak{A}$ are found to be the group congruences associated with regular groups, which form also in ideal of the lattice of congruences of $\mathfrak{A}$ . We then characterize the automorphism group of $\mathfrak{A}$ with respect to the maximal induced group. As an application, we show that, given a group G and an automaton $\mathfrak{A}$ , there exists an automaton whose automorphism group is isomorphic to G and such that the quotient by the automorphism congruence is $\mathfrak{A}$ .

Keywords:
本文献已被 SpringerLink 等数据库收录！