Bass-Tits minimization of automata, quotients of trees and diameters |
| |
Authors: | Lisa Carbone Dennis Clark |
| |
Institution: | Department of Mathematics, Rutgers, The State University, 110 Freling Huysen Road, Piscataway, NJ 08854-8019, USA |
| |
Abstract: | Let X be a tree and let G=Aut(X), Bass and Tits have given an algorithm to construct the ‘ultimate quotient’ of X by G starting with any quotient of X, an ‘edge-indexed’ graph. Using a sequence of integers that we compute at consecutive steps of the Bass-Tits (BT) algorithm, we give a lower bound on the diameter of the ultimate quotient of a tree by its automorphism group. For a tree X with finite quotient, this gives a lower bound on the minimum number of generators of a uniform X-lattice whose quotient graph coincides with G?X. This also gives a criterion to determine if the ultimate quotient of a tree is infinite. We construct an edge-indexed graph (A,i) for a deterministic finite state automaton and show that the BT algorithm for computing the ultimate quotient of (A,i) coincides with state minimizing algorithm for finite state automata. We obtain a lower bound on the minimum number of states of the minimized automaton. This gives a new proof that language for the word problem in a finitely generated group is regular if and only if the group is finite, and a new proof that the language of the membership problem for a subgroup is regular if and only if the subgroup has finite index. |
| |
Keywords: | Primary: 20F32 secondary: 22F50 |
本文献已被 ScienceDirect 等数据库收录! |
|