{
  "id": "math/0001035",
  "version": "v1",
  "published": "2000-01-06T16:24:11.000Z",
  "updated": "2000-01-06T16:24:11.000Z",
  "title": "Knuth-Bendix for groups with infinitely many rules",
  "authors": [
    "D. B. A. Epstein",
    "P. J. Sanders"
  ],
  "comment": "63 pages, 6 figures. A completely rewritten version of math/9805057. A slightly shortened version of this paper has been accepted by IJAC",
  "categories": [
    "math.GR"
  ],
  "abstract": "It is shown how to use a small finite state automaton in two variables in order to carry out the Knuth-Bendix process for rewriting words in a group in shortlex order. 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. We show how to improve on the standard subset construction to determinize a non-deterministic automaton under special conditions which hold in our situation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2000-01-06T16:24:11.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "20-04",
      "68Q42",
      "03D40",
      "20F32"
    ],
    "keywords": [
      "infinite set",
      "arbitrary finite state automaton",
      "small finite state automaton",
      "standard subset construction",
      "non-deterministic automaton"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 63,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math......1035E"
    }
  }
}