TY - JOUR

T1 - String rewriting for double coset systems

AU - Brown, Ronald

AU - Heyworth, Anne

AU - Ghani, Neil

AU - Wensley, Christopher D.

PY - 2006

Y1 - 2006

N2 - 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 then 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 hjow 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.

AB - 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 then 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 hjow 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.

KW - double cosets, string rewriting, Knuth-Bendix, induced actions, left Kan extension

U2 - 10.1016/j.jsc.2005.10.004

DO - 10.1016/j.jsc.2005.10.004

M3 - Article

VL - 41

SP - 573

EP - 590

JO - Journal of Symbolic Computation

JF - Journal of Symbolic Computation

ER -