Quelle  kbsmg.gd   Sprache: Shell

#############################################################################
##
#W  kbsmg.gd           GAP library                                 Derek Holt
##
#Y  Copyright (C)  1997,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St.  Andrews, Scotland
##
##  This file contains the declarations for Knuth Bendix Rewriting Systems
##


############################################################################
##
#C  IsKnuthBendixRewritingSystem(<obj>)
## 
##  This is the category of Knuth Bendix rewriting systems.
##  DO WE NEED A NEW CATEGORY OF KBMAG REWRITING SYSTEMS???
##
##DeclareCategory("IsKnuthBendixRewritingSystem", IsRewritingSystem);

############################################################################
##
#F  CreateKBMAGRewritingSystemOfFpSemigroup(<S>,<lt>)
##  
##
DeclareGlobalFunction("CreateKBMAGRewritingSystemOfFpSemigroup");

############################################################################
##
#F  CreateKBMAGRewritingSystemOfFpMonoid(<S>,<lt>)
##  
##
DeclareGlobalFunction("CreateKBMAGRewritingSystemOfFpMonoid");

############################################################################
##
#F  CreateKBMAGRewritingSystemOfFpGroup(<S>,<lt>)
##  
##
DeclareGlobalFunction("CreateKBMAGRewritingSystemOfFpGroup");

#############################################################################
##
#O  KBMAGRewritingSystem(<rws>)
##
##
DeclareOperation("KBMAGRewritingSystem",[IsSemigroup]);

#############################################################################
##
#O  WordMonoidOfRewritingSystem(<rws>)
##
##
DeclareOperation("WordMonoidOfRewritingSystem",[IsKnuthBendixRewritingSystem]);

############################################################################
##
#F  ExternalWordToInternalWordOfRewritingSystem(<R>,<w>)
##  
## Convert a word in the external free structure of a rewriting system
## to its corresponding word in the internal word monoid.
##
DeclareGlobalFunction("ExternalWordToInternalWordOfRewritingSystem");

############################################################################
##
#F  InternalWordToExternalWordOfRewritingSystem(<R>,<w>)
##  
## Convert a word in the external free structure of a rewriting system
## to its corresponding word in the internal word monoid.
##
DeclareGlobalFunction("InternalWordToExternalWordOfRewritingSystem");

############################################################################
##
#O  Alphabet(<rws>)
##
##
DeclareAttribute("Alphabet",IsKnuthBendixRewritingSystem);

############################################################################
##
#F  OptionsRecordOfKBMAGRewritingSystem(<R>)
##  
##  This is a record whose components are optional parameters controlling
##  the Knuth-Bendix completion process, and can be set by the user.
##
DeclareGlobalFunction("OptionsRecordOfKBMAGRewritingSystem");

############################################################################
##
#F  ReorderAlphabetOfKBMAGRewritingSystem(<R>,<perm>)
##  
## <perm> should be a permutation of [1..Size of Alphabet of <rws>].
## The order of the alphabet is part of the definition of the
## ordering of the rewriting-system.
##
DeclareGlobalFunction("ReorderAlphabetOfKBMAGRewritingSystem");

############################################################################
##
#F  SetOrderingOfKBMAGRewritingSystem(<R>,<ordering-string>[,list])
##  
## This sets the ordering of words that will be used by the Knuth-Bendix
## program. Remember that the ordering also depends on the ordering of
## the alphabet, which can be changed by the preceding function.
## The permitted ordering strings are:
## "shortlex", "wtlex", "wreathprod", "recursive".
## In the "wtlex" and "recursive" cases, the third parameter giving a
## list of the (positive integral) weights or levels of the alphabet
## is mandatory.
##
DeclareGlobalFunction("SetOrderingOfKBMAGRewritingSystem");

############################################################################
##
#F OrderingOfKBMAGRewritingSystem(<R>)
##  
## Prints out a description of the ordering.
##
DeclareGlobalFunction("OrderingOfKBMAGRewritingSystem");

