Automatic Groups and Knuth-Bendix with Infinitely Many Rules
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
It is shown how to use a small finite state automaton in two variables in order to carry out part of the Knuth--Bendix process for rewriting words in a group. The main objective is to provide a substitute for the most space-demanding module of the existing software which attempts to find a shortlex-automatic structure for a group. The two-variable automaton can be used to store an infinite set of rules and to carry out fast reduction of arbitrary words using this infinite set. We introduce a new operation, which we call welding, which applies to an arbitrary finite state automaton. In our context this operation is vital. We point out a small potential improvement in the subset algorithm for making a non-deterministic automaton deterministic.
41 pages. In LaTeX2e using the packages amsmath, amssymb, xspace, epic. Submitted to Internat. J. Algebra Comput
41 pages. In LaTeX2e using the packages amsmath, amssymb, xspace, epic. Submitted to Internat. J. Algebra Comput