% generated by GAPDoc2LaTeX from XML source (Frank Luebeck)
\documentclass[a4paper,11pt]{report}
\usepackage{a4wide}
\sloppy
\pagestyle{myheadings}
\usepackage{amssymb}
\usepackage[latin1]{inputenc}
\usepackage{makeidx}
\makeindex
\usepackage{color}
\definecolor{DarkOlive}{rgb}{0.1047,0.2412,0.0064}
\definecolor{FireBrick}{rgb}{0.5812,0.0074,0.0083}
\definecolor{RoyalBlue}{rgb}{0.0236,0.0894,0.6179}
\definecolor{RoyalGreen}{rgb}{0.0236,0.6179,0.0894}
\definecolor{RoyalRed}{rgb}{0.6179,0.0236,0.0894}
\definecolor{LightBlue}{rgb}{0.8544,0.9511,1.0000}
\definecolor{Black}{rgb}{0.0,0.0,0.0}
\definecolor{FuncColor}{rgb}{1.0,0.0,0.0}
%% strange name because of pdflatex bug:
\definecolor{Chapter }{rgb}{0.0,0.0,1.0}

\usepackage{fancyvrb}

\usepackage{pslatex}

\usepackage[pdftex=true,
        a4paper=true,bookmarks=false,pdftitle={Written with GAPDoc},
        pdfcreator={LaTeX with hyperref package / GAPDoc},
        colorlinks=true,backref=page,breaklinks=true,linkcolor=RoyalBlue,
        citecolor=RoyalGreen,filecolor=RoyalRed,
        urlcolor=RoyalRed,pagecolor=RoyalBlue]{hyperref}

