arXiv Analytics

Sign in

Search ResultsShowing 1-8 of 8

Sort by
  1. arXiv:math/0508391 (Published 2005-08-21)

    String rewriting for Double Coset Systems

    Ronald Brown, Neil Ghani, Anne Heyworth, Christopher D. Wensley
    Comments: accepted for publication by the Journal of Symbolic Computation
    Categories: math.CO, math.GR
    Subjects: 20F05, 20F10

    In this paper we show how string rewriting methods can be applied to give a new method of computing double cosets. Previous methods for double cosets were enumerative and thus restricted to finite examples. Our rewriting methods do not suffer this restriction and we present some examples of infinite double coset systems which can now easily be solved using our approach. Even when both enumerative and rewriting techniques are present, our rewriting methods will be competitive because they i) do not require the preliminary calculation of cosets; and ii) as with single coset problems, there are many examples for which rewriting is more effective than enumeration. Automata provide the means for identifying expressions for normal forms in infinite situations and we show how they may be constructed in this setting. Further, related results on logged string rewriting for monoid presentations are exploited to show how witnesses for the computations can be provided and how information about the subgroups and the relations between them can be extracted. Finally, we discuss how the double coset problem is a special case of the problem of computing induced actions of categories which demonstrates that our rewriting methods are applicable to a much wider class of problems than just the double coset problem.

  2. arXiv:math/0003080 (Published 2000-03-14)

    Grobner Basis Techniques for Computing Actions of K-Categories

    Anne Heyworth
    Comments: 10 pages LaTeX, (submitted CT2000)
    Categories: math.CO
    Subjects: 68Q40, 68Q42

    This paper involves categories and computer science. The paper is motivated by a question which arises from two pieces of research. Firstly, the work of Brown and Heyworth which extends rewriting techniques to enable the computation of left Kan extensions over the category of sets. It is well known that left Kan extensions can be defined over categories other than Sets. Secondly, the `folklore' that rewriting theory is a special case of noncommutative Groebner basis theory. It is therefore natural to ask whether Groebner bases can provide a method for computing Kan extensions beyond the special case of rewriting. To answer this question completely, fully exploiting the computational power of Groebner basis techniques relating to Kan extensions is the ultimate aim. This paper provides a first step by showing how standard noncommutative Groebner basis procedures can be used to calculate left Kan extensions of K-category actions. In the final section of the paper a number of interesting problems arising from the work are identified.

  3. arXiv:math/0002119 (Published 2000-02-15)

    Groebner Basis Procedures for Testing Petri Nets

    Angie Chandler, Anne Heyworth
    Comments: 13 pages, Latex with 3 diagrams as eps files
    Categories: math.CO, math.OC
    Subjects: 60R05, 90C35

    This paper contains introductory material on Petri nets and Groebner basis theory and makes some observations on the relation between the two areas. The aim of the paper is to show how Groebner basis procedures can be applied to the problem of reachability in Petri nets, and to give details of an application to testing models of navigational systems.

  4. arXiv:math/9907083 (Published 1999-07-13, updated 2005-05-10)

    Rewriting Procedures Generalise to Kan Extensions of Actions of Categories

    Anne Heyworth
    Comments: 9 pages, LaTeX2e, (extended abstract FLoC/RTA'99). Replacement (v2) has correct LaTeX source file for submission (source for math/9907082 was accidently submitted as v1)
    Categories: math.CO
    Subjects: 18A40, 68Q40, 68Q42

    Kan extensions provide a natural general framework for a variety of combinatorial problems. We have developed rewriting procedures for Kan extensions (over the category of sets) and this enables one program to address a wide range of problems. Thus it is possible to use the same framework (and therefore program) to enumerate monoid or group (or category of groupoid) elements, to enumerate cosets or congruence classes on monoids, calculate equivariant equivalence relations, induced actions of groups, monoids or categories and even more. This extended abstract is an outline of "Using Rewriting Systems to Compute Kan Extensions and Induced Actions of Categories" by R. Brown and A. Heyworth.

  5. arXiv:math/9907082 (Published 1999-07-13)

    Logged Rewriting Procedures with Application to Identities Among Relations

    Anne Heyworth, Christopher D Wensley
    Comments: 17 pages, LaTeX2e, (submitted to LMS)
    Categories: math.CO
    Subjects: 16S15, 18G10, 20F05, 68Q40, 68Q42

    The key idea is that rewriting procedures can be enhanced so that they not only rewrite words but record (log) how the rewriting has taken place. We introduce logged rewrite systems and present a variation on the Knuth-Bendix algorithm for obtaining (where possible) complete logged rewrite systems. This procedure is then applied to work of Brown and Razak Salleh, and an algorithm is developed which provides a set of generators for the module of identities among relations of a group presentation.

  6. arXiv:math/9906153 (Published 1999-06-23)

    Using Automata to obtain Regular Expressions for Induced Actions

    Anne Heyworth
    Comments: 14 pages, LaTeX2e, (submitted to IJAC)
    Categories: math.CO
    Subjects: 08A50, 16B50, 68Q40, 68Q42, 68Q45

    Presentations of Kan extensions of category actions provide a natural framework for expressing induced actions, and therefore a range of different combinatorial problems. Rewrite systems for Kan extensions have been defined and a variation on the Knuth-Bendix completion procedure can be used to complete them -- when possible. Regular languages and automata are a useful way of expressing sets and actions, and in this paper we explain how to use rewrite systems for Kan extensions to construct automata expressing the induced action and how sets of normal forms can be calculated by obtaining language equations from the automata.

  7. arXiv:math/9903032 (Published 1999-03-05)

    Using Rewriting Systems to Compute Kan Extensions and Induced Actions of Categories

    Ronald Brown, Anne Heyworth
    Comments: 31 pages, LaTeX2e, (submitted to JSC)
    Categories: math.CO
    Subjects: 68Q42, 18A40, 68Q40

    The basic method of rewriting for words in a free monoid given a monoid presentation is extended to rewriting for paths in a free category given a `Kan extension presentation'. This is related to work of Carmody-Walters on the Todd-Coxeter procedure for Kan extensions, but allows for the output data to be infinite, described by a language. The result also allows rewrite methods to be applied in a greater range of situations and examples, in terms of induced actions of monoids, categories, groups or groupoids.

  8. arXiv:math/9901044 (Published 1999-01-11)

    Rewriting as a Special Case of Noncommutative Groebner Basis Theory

    Anne Heyworth
    Comments: article, 4 pages, LaTeX2e
    Categories: math.CO
    Subjects: 68Q42, 16S15, 68Q40

    Rewriting for semigroups is a special case of Groebner basis theory for noncommutative polynomial algebras. The fact is a kind of folklore but is not fully recognised. The aim of this paper is to elucidate this relationship, showing that the noncommutative Buchberger algorithm corresponds step-by-step to the Knuth-Bendix completion procedure.