1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#############################################################################
##
#W rwssmg.gd GAP library Isabel Araújo
##
##
#Y Copyright (C) 1997, Lehrstuhl D für Mathematik, RWTH Aachen, Germany
#Y (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
#Y Copyright (C) 2002 The GAP Group
##
## This file contains the declarations for semigroups defined by rws.
##
############################################################################
##
#A ReducedConfluentRewritingSystem( <S>[, <ordering>] )
##
## <#GAPDoc Label="ReducedConfluentRewritingSystem">
## <ManSection>
## <Attr Name="ReducedConfluentRewritingSystem" Arg='S[, ordering]'/>
##
## <Description>
## returns a reduced confluent rewriting system of
## the finitely presented semigroup or monoid <A>S</A> with respect to the
## reduction ordering <A>ordering</A> (see <Ref Chap="Orderings"/>).
## <P/>
## The default for <A>ordering</A> is the length plus lexicographic ordering
## on words, also called the shortlex ordering; for the definition see for
## example <Cite Key="Sims94"/>.
## <P/>
## Notice that this might not terminate. In particular, if the semigroup or
## monoid <A>S</A> does not have a solvable word problem then it this will
## certainly never end.
## Also, in this case, the object returned is an immutable
## rewriting system, because once we have a confluent
## rewriting system for a finitely presented semigroup or monoid we do
## not want to allow it to change (as it was most probably very time
## consuming to get it in the first place). Furthermore, this is also
## an attribute storing object (see <Ref Sect="Representation"/>).
## <Example><![CDATA[
## gap> f := FreeSemigroup( "a" , "b" );;
## gap> a := GeneratorsOfSemigroup( f )[ 1 ];;
## gap> b := GeneratorsOfSemigroup( f )[ 2 ];;
## gap> g := f / [ [ a^2 , a*b ] , [ a^4 , b] ];;
## gap> rws := ReducedConfluentRewritingSystem(g);
## Rewriting System for Semigroup( [ a, b ] ) with rules
## [ [ a*b, a^2 ], [ a^4, b ], [ b*a, a^2 ], [ b^2, a^2 ] ]
## ]]></Example>
## <P/>
## The creation of a reduced confluent rewriting system for a semigroup
## or for a monoid, in &GAP;, uses the Knuth-Bendix procedure for strings,
## which manipulates a rewriting system of the semigroup or monoid and attempts
## to make it confluent (See <Ref Chap="Rewriting Systems"/>.
## See also Sims <Cite Key="Sims94"/>).
## (Since the word problem for semigroups/monoids is not solvable in general,
## Knuth-Bendix procedure cannot always terminate).
## <P/>
## In order to apply this procedure we will build a rewriting system
## for the semigroup or monoid, which we will call a <E>Knuth-Bendix Rewriting
## System</E> (we need to define this because we need the rewriting system
## to store some information needed for the implementation of the
## Knuth-Bendix procedure).
## <P/>
## Actually, Knuth-Bendix Rewriting Systems do not only serve this purpose.
## Indeed these are objects which are mutable and which can be manipulated
## (see <Ref Chap="Rewriting Systems"/>).
## <P/>
## Note that the implemented version of the Knuth-Bendix procedure, in &GAP;
## returns, if it terminates, a confluent rewriting system which is reduced.
## Also, a reduction ordering has to be specified when building a rewriting
## system. If none is specified, the shortlex ordering is assumed
## (note that the procedure may terminate with a certain ordering and
## not with another one).
## <P/>
## On Unix systems it is possible to replace the built-in Knuth-Bendix by
## other routines, for example the package <Package>kbmag</Package> offers
## such a possibility.
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("ReducedConfluentRewritingSystem",IsSemigroup);
#############################################################################
##
#A FreeMonoidOfRewritingSystem(<rws>)
##
## <#GAPDoc Label="FreeMonoidOfRewritingSystem">
## <ManSection>
## <Attr Name="FreeMonoidOfRewritingSystem" Arg='rws'/>
##
## <Description>
## returns the free monoid over which <A>rws</A> is
## a rewriting system
## <Example><![CDATA[
## gap> f1 := FreeSemigroupOfRewritingSystem(rws);
## <free semigroup on the generators [ a, b ]>
## gap> f1=f;
## true
## gap> g1 := SemigroupOfRewritingSystem(rws);
## <fp semigroup on the generators [ a, b ]>
## gap> g1=g;
## true
## ]]></Example>
## <P/>
## As mentioned before, having a confluent rewriting system, one can decide
## whether two words represent the same element of a finitely
## presented semigroup (or finitely presented monoid).
## <P/>
## <Example><![CDATA[
## gap> a := GeneratorsOfSemigroup( g )[ 1 ];
## a
## gap> b := GeneratorsOfSemigroup( g )[ 2 ];
## b
## gap> a*b*a=a^3;
## true
## gap> ReducedForm(rws,UnderlyingElement(a*b*a));
## a^3
## gap> ReducedForm(rws,UnderlyingElement(a^3));
## a^3
## ]]></Example>
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("FreeMonoidOfRewritingSystem",
IsRewritingSystem);
#############################################################################
##
#A FamilyForRewritingSystem(<rws>)
##
## <ManSection>
## <Attr Name="FamilyForRewritingSystem" Arg='rws'/>
##
## <Description>
## returns the family of words over which <A>rws</A> is
## a rewriting system
## </Description>
## </ManSection>
##
DeclareAttribute("FamilyForRewritingSystem",
IsRewritingSystem);
#############################################################################
##
#A FreeSemigroupOfRewritingSystem(<rws>)
##
## <#GAPDoc Label="FreeSemigroupOfRewritingSystem">
## <ManSection>
## <Attr Name="FreeSemigroupOfRewritingSystem" Arg='rws'/>
##
## <Description>
## returns the free semigroup over which <A>rws</A> is
## a rewriting system
## </Description>
## </ManSection>
## <#/GAPDoc>
##
DeclareAttribute("FreeSemigroupOfRewritingSystem",
IsRewritingSystem);
#############################################################################
##
#F ReduceLetterRepWordsRewSys(<tzrules>,<w>)
##
## <ManSection>
## <Func Name="ReduceLetterRepWordsRewSys" Arg='tzrules,w'/>
##
## <Description>
## Here <A>w</A> is a word of a free monoid or a free semigroup in tz
## represenattion, and <A>tzrules</A> are rules in tz representation. This
## function returns the reduced word in tz representation.
## <P/>
## All lists in <A>tzrules</A> as well as <A>w</A> must be plain lists, the entries
## must be small integers. (The behaviour otherwise is unpredictable.)
## </Description>
## </ManSection>
##
DeclareGlobalFunction("ReduceLetterRepWordsRewSys");
#############################################################################
##
#E
|