#############################################################################
##
#O  KnuthBendix(<rws>)
##
##  Apply the Knuth-Bendix completion algorithm to <rws>
##
DeclareOperation("KnuthBendix",[IsKnuthBendixRewritingSystem]);

#############################################################################
##
#F  AutomaticStructure(<rws>[,<large>,<filestore>,<diff1>])
##
##  Attempt to compute a shortlex automatix structure for <rws>
##  <large>,<filestore>and<diff1> are optional boolean parameters.
##  <large> is the most useful and should be used for difficult examples.
##
DeclareGlobalFunction("AutomaticStructure");

#############################################################################
##
#O  EnumerateReducedWords(<rws>,<minlength>,<maxlength>)
##
##  return a list of the reduced words in the rewriting system having lengths
##  between <minlength> and <maxlength> 
##
DeclareOperation("EnumerateReducedWords",
                           [IsKnuthBendixRewritingSystem,IsInt,IsInt]);

#############################################################################
##
#A  IsReducedWord(<rws>,<w>)
##
##  is w in reduced form?
##
DeclareOperation("IsReducedWord",
                           [IsKnuthBendixRewritingSystem,IsAssocWord]);

#############################################################################
##
#A  ReducedWord(<rws>,<w>)
##
##  reduced form of w - same as ReducedForm
##
DeclareOperation("ReducedWord",
                           [IsKnuthBendixRewritingSystem,IsAssocWord]);

############################################################################
##
#F GrowthFunction(<rws>)
##
## The growth function of <rws> if available (a rational function).
##
DeclareGlobalFunction("GrowthFunction");

############################################################################
##
#F ReductionAutomaton(<rws>)
##
## The reduction automaton of <rws> if available.
##
DeclareGlobalFunction("ReductionAutomaton");

############################################################################
##
#F WordAcceptor(<rws>)
##
##
DeclareGlobalFunction("WordAcceptor");

############################################################################
##
#F FirstWordDifferenceAutomaton(<rws>)
##
##
DeclareGlobalFunction("FirstWordDifferenceAutomaton");

############################################################################
##
#F SecondWordDifferenceAutomaton(<rws>)
##
##
DeclareGlobalFunction("SecondWordDifferenceAutomaton");

############################################################################
##
#F GeneralMultiplier(<rws>)
##
##
DeclareGlobalFunction("GeneralMultiplier");

############################################################################
##
#F  ResetRewritingSystem(<rws>)
##
##  Reset after an earlier run of KnuthBendix or AutomaticStructure
##
DeclareGlobalFunction("ResetRewritingSystem");

#############################################################################
##
#F  SubgroupOfKBMAGRewritingSystem(<rws>,<H>)
##
## Defines a subgroup of a KBMAGRewritingSystem <rws>, which will itself
## be a KBMAG rewriting system, but initially without rules.
## This is only applicable if <rws> is defined from a group.
## <H> needs to define a subgroup of the underlying free group of <rws>,
##  either as a subgroup or a s a list of generators.
##
DeclareGlobalFunction("SubgroupOfKBMAGRewritingSystem");

#############################################################################
##
#A  IsConfluentOnCosets(<rws>,<subrws>)
##
##
DeclareOperation("IsConfluentOnCosets",
        [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem]);

#############################################################################
##
#O  KnuthBendixOnCosets(<rws>,<subrws>,)
##
##  Apply the Knuth-Bendix completion algorithm on a cosets rewriting
##  system of <rws> with respect to the subgroup corresponding to <subrws>
##  (<subrws> should be the result returned by a call of
##  SubgroupOfKBMAGRewritingSystem. If the optional <subgens> is 'true',
## then in addition a confluent rewriting system for <subrws> is
## computed.
##
DeclareOperation("KnuthBendixOnCosets",
    [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem]);