% write page numbers to a .pnr log file for online help
\newwrite\pagenrlog
\immediate\openout\pagenrlog =\jobname.pnr
\immediate\write\pagenrlog{PAGENRS := [}
\newcommand{\logpage}[1]{\protect\write\pagenrlog{#1, \thepage,}}
%% were never documented, give conflicts with some additional packages


\newcommand{\GAP}{\textsf{GAP}}

\begin{document}

\logpage{[ 0, 0, 0 ]}
\begin{titlepage}
\begin{center}{\Huge \textbf{\textsf{kan}\mbox{}}}\\[1cm]
\hypersetup{pdftitle=\textsf{kan}}
\markright{\scriptsize \mbox{}\hfill \textsf{kan} \hfill\mbox{}}
{\Large \textbf{A package for Induced Category Actions\mbox{}}}\\[1cm]
{Version 0.97\mbox{}}\\[1cm]
{November 2008\mbox{}}\\[1cm]
\mbox{}\\[2cm]
{\large \textbf{ Anne Heyworth  \mbox{}}}\\
{\large \textbf{ Chris Wensley    \mbox{}}}\\
\hypersetup{pdfauthor= Anne Heyworth  ;  Chris Wensley    }
\end{center}\vfill

\mbox{}\\
{\mbox{}\\
\small \noindent \textbf{ Anne Heyworth  } --- Email: \href{mailto://anne.heyworth@googlemail.com} {\texttt{anne.heyworth@googlemail.com}}}\\
{\mbox{}\\
\small \noindent \textbf{ Chris Wensley    } --- Email: \href{mailto://c.d.wensley@bangor.ac.uk} {\texttt{c.d.wensley@bangor.ac.uk}}\\
 --- Homepage: \href{http://www.bangor.ac.uk/~mas023/} {\texttt{http://www.bangor.ac.uk/\texttt{\symbol{126}}mas023/}}\\
 --- Address: \begin{minipage}[t]{8cm}\noindent
 School of Computer Science, Bangor University,\\
 Dean Street, Bangor, Gwynedd, LL57 1UT, U.K. \end{minipage}
}\\
\end{titlepage}

\newpage\setcounter{page}{2}
{\small 
\section*{Abstract}
\logpage{[ 0, 0, 1 ]}
 The \textsf{kan} package was originally implemented in 1997 using the \textsf{GAP} 3 language, to compute induced actions of categories, when the first author
was studying for a Ph.D. in Bangor. 

 This reduced version only provides functions for the computation of normal
forms of representatives of double cosets of finitely presented groups. 

 Bug reports, suggestions and comments are, of course, welcome. Please contact
the second author at \href{mailto://c.d.wensley@bangor.ac.uk} {\texttt{c.d.wensley@bangor.ac.uk}}. \mbox{}}\\[1cm]
{\small 
\section*{Copyright}
\logpage{[ 0, 0, 2 ]}
 {\copyright} 2005-2008 Anne Heyworth and Chris Wensley 

 \mbox{}}\\[1cm]
{\small 
\section*{Acknowledgements}
\logpage{[ 0, 0, 3 ]}
 This \textsf{kan} package is released under the GNU General Public License (GPL). This file is
part of \textsf{kan}, though as documentation it is released under the GNU Free Documentation
License (see \href{http://www.gnu.org/licenses/licenses.html#FDL} {\texttt{http://www.gnu.org/licenses/licenses.html\#FDL}}). 

 \textsf{kan} is free software; you can redistribute it and/or modify it under the terms of
the GNU General Public License as published by the Free Software Foundation;
either version 2 of the License, or (at your option) any later version. 

 \textsf{kan} is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY;
without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
PARTICULAR PURPOSE. See the GNU General Public License for more details. 

 You should have received a copy of the GNU General Public License along with \textsf{kan}; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite
330, Boston, MA 02111-1307 USA. 

 For more details, see \href{http://www.fsf.org/licenses/gpl.html} {\texttt{http://www.fsf.org/licenses/gpl.html}}. 

 This documentation was prepared with the \textsf{GAPDoc} package of Frank L\texttt{\symbol{92}}"ubeck and Max
Neunh\texttt{\symbol{92}}"offer. \mbox{}}\\[1cm]
\newpage

\def\contentsname{Contents\logpage{[ 0, 0, 4 ]}}

\tableofcontents
\newpage

           
\chapter{\textcolor{Chapter }{Introduction}}\label{intro}
\logpage{[ 1, 0, 0 ]}
\hyperdef{L}{X7DFB63A97E67C0A1}{}
{
  The \textsf{kan} package started out as part of Anne Heyworth's thesis \cite{anne-thesis}\texttt{\symbol{125}}, and was designed to compute induced actions of
categories (see also \cite{BrHe}). 

 This version of \textsf{kan} only provides functions for the computation of normal forms of representatives
of double cosets of finitely presented groups, and is made available in
support of the paper \cite{BrGhHeWe}. Existing methods for computing double cosets in \textsf{GAP} are described in \cite{SteveL}. 

 The package is loaded into \textsf{GAP} with the command 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> LoadPackage( "kan" ); 
  
\end{Verbatim}
 This version of \textsf{kan} has been prepared for \textsf{GAP} 4.4.11. Some of the functions in the \textsf{automata} package are used to compute word acceptors and regular expressions for the
languages they accept. 

 The \textsf{kbmag} package is also used to compute a word acceptor of a group \texttt{G} when \texttt{G} has no finite rewriting system. If \textsf{kbmag} is not available (the user is not on a UNIX system, or the C-programs have not
been compiled), the file \texttt{dckbmag.gi} will not be read, so methods for the functions detailed in section 2.4.1 will
not be available. 

 The information parameter \texttt{InfoKan} takes default value \texttt{0}. When raised to a higher value, additional information is printed out. 

 Once the package is loaded, it is possible to check the installation is
correct by running the test suite of the package with the following command.
(The test file itself is \texttt{tst/kan{\textunderscore}manual.tst}.) 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> ReadPackage( "kan", "tst/testall.g" );
  + setting AssertionLevel to 0 to avoid recursion in Automata
  + Testing all example commands in the Kan manual
  + GAP4stones: 6
  true
  
\end{Verbatim}
 (If \textsf{kbmag} is not loaded then a collection of error lines for Example 3 will be printed
out.) 

 Please send bug reports, suggestions and other comments to the second author. 

 The \textsf{kan} package is subject to the \textsf{GAP} copyright regulations as detailed in the copyright notice in the \textsf{GAP} manual. }

           
\chapter{\textcolor{Chapter }{Double Coset Rewriting Systems}}\label{chap-dcrws}
\logpage{[ 2, 0, 0 ]}
\hyperdef{L}{X7F197C8D835A6F45}{}
{
  The \textsf{kan} package provides functions for the computation of normal forms for double
coset representatives of finitely presented groups. The first version of the
package was released to support the paper \cite{BrGhHeWe}, which describes the algorithms used in this package. 
\section{\textcolor{Chapter }{Rewriting Systems}}\logpage{[ 2, 1, 0 ]}
\hyperdef{L}{X7CA8FCFD81AA1890}{}
{
 

\subsection{\textcolor{Chapter }{KnuthBendixRewritingSystem}}
\logpage{[ 2, 1, 1 ]}\nobreak
\hyperdef{L}{X87A3823483E4FF86}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KnuthBendixRewritingSystem({\slshape grp, gensorder, ordering, alph})\index{KnuthBendixRewritingSystem@\texttt{KnuthBendixRewritingSystem}}
\label{KnuthBendixRewritingSystem}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{ReducedConfluentRewritingSystem({\slshape grp, gensorder, ordering, limit})\index{ReducedConfluentRewritingSystem@\texttt{ReducedConfluentRewritingSystem}}
\label{ReducedConfluentRewritingSystem}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DisplayRwsRules({\slshape rws})\index{DisplayRwsRules@\texttt{DisplayRwsRules}}
\label{DisplayRwsRules}
}\hfill{\scriptsize (operation)}}\\


 Methods for \texttt{KnuthBendixRewritingSystem} and \texttt{ReducedConfluentRewritingSystem} are supplied which apply to a finitely presented group. These start by calling \texttt{IsomorphismFpMonoid} and then work with the resulting monoid. The parameter \texttt{gensorder} will normally be \texttt{"shortlex"} or \texttt{"wreath"}, while \texttt{ordering} is an integer list for reordering the generators, and \texttt{alph} is an alphabet string used when printing words. A \emph{partial} rewriting system may be obtained by giving a \texttt{limit} to the number of rules calculated. As usual, $A,B$ denote the inverses of $a,b$. 

 In the example the generators are by default ordered $[A,a,B,b]$, so the list \texttt{L1} is used to specify the order \texttt{[a,A,b,B]} to be used with the shortlex ordering. Specifying a limit \texttt{0} means that no limit is prescribed. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> G1 := FreeGroup( 2 );;
  gap> L1 := [2,1,4,3];;
  gap> order := "shortlex";;
  gap> alph1 := "AaBb";;
  gap> rws1 := ReducedConfluentRewritingSystem( G1, L1, order, 0, alph1 );
  Rewriting System for Monoid( [ f1^-1, f1, f2^-1, f2 ], ... ) with rules
  [ [ f1^-1*f1, <identity ...> ], [ f1*f1^-1, <identity ...> ],
    [ f2^-1*f2, <identity ...> ], [ f2*f2^-1, <identity ...> ] ]
  gap> DisplayRwsRules( rws1 );;
  [ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ]
  
\end{Verbatim}
 }

 
\section{\textcolor{Chapter }{Example 1 -- free product of two cyclic groups}}\logpage{[ 2, 2, 0 ]}
\hyperdef{L}{X846F0B22859B601A}{}
{
 \index{example -- free product} 

\subsection{\textcolor{Chapter }{DoubleCosetRewritingSystem}}
\logpage{[ 2, 2, 1 ]}\nobreak
\hyperdef{L}{X825D1F4D85DE122D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DoubleCosetRewritingSystem({\slshape grp, genH, genK, rws})\index{DoubleCosetRewritingSystem@\texttt{DoubleCosetRewritingSystem}}
\label{DoubleCosetRewritingSystem}
}\hfill{\scriptsize (function)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsDoubleCosetRewritingSystem({\slshape dcrws})\index{IsDoubleCosetRewritingSystem@\texttt{IsDoubleCosetRewritingSystem}}
\label{IsDoubleCosetRewritingSystem}
}\hfill{\scriptsize (property)}}\\


 A \emph{double coset rewriting system} for the double cosets $H \backslash G / K$ requires as data a finitely presented group $G =$\texttt{grp}, generators \texttt{genH, genK} for subgroups $H, K$, and a rewriting system \texttt{rws} for $G$. 

 A simple example is given by taking $G$ to be the free group on two generators $a,b$, a cyclic subgroup $H$ with generator $a^6$, and a second cyclic subgroup $K$ with generator $a^4$. (Similar examples using different powers of $a$ are easily constructed.) Since \texttt{gcd(6,4)=2}, we have $Ha^2K=HK$, so the double cosets have representatives $[HK, HaK, Ha^iba^jK, Ha^ibwba^jK]$ where $i \in [0..5]$, $j \in [0..3]$, and $w$ is any word in $a,b$. 

 In the example the free group $G$ is converted to a four generator monoid with relations defining the inverse of
each generator, \texttt{[[Aa,id],[aA,id],[Bb,id],[bB,id]]}, where \texttt{id} is the empty word. The initial rules for the double coset rewriting system
comprise those of $G$ plus those given by the generators of $H,K$, which are $[[Ha^6,H],[a^4K,K]]$. In the complete rewrite system new rules involving $H$ or $K$ may arise, and there may also be rules involving both $H$ and $K$. 

 For this example, 
\begin{itemize}
\item  there are two $H$-rules, $[[Ha^4,HA^2],[HA^3,Ha^3]]$, 
\item  there are two $K$-rules, $[[a^3K,AK],[A^2K,a^2K]]$, 
\item  and there are two $H$-$K$-rules, $[[Ha^2K,HK],[HAK,HaK]]$. 
\end{itemize}
 Here is how the computation may be performed. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> genG1 := GeneratorsOfGroup( G1 );;
  gap> genH1 := [ genG1[1]^6 ];;
  gap> genK1 := [ genG1[1]^4 ];;
  gap> dcrws1 := DoubleCosetRewritingSystem( G1, genH1, genK1, rws1 );;
  gap> IsDoubleCosetRewritingSystem( dcrws1 );
  true
  gap> DisplayRwsRules( dcrws1 );;
  G-rules:
  [ [ Aa, id ], [ aA, id ], [ Bb, id ], [ bB, id ] ]
  H-rules:
  [ [ Haaaa, HAA ],
    [ HAAA, Haaa ] ]
  K-rules:
  [ [ aaaK, AK ],
    [ AAK, aaK ] ]
  H-K-rules:
  [ [ HaaK, HK ],
    [ HAK, HaK ] ]
  
\end{Verbatim}
 

\subsection{\textcolor{Chapter }{WordAcceptorOfReducedRws}}
\logpage{[ 2, 2, 2 ]}\nobreak
\hyperdef{L}{X83FF05087E7B133A}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordAcceptorOfReducedRws({\slshape rws})\index{WordAcceptorOfReducedRws@\texttt{WordAcceptorOfReducedRws}}
\label{WordAcceptorOfReducedRws}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordAcceptorOfDoubleCosetRws({\slshape rws})\index{WordAcceptorOfDoubleCosetRws@\texttt{WordAcceptorOfDoubleCosetRws}}
\label{WordAcceptorOfDoubleCosetRws}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IsWordAcceptorOfDoubleCosetRws({\slshape aut})\index{IsWordAcceptorOfDoubleCosetRws@\texttt{IsWordAcceptorOfDoubleCosetRws}}
\label{IsWordAcceptorOfDoubleCosetRws}
}\hfill{\scriptsize (property)}}\\


 Using functions from the \textsf{automata} package, we may 
\begin{itemize}
\item  compute a \emph{word acceptor} for the rewriting system of $G$; 
\item  compute a \emph{word acceptor} for the double coset rewriting system; 
\item  test a list of words to see whether they are recognised by the automaton; 
\item  obtain a rational expression for the language of the automaton. 
\end{itemize}
 }

 

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> waG1 := WordAcceptorOfReducedRws( rws1 );
  Automaton("nondet",6,"aAbB",[ [ [ 1 ], [ 4 ], [ 1 ], [ 4 ], [ 4 ], [ 4 ] ], [ \
  [ 1 ], [ 3 ], [ 3 ], [ 1 ], [ 3 ], [ 3 ] ], [ [ 1 ], [ 6 ], [ 6 ], [ 6 ], [ 1 \
  ], [ 6 ] ], [ [ 1 ], [ 5 ], [ 5 ], [ 5 ], [ 5 ], [ 1 ] ] ],[ 2 ],[ 1 ]);;
  gap> wadc1 := WordAcceptorOfDoubleCosetRws( dcrws1 );
  < deterministic automaton on 6 letters with 15 states >
  gap> Print( wadc1 );
  Automaton("det",15,"HKaAbB",[ [ 2, 2, 2, 6, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ],\
   [ 2, 2, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 2 ], [ 2, 2, 13, 2, 10, 5, 2, 13,\
   2, 7, 11, 11, 12, 2, 2 ], [ 2, 2, 9, 2, 2, 14, 2, 9, 15, 2, 2, 2, 2, 7, 15 ],\
   [ 2, 2, 2, 2, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ], [ 2, 2, 3, 2, 3, 3, 3, 2, 3,\
   3, 3, 3, 3, 3, 3 ] ],[ 4 ],[ 1 ]);;
  gap> words1 := [ "HK","HaK","HbK","HAK","HaaK","HbbK","HabK","HbaK","HbaabK"];;
  gap> valid1 := List( words1, w -> IsRecognizedByAutomaton( wadc1, w ) );
  [ true, true, true, false, false, true, true, true, true ]
  gap> lang1 := FAtoRatExp( wadc1 );
  ((H(aaaUAA)BUH(a(aBUB)UABUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(a(aa*bUb)Ub)UA(AA\
  *bUb))UH(aaaUAA)bUH(a(abUb)UAbUb))((a(a(aa*BUB)UB)UA(AA*BUB))(a(a(aa*BUB)UB)UA\
  (AA*BUB)UB)*(a(a(aa*bUb)Ub)UA(AA*bUb))Ua(a(aa*bUb)Ub)UA(AA*bUb)Ub)*((a(a(aa*BU\
  B)UB)UA(AA*BUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(aKUK)UAKUK)Ua(aKUK)UAKUK)U(H(a\
  aaUAA)BUH(a(aBUB)UABUB))(a(a(aa*BUB)UB)UA(AA*BUB)UB)*(a(aKUK)UAKUK)UH(aKUK)
  
\end{Verbatim}
 }

 
\section{\textcolor{Chapter }{Example 2 -- the trefoil group}}\logpage{[ 2, 3, 0 ]}
\hyperdef{L}{X838CC08E7E92EBC0}{}
{
 \index{example -- trefoil group} \index{trefoil group} 

\subsection{\textcolor{Chapter }{PartialDoubleCosetRewritingSystem}}
\logpage{[ 2, 3, 1 ]}\nobreak
\hyperdef{L}{X83DE506B828F4B0D}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{PartialDoubleCosetRewritingSystem({\slshape grp, Hgens, Kgens, rws, limit})\index{PartialDoubleCosetRewritingSystem@\texttt{PartialDoubleCosetRewritingSystem}}
\label{PartialDoubleCosetRewritingSystem}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordAcceptorOfPartialDoubleCosetRws({\slshape grp, prws})\index{WordAcceptorOfPartialDoubleCosetRws@\texttt{WordAcceptorOfPartialDoubleCosetRws}}
\label{WordAcceptorOfPartialDoubleCosetRws}
}\hfill{\scriptsize (attribute)}}\\


 It may happen that, even when $G$ has a finite rewriting system, the double coset rewriting system is infinite.
This is the case with the trefoil group $T$ with generators $[x,y]$ and relator $[x^3 = y^2]$ if the wreath product ordering is used with $X > x > Y > y$. The group itself has a rewriting system with just 6 rules. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> FT := FreeGroup( 2 );;
  gap> relsT := [ FT.1^3*FT.2^-2 ];;
  gap> T := FT/relsT;;
  gap> genT := GeneratorsOfGroup( T );;
  gap> x := genT[1];  y := genT[2];
  gap> alphT := "XxYy";;
  gap> ordT := [4,3,2,1];;
  gap> orderT := "wreath";;
  gap> rwsT := ReducedConfluentRewritingSystem( T, ordT, orderT, 0, alphT );
  gap> DisplayRwsRules( rwsT );;
  [ [ Yy, id ], [ yY, id ], [ X, xxYY ], [ xxx, yy ], [ yyx, xyy ], [ Yx, yxYY ]\
   ]
  gap> accT := WordAcceptorOfReducedRws( rwsT );
  < deterministic automaton on 4 letters with 7 states >
  gap> Print( accT );
  Automaton("nondet",7,"yYxX",[ [ [ 1 ], [ 4 ], [ 1 ], [ 4, 7 ], [ 4 ], [ 4 ], [\
   4, 7 ] ], [ [ 1 ], [ 3 ], [ 3 ], [ 1 ], [ 3 ], [ 3 ], [ 1 ] ], [ [ 1 ], [ 5 ]\
  , [ 1 ], [ 5 ], [ 5, 6 ], [ 1 ], [ 1 ] ], [ [ 1 ], [ 1 ], [ 1 ], [ 1 ], [ 1 ],\
   [ 1 ], [ 1 ] ] ],[ 2 ],[ 1 ]);;
  gap> langT := FAtoRatExp( accT );
  (xx*(xyUy)Uy)(xx*(xyUy)Uyy*yUy)*(xx*((xYUY)Y*(yUxUX)Ux(xUX)UX)(yUYUxUX)*U(yy*(\
  YUxUX)UYUX)(yUYUxUX)*)Uxx*((xYUY)Y*(yUxUX)Ux(xUX)UX)(yUYUxUX)*U(YY*(yUxUX)UX)(\
  yUYUxUX)*(yxUx)((xyUy)x)*
  gap> r := RationalExpression( "((xyUy)y*UxY*UY*)Uyy*UY*" ); 
  (xyUy)y*UxY*UY*Uyy*UY*
  gap> AreEqualLang( langT, r );
  The given languages are not over the same alphabet
  false
  
\end{Verbatim}
 In a previous version the expression \texttt{r}, which does not involve the letter \texttt{X}, was returned as the language \texttt{langT}. This discrepancy should be investigated. 

 Taking subgroups $H$, $K$ to be generated by $x$ and $y$ respectively, the double coset rewriting system has an infinite number of $H$-rules. It turns out that only a finite number of these are needed to produce
the required automaton. The function \texttt{PartialDoubleCosetRewritingSystem} allows a limit to be specified on the number of rules to be computed. In the
listing below a limit of 20 is used, but in fact 10 is sufficient. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> prwsT := PartialDoubleCosetRewritingSystem( T, [x], [y], rwsT, 20 );;
  #I WARNING: reached supplied limit 20 on number of rules
  gap> DisplayRwsRules( prwsT );
  G-rules:
  [ [ X, xxYY ], [ Yx, yxYY ], [ Yy, id ], [ yY, id ], [ xxx, yy ], [ yyx, xyy ]\
   ]
  H-rules:
  [ [ Hx, H ],
    [ HY, Hy ],
    [ Hyy, H ],
    [ Hyxyy, Hyx ],
    [ HyxY, Hyxy ],
    [ Hyxyxyy, Hyxyx ],
    [ Hyxxyy, Hyxx ],
    [ HyxxY, Hyxxy ],
    [ HyxyxY, Hyxyxy ],
    [ Hyxyxyxyy, Hyxyxyx ],
    [ Hyxyxxyy, Hyxyxx ],
    [ Hyxxyxyy, Hyxxyx ],
    [ HyxxyxYY, Hyxxyx ] ]
  K-rules:
  [ [ YK, K ],
    [ yK, K ] ]
  
\end{Verbatim}
 This list of partial rules is then used by a modified word acceptor function. 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> paccT := WordAcceptorOfPartialDoubleCosetRws( T, prwsT );;
  < deterministic automaton on 6 letters with 6 states >
  gap> Print( paccT, "\n" );
  Automaton("det",6,"HKyYxX",[ [ 2, 2, 2, 6, 2, 2 ], [ 2, 2, 1, 2, 2, 1 ], [ 2, \
  2, 5, 2, 2, 5 ], [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 6, 2, 3, 2 ], [ 2, 2, 2, 2, 2, \
  2 ] ],[ 4 ],[ 1 ]);;
  gap> plangT := FAtoRatExp( paccT );
  H(yx(yx)*x)*(yx(yx)*KUK)
  gap> wordsT := ["HK", "HxK", "HyK", "HYK", "HyxK", "HyxxK", "HyyH", "HyxYK"];;
  gap> validT := List( wordsT, w -> IsRecognizedByAutomaton( paccT, w ) );
  [ true, false, false, false, true, true, false, false ]
  
\end{Verbatim}
 }

 
\section{\textcolor{Chapter }{Example 3 -- an infinite rewriting system}}\logpage{[ 2, 4, 0 ]}
\hyperdef{L}{X86DACE357868DC1B}{}
{
 \index{example -- infinite rws} 

\subsection{\textcolor{Chapter }{KBMagRewritingSystem}}
\logpage{[ 2, 4, 1 ]}\nobreak
\hyperdef{L}{X8722C57284F51940}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KBMagRewritingSystem({\slshape fpgrp})\index{KBMagRewritingSystem@\texttt{KBMagRewritingSystem}}
\label{KBMagRewritingSystem}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KBMagWordAcceptor({\slshape fpgrp})\index{KBMagWordAcceptor@\texttt{KBMagWordAcceptor}}
\label{KBMagWordAcceptor}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{KBMagFSAtoAutomataDFA({\slshape fsa, alph})\index{KBMagFSAtoAutomataDFA@\texttt{KBMagFSAtoAutomataDFA}}
\label{KBMagFSAtoAutomataDFA}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordAcceptorByKBMag({\slshape grp, alph})\index{WordAcceptorByKBMag@\texttt{WordAcceptorByKBMag}}
\label{WordAcceptorByKBMag}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordAcceptorByKBMagOfDoubleCosetRws({\slshape grp, dcrws})\index{WordAcceptorByKBMagOfDoubleCosetRws@\texttt{WordAcceptorByKBMagOfDoubleCosetRws}}
\label{WordAcceptorByKBMagOfDoubleCosetRws}
}\hfill{\scriptsize (operation)}}\\


 When the group $G$ has an infinite rewriting system, the double coset rewriting system will also
be infinite. In this case we try the function \texttt{KBMagWordAcceptor} which calls the package \textsf{KBMAG} to compute a word acceptor for $G$, and \texttt{KBMagFSAtoAutomataDFA} to convert this to a deterministic automaton as used by the \textsf{automata} package. The resulting \texttt{dfa} forms part of the double coset automaton, together with sufficient $H$-rules, $K$-rules and $H$-$K$-rules found by the function \texttt{PartialDoubleCosetRewritingSystem}. (Note that these five attributes and operations will not be available if the \textsf{kbmag} package has not been loaded.) 

 In the following example we take a two generator group $G3$ with relators $[a^3,b^3,(a*b)^3]$, the normal forms of whose elements are some of the strings with $a$ or $a^{-1}$ alternating with $b$ or $b^{-1}$. The automatic structure computed by \textsf{KBMAG} has a word acceptor with 17 states. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> F3 := FreeGroup("a","b");;
  gap> rels3 := [ F3.1^3, F3.2^3, (F3.1*F3.2)^3 ];;
  gap> G3 := F3/rels3;;
  gap> alph3 := "AaBb";;
  gap> waG3 := WordAcceptorByKBMag( G3, alph3 );;
  gap> Print( waG3, "\n");
  Automaton("det",18,"aAbB",[ [ 2, 18, 18, 8, 10, 12, 13, 18, 18, 18, 18, 18, 18\
  , 8, 17, 12, 18, 18 ], [ 3, 18, 18, 9, 11, 9, 12, 18, 18, 18, 18, 18, 18, 11, \
  18, 11, 18, 18 ], [ 4, 6, 6, 18, 18, 18, 18, 18, 6, 12, 16, 18, 12, 18, 18, 18\
  , 12, 18 ], [ 5, 5, 7, 18, 18, 18, 18, 14, 15, 5, 18, 18, 7, 18, 18, 18, 15, 1\
  8 ] ],[ 1 ],[ 1 .. 17 ]);;
  gap> langG3 := FAtoRatExp( waG3 );
  ((abUAb)AUbA)(bA)*(b(aU@)UB(aB)*(a(bU@)U@)U@)U(abUAb)(aU@)U((aBUB)(aB)*AUba(Ba\
  )*BA)(bA)*(b(aU@)U@)U(aBUB)(aB)*(a(bU@)U@)Uba(Ba)*(BU@)UbUaUA(B(aB)*(a(bU@)UAU\
  @)U@)U@
  
\end{Verbatim}
 

\subsection{\textcolor{Chapter }{DCrules}}
\logpage{[ 2, 4, 2 ]}\nobreak
\hyperdef{L}{X815C08FD87D014B5}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DCrules({\slshape dcrws})\index{DCrules@\texttt{DCrules}}
\label{DCrules}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Hrules({\slshape dcrws})\index{Hrules@\texttt{Hrules}}
\label{Hrules}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{Krules({\slshape dcrws})\index{Krules@\texttt{Krules}}
\label{Krules}
}\hfill{\scriptsize (attribute)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{HKrules({\slshape dcrws})\index{HKrules@\texttt{HKrules}}
\label{HKrules}
}\hfill{\scriptsize (attribute)}}\\


 We now take $H$ to be generated by $ab$ and $K$ to be generated by $ba$. If we specify a limits of 50, 75, 100, 200 for the number of rules in a
partial double coset rewrite system, we obtain lists of $H$-rules, $K$-rules and $H$-$K$-rules of increasing length. The numbers of states in the resulting automata
also increase. We may deduce by hand (but not computationally -- see \cite{BrGhHeWe}) three infinite sets of rules and a limit for the automata. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> lim := 100;;
  gap> genG3 := GeneratorsOfGroup( G3 );;
  gap> a := genG3[1];;  b := genG3[2];; 
  gap> gH3 := [ a*b ];;  gK3 := [ b*a ];;
  gap> rwsG3 := KnuthBendixRewritingSystem( G3, "shortlex", [2,1,4,3], alph3 );;
  gap> dcrws3 := PartialDoubleCosetRewritingSystem( G3, gH3, gK3, rwsG3, lim );;
  #I using PartialDoubleCosetRewritingSystem with limit 100
  #I  51 rules, and 1039 pairs
  #I WARNING: reached supplied limit 100 on number of rules
  gap> Print( Length( Rules( dcrws3 ) ), " rules found.\n" );
  101 rules found.
  gap> dcaut3 := WordAcceptorByKBMagOfDoubleCosetRws( G3, dcrws3 );;
  gap> Print( "Double Coset Minimalized automaton:\n", dcaut3 );
  Double Coset Minimalized automaton:
  Automaton("det",40,"HKaAbB",[ [ 2, 2, 2, 5, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2\
  , 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 ], [ \
  2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, \
  1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 1 ], [ 2, 2, 2, 2, 3, 22, 2, 2, 2, 2, 2\
  , 2, 2, 2, 2, 2, 2, 2, 39, 2, 39, 2, 25, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2\
  , 2, 2, 2, 2 ], [ 2, 2, 2, 2, 40, 3, 27, 2, 8, 2, 10, 2, 12, 2, 14, 2, 16, 2, \
  18, 2, 20, 2, 2, 2, 2, 24, 2, 27, 2, 29, 2, 31, 2, 33, 2, 35, 2, 37, 2, 2 ], [\
   2, 2, 2, 2, 19, 2, 2, 26, 2, 9, 2, 11, 2, 13, 2, 15, 2, 17, 2, 38, 2, 3, 2, 2\
  6, 3, 2, 7, 2, 28, 2, 30, 2, 32, 2, 34, 2, 36, 2, 2, 26 ], [ 2, 2, 2, 2, 2, 2,\
   2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 6, 2, 23, 23, 2, 2, 2, 2, 2, 2, \
  2, 2, 2, 2, 2, 2, 2, 21, 6 ] ],[ 4 ],[ 1 ]);;
  gap> dclang3 := FAtoRatExp( dcaut3 );;
  gap> Print( "Double Coset language of acceptor:\n", dclang3, "\n" );
  Double Coset language of acceptor:
  (HbAbAbAbAbAbAbUHAb)(Ab)*(A(Ba(Ba)*bKUK)UK)UHbAbA(bA(bA(bA(bAKUK)UK)UK)UK)UH(A\
  (B(aB)*(abUA)KUK)UaKUb(a(Ba)*BA(bA(bA(bA(bA(bA(bA(bA)*(bKUK)UK)UK)UK)UK)UK)UK)\
  UAK)UK)
  gap> ok := DCrules(dcrws3);;
  gap> alph3e := dcrws3!.alphabet;;
  gap> Print("H-rules:\n");  DisplayAsString( Hrules(dcrws3), alph3e, true );
  H-rules:
  [ HB, Ha ]
  [ HaB, Hb ]
  [ Hab, H ]
  [ HbAB, HAba ]
  [ HbAbAB, HAbAba ]
  [ HbAbAbAB, HAbAbAba ]
  [ HbAbAbAbAB, HAbAbAbAba ]
  [ HbAbAbAbAbAB, HAbAbAbAbAba ]
  [ HbAbAbAbAbAbAB, HAbAbAbAbAbAba ]
  gap> Print("K-rules:\n");  DisplayAsString( Krules(dcrws3), alph3e, true );
  K-rules:
  [ BK, aK ]
  [ BaK, bK ]
  [ baK, K ]
  [ BAbK, abAK ]
  [ BAbAbK, abAbAK ]
  [ BAbAbAbK, abAbAbAK ]
  [ BAbAbAbAbK, abAbAbAbAK ]
  [ BAbAbAbAbAbK, abAbAbAbAbAK ]
  [ BAbAbAbAbAbAbK, abAbAbAbAbAbAK ]
  gap> Print("HK-rules:\n");  DisplayAsString( HKrules(dcrws3), alph3e, true );
  HK-rules:
  [ HbK, HAK ]
  [ HbAbK, HAbAK ]
  [ HbAbAbK, HAbAbAK ]
  [ HbAbAbAbK, HAbAbAbAK ]
  [ HbAbAbAbAbK, HAbAbAbAbAK ]
  [ HbAbAbAbAbAbK, HAbAbAbAbAbAK ]
  
\end{Verbatim}
 

\subsection{\textcolor{Chapter }{NextWord}}
\logpage{[ 2, 4, 3 ]}\nobreak
\hyperdef{L}{X7AF0265982B42E47}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{NextWord({\slshape dcrws, word})\index{NextWord@\texttt{NextWord}}
\label{NextWord}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{WordToString({\slshape word, alph})\index{WordToString@\texttt{WordToString}}
\label{WordToString}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DisplayAsString({\slshape word, alph})\index{DisplayAsString@\texttt{DisplayAsString}}
\label{DisplayAsString}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{IdentityDoubleCoset({\slshape dcrws})\index{IdentityDoubleCoset@\texttt{IdentityDoubleCoset}}
\label{IdentityDoubleCoset}
}\hfill{\scriptsize (operation)}}\\


 These functions may be used to find normal forms of increasing length for
double coset representatives. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> len := 30;;
  gap> L3 := 0*[1..len];;
  gap> L3[1] := IdentityDoubleCoset( dcrws3 );;
  gap> for i in [2..len] do
  gap>     L3[i] := NextWord( dcrws3, L3[i-1] );
  gap> od;
  gap> ## List of 30 normal forms for double cosets:
  gap> DisplayAsString( L3, alph3e, true );
  [ HK, HAK, HaK, HAbK, HbAK, HABAK, HAbAK, HABabK, HAbAbK, HbAbAK, HbaBAK, HABa\
  BAK, HAbAbAK, HABaBabK, HAbABabK, HAbAbAbK, HbAbAbAK, HbaBAbAK, HbaBaBAK, HABa\
  BaBAK, HAbAbAbAK, HABaBaBabK, HAbABaBabK, HAbAbABabK, HAbAbAbAbK, HbAbAbAbAK, \
  HbaBAbAbAK, HbaBaBAbAK, HbaBaBaBAK, HABaBaBaBAK ]
  gap> w := NextWord( dcrws3, L3[30] );
  m1*m3*m6*m3*m6*m3*m6*m3*m6*m3*m2
  gap> s := WordToString( w, alph3e );
  "HAbAbAbAbAK"
  
\end{Verbatim}
 }

 }

           
\chapter{\textcolor{Chapter }{Development History}}\label{chap-history}
\logpage{[ 3, 0, 0 ]}
\hyperdef{L}{X810C43BC7F63C4B4}{}
{
  
\section{\textcolor{Chapter }{Versions of the package}}\logpage{[ 3, 1, 0 ]}
\hyperdef{L}{X8192EA4C7B7CC5CD}{}
{
 The first version of the package, written for \textsf{GAP} 3, formed part of Anne Heyworth's thesis \cite{anne-thesis} in 1999, but was not made generally available. 

 Version, \textsf{kan} 0.91, was prepared to run under \textsf{GAP} 4.4.6, in July 2005. 

 Version, \textsf{kan} 0.94, differed in two significant ways. 
\begin{itemize}
\item  This manual is prepared using the \textsf{GAPDoc} package. 
\item  The test file \texttt{kan/tst/kan\texttt{\symbol{92}}{\textunderscore}manual.tst} sets the \texttt{AssertionLevel} to \texttt{0} to avoid recursion in the \textsf{Automata} package. 
\end{itemize}
 

 Version 0.95, of 9th October 2007, just fixed file protections and added a \texttt{CHANGES} file. 

 Version 0.96 was required because the \textsf{kan} website moved with the rest of the Mathematics website at Bangor. 

 Version 0.97, of November 18th 2008, deleted temporary fixes which were no
longer needed once version 1.12 of \textsf{Automata} became available. }

 
\section{\textcolor{Chapter }{What needs doing next?}}\logpage{[ 3, 2, 0 ]}
\hyperdef{L}{X83D1530487593182}{}
{
 There are too many items to list here, but some of the most important are as
follows. 
\begin{itemize}
\item  Implement iterators and enumerators for double cosets. 
\item  At present the methods for \texttt{DoubleCosetsNC} and \texttt{RightCosetsNC} in this package return automata, rather than lists of cosets or coset
enumerators. This needs to be fixed. 
\item  Provide methods for operations such as \texttt{DoubleCosetRepsAndSizes}. 
\item  Convert the rest of the original \textsf{GAP} 3 version of \textsf{kan} to \textsf{GAP} 4. 
\end{itemize}
 

\subsection{\textcolor{Chapter }{DoubleCosetsAutomaton}}
\logpage{[ 3, 2, 1 ]}\nobreak
\hyperdef{L}{X852CC057809CE3EE}{}
{\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{DoubleCosetsAutomaton({\slshape G, U, V})\index{DoubleCosetsAutomaton@\texttt{DoubleCosetsAutomaton}}
\label{DoubleCosetsAutomaton}
}\hfill{\scriptsize (operation)}}\\
\noindent\textcolor{FuncColor}{$\Diamond$\ \texttt{RightCosetsAutomaton({\slshape G, V})\index{RightCosetsAutomaton@\texttt{RightCosetsAutomaton}}
\label{RightCosetsAutomaton}
}\hfill{\scriptsize (operation)}}\\


 Alternative methods for \texttt{DoubleCosetsNC(G,U,V)} and \texttt{RightCosetsNC(G,V)} \emph{should be} provided in the cases where the group \texttt{G} has a rewriting system or is known to be infinite. At present the functions \texttt{RightCosetsAutomaton} and \texttt{DoubleCosetsAutomaton} return minimized automata, and \texttt{Iterators} for these are not yet available. }

 
\begin{Verbatim}[fontsize=\small,frame=single,label=Example]
  
  gap> F := FreeGroup(2);;
  gap> rels := [ F.2^2, (F.1*F.2)^2 ];;
  gap> G4 := F/rels;;
  gap> genG4 := GeneratorsOfGroup( G4 );;
  gap> a := genG4[1];  b := genG4[2];;
  gap> U := Subgroup( G4, [a^2] );;
  gap> V := Subgroup( G4, [b] );;
  gap> dc4 := DoubleCosetsAutomaton( G4, U, V );;
  gap> Print( dc4 );
  Automaton("det",5,"HKaAbB",[ [ 2, 2, 2, 5, 2 ], [ 2, 2, 1, 2, 1 ], [ 2, 2, 2, \
  2, 3 ], [ 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2 ] ],[ 4 ],[ 1 ])\
  ;;
  gap> rc4 := RightCosetsAutomaton( G4, V );;
  gap> Print( rc4 );
  Automaton("det",6,"HKaAbB",[ [ 2, 2, 2, 6, 2, 2 ], [ 2, 2, 1, 2, 1, 1 ], [ 2, \
  2, 3, 2, 2, 3 ], [ 2, 2, 2, 2, 5, 5 ], [ 2, 2, 2, 2, 2, 2 ], [ 2, 2, 2, 2, 2, \
  2 ] ],[ 4 ],[ 1 ]);;
  
\end{Verbatim}
 }

 }

 \def\bibname{References\logpage{[ "Bib", 0, 0 ]}
\hyperdef{L}{X7A6F98FD85F02BFE}{}
}

\bibliographystyle{alpha}
\bibliography{manual}

\def\indexname{Index\logpage{[ "Ind", 0, 0 ]}
\hyperdef{L}{X83A0356F839C696F}{}
}


\printindex

\newpage
\immediate\write\pagenrlog{["End"], \arabic{page}];}
\immediate\closeout\pagenrlog
\end{document}