Automatic Groups and Knuth-Bendix with Infinitely Many Rules
From MaRDI portal
Publication:6500898
arXivmath/9805057MaRDI QIDQ6500898FDOQ6500898
Authors: David B. A. Epstein, Paul J. Sanders 
Abstract: 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.
Grammars and rewriting systems (68Q42) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Software, source code, etc. for problems pertaining to group theory (20-04) Word problems, etc. in computability and recursion theory (03D40)
This page was built for publication: Automatic Groups and Knuth-Bendix with Infinitely Many Rules
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6500898)