#############################################################################
##
#O  KnuthBendixOnCosetsWithSubgroupRewritingSystem(<rws>,<subrws>)
##
## Same as KnuthBendixOnCosets but
## in addition a confluent rewriting system for <subrws> is computed.
##
DeclareOperation("KnuthBendixOnCosetsWithSubgroupRewritingSystem",
    [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem]);

#############################################################################
##
#F  RewritingSystemOfSubgroupOfKBMAGRewritingSystem(<rws>,<subrws>)
##
##  Returns the rewriting system computed by 
##  KnuthBendixOnCosetsWithSubgroupRewritingSystem
##
DeclareGlobalFunction("RewritingSystemOfSubgroupOfKBMAGRewritingSystem");

#############################################################################
##
#F  AutomaticStructureOnCosets(<rws>,<subrws>,[large,filestore,diff1])
##
##  Attempt to compute a shortlex coset automatix structure for <rws>
##  <large>,<filestore>and<diff1> are optional boolean parameters.
##  <large> is the most useful and should be used for difficult examples.
##
DeclareGlobalFunction("AutomaticStructureOnCosets");

#############################################################################
##
#F  AutomaticStructureOnCosetsWithSubgroupPresentation(<rws>,<subrws>,
##                                        [large,filestore,diff1])
##
##  Same as AutomaticStructureOnCosets but compute subgroup
##  presentation in addition.
##
DeclareGlobalFunction("AutomaticStructureOnCosetsWithSubgroupPresentation");

#############################################################################
##
#F  PresentationOfSubgroupOfKBMAGRewritingSystem(<rws>,<subrws>)
##
##  Returns the subgroup presentation computed by 
##  AutomaticStructureOnCosetsWithSubgroupPresentation
##
DeclareGlobalFunction("PresentationOfSubgroupOfKBMAGRewritingSystem");

#############################################################################
##
#O  ReducedFormOfCosetRepresentative(<rws>,<subrws>,<w>)
##
## Reduce coset representative of word w - cosets of <subrws> in <rws>.
##
DeclareOperation("ReducedFormOfCosetRepresentative",
    [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem,IsAssocWord]);

#############################################################################
##
#O  ReducedCosetRepresentative(<rws>,<subrws>,<w>)
##
## Same as ReducedFormOfCosetRepresentative
##
DeclareOperation("ReducedCosetRepresentative",
    [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem,IsAssocWord]);

#############################################################################
##
#A  IsReducedCosetRepresentative(<rws>,<subrws>,<w>)
##
##  is w in reduced form as a coset representative?
##
DeclareOperation("IsReducedCosetRepresentative",
    [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem,IsAssocWord]);

#############################################################################
##
#O  EnumerateReducedCosetRepresentatives(<rws>,<subrws>,<minlength>,<maxlength>)
##
##  return a list of the reduced words for coset representatives in the
##  subgroup rewriting system <subrws> in <rws> having lengths
##  between <minlength> and <maxlength> 
##
DeclareOperation("EnumerateReducedCosetRepresentatives",
     [IsKnuthBendixRewritingSystem,IsKnuthBendixRewritingSystem,IsInt,IsInt]);

############################################################################
##
#F GrowthFunctionOfCosetRepresentatives(<rws>,<subrws>)
##
## The growth function of the reduced words for coset representatives in
## the subgroup rewriting system <subrws> in <rws> (a rational function).
##
DeclareGlobalFunction("GrowthFunctionOfCosetRepresentatives");


############################################################################
##
#F  ResetRewritingSystemOnCosets(<rws>,<subrws>)
##
##  Reset after an earlier run of KnuthBendix or AutomaticStructure
##  On Cosets
##
DeclareGlobalFunction("ResetRewritingSystemOnCosets");

#############################################################################
##
#V  KBMAG_REW
##
##  `KBMAG_REW', contains the KB functions for library level rewriting
##  systems provided using KBMAG.
BindGlobal("KBMAG_REW",rec(name:="KBMAG Knuth-Bendix"));


#############################################################################
##
#E