kbmag

Knuth-Bendix on Monoids and Automatic Groups

1.5.11

3 January 2023

Abstract

The KBMag package is a GAP interface to some `C' programs for running the Knuth-Bendix completion program on finite semigroup, monoid or group presentations, and for attempting to compute automatic structures of finitely presented groups.

Bug reports, comments, suggestions for additional features, and offers to implement some of these, will all be very welcome.

This package may be distributed under the terms and conditions of the GNU Public License Version 2.

Acknowledgements

This documentation was prepared with the GAPDoc [LN17] and AutoDoc [GH17] packages.

The procedure used to produce new releases uses the package GitHubPagesForGAP [Hor17] and the package ReleaseTools.

1 Introduction

2 The Knuth-Bendix program on semigroups, monoids and groups

2.1 Creating a rewriting system

2.1-1 KBMAGRewritingSystem

2.2 Elementary functions on rewriting systems

  2.2-1 IsKBMAGRewritingSystemRep
  2.2-2 IsConfluent
  2.2-3 SemigroupOfRewritingSytem
  2.2-4 ExternalWordToInternalWordOfRewritingSystem
  2.2-5 Alphabet
  2.2-6 Rules
  2.2-7 ResetRewritingSystem

2.3 Setting the ordering

2.3-1 SetOrderingOfKBMAGRewritingSystem

2.4 Control parameters

2.4-1 InfoRWS
2.4-2 OptionsRecordOfKBMAGRewritingSystem

2.5 The Knuth-Bendix program

2.5-1 KnuthBendix
2.5-2 ReductionAutomaton

2.6 The automatic groups program

2.6-1 AutomaticStructure
2.6-2 WordAcceptor

2.7 Word reduction

2.7-1 IsReducedWord
2.7-2 ReducedWord

2.8 Counting and enumerating irreducible words

  2.8-1 Size
  2.8-2 Order
  2.8-3 EnumerateReducedWords
  2.8-4 GrowthFunction

2.9 Rewriting System Examples

  2.9-1 Example 1
  2.9-2 Example 2
  2.9-3 Example 3
  2.9-4 Example 4
  2.9-5 Example 5

3 The Knuth-Bendix program on cosets

3.1 Subgroups, cosets and subgroup presentations

3.1-1 SubgroupOfKBMAGRewritingSystem
3.1-2 ResetRewritingSystemOnCosets

3.2 The Knuth-Bendix program on cosets

  3.2-1 KnuthBendixOnCosets
  3.2-2 RewritingSystemOfSubgroupOfKBMAGRewritingSystem
  3.2-3 IsConfluentOnCosets

3.3 The automatic cosets program

3.3-1 AutomaticStructureOnCosets
3.3-2 PresentationOfSubgroupOfKBMAGRewritingSystem

3.4 Word reduction on cosets

3.4-1 IsReducedCosetRepresentative
3.4-2 ReducedCosetRepresentative

3.5 Counting and enumerating irreducible words for cosets

  3.5-1 Index
  3.5-2 EnumerateReducedCosetRepresentatives
  3.5-3 GrowthFunctionOfCosetRepresentatives

3.6 Examples of the use of Rewriting System on Cosets

3.6-1 Example 1
3.6-2 Example 2

4 The stand-alone package

4.1 Functions for manipulating finite state automata

  4.1-1 IsInitializedFSA
  4.1-2 InitializeFSA
  4.1-3 FSA
  4.1-4 WriteFSA
  4.1-5 IsDeterministicFSA
  4.1-6 AlphabetFSA
  4.1-7 NumberOfStatesFSA
  4.1-8 NumberOfLettersFSA
  4.1-9 AcceptingStatesFSA
  4.1-10 InitialStatesFSA
  4.1-11 DenseDTableFSA
  4.1-12 SparseTableFSA
  4.1-13 TargetDFA
  4.1-14 TargetsFSA
  4.1-15 SourcesFSA
  4.1-16 WordTargetDFA
  4.1-17 IsAcceptedWordDFA
  4.1-18 AddStateFSA
  4.1-19 DeleteStateFSA
  4.1-20 PermuteStatesFSA
  4.1-21 AddLetterFSA
  4.1-22 DeleteLetterFSA
  4.1-23 PermuteLettersFSA
  4.1-24 AddEdgeFSA
  4.1-25 DeleteEdgeFSA
  4.1-26 SetAcceptingFSA
  4.1-27 SetInitialFSA
  4.1-28 IsAccessibleFSA
  4.1-29 AccessibleFSA
  4.1-30 IsTrimFSA
  4.1-31 TrimFSA
  4.1-32 IsBFSFSA
  4.1-33 BFSFSA
  4.1-34 LSizeDFA
  4.1-35 LEnumerateDFA

4.2 Functions calling external programs

  4.2-1 DeterminizeFSA
  4.2-2 MinimizeFSA
  4.2-3 NotFSA
  4.2-4 StarFSA
  4.2-5 ReverseFSA
  4.2-6 ExistsFSA
  4.2-7 SwapCoordsFSA
  4.2-8 AndFSA
  4.2-9 OrFSA
  4.2-10 ConcatFSA
  4.2-11 LanguagesEqualFSA
  4.2-12 GrowthFSA

References

Index

kbmag

Knuth-Bendix on Monoids and Automatic Groups

Abstract

Copyright

Acknowledgements

Contents