|
# This files contains the functions:
# DTP_SolveEquation
# DTP_Inverse
# DTP_Exp
# DTP_NormalForm
# DTP_Order
#
# DTP_DetermineMultiplicationFunction
# DTP_IsInNormalForm
# _DTP_DetermineNormalForm
# _DTP_DetermineOrder
#
# DTP_PCP_SolveEquation
# DTP_PCP_Inverse
# DTP_PCP_Exp
# DTP_PCP_NormalForm
# DTP_PCP_Order
##############################################################################
# Each application (DTP_SolveEquation, DTP_NormalForm, DTP_Order, ...) may
# take an DTObj where DTObj![PC_DTPPolynomials] is either the output of the
# function DTP_DTpols_rs or the output of DTP_DTpols_r. Let
# polynomials := DTObj![PC_DTPPolynomials].
# Since the condition IsInt(polynomials[1][1][1]) is true if and only if
# "polynomials" is the ouput of DTP_DTpols_r, we can decide which
# multiplication function we should use for computations. Explanation:
# For DTP_DTpols_r:
# polynomials[1] <-> f_1
# polynomials[1][1] <-> first g_alpha in f_1
# polynomials[1][1][1] <-> constant coefficient in first g_alpha in f_1
#
# For DTP_DTpols_rs:
# polynomials[1] <-> list of the n polynomials f_{r, 1} (1 <= r <= n)
# polynomials[1][1] <-> polynomial f_{1, 1}
# polynomials[1][1][1] <-> first g_alpha in f_{1, 1}, this is a list
#
# Hence, we can determine the suitable multiplication function "multiply"
# by using
# if IsInt(DTObj![PC_DTPPolynomials][1][1][1]) then
# # version f_r
# multiply := DTP_Multiply_r;
# else
# # version f_rs
# multiply := DTP_Multiply_rs;
# fi;
# Input: DTObj
# Output: function DTP_Multiply_r or DTP_Multiply_rs depending on whether
# polynomials f_r or f_rs were computed for DTObj.
InstallGlobalFunction( DTP_DetermineMultiplicationFunction,
function(DTObj)
if IsInt(DTObj![PC_DTPPolynomials][1][1][1]) then
# version f_r
return DTP_Multiply_r;
else
# version f_rs
return DTP_Multiply_rs;
fi;
end) ;
# Input: - exponent vectors x, z
# - DTObj
# Output: exponent vector y such that for the corresponding elements
# x * y = z. If DTObj![PC_DTPConfluent] = true, y describes a normal
# form.
InstallGlobalFunction( DTP_SolveEquation,
function(x, z, DTObj)
local y, i, n, multiply;
multiply := DTP_DetermineMultiplicationFunction(DTObj);
n := DTObj![PC_NUMBER_OF_GENERATORS];
y := [];
# both exponent vectors must have length n
if Length(x) <> n or Length(z) <> n then
Error("Exponent vectors x and z must have length ", n);
fi;
for i in [1 .. n] do
# Loop invariant:
# x = a_1^z_1 ... a_{i-1}^{z_{i-1}} * a_i^x_i ... a_n^x_n
y[i] := z[i] - x[i];
# calculate x * a_i^y_i
x := multiply(x, ExponentsByObj(DTObj, [i, y[i]]), DTObj);
od;
# Now by the loop invariant: x = z
# On the other hand: x = x * y by construction
if DTObj![PC_DTPConfluent] then
return DTP_NormalForm(y, DTObj);
else
return y;
fi;
end) ;
# Input: pcp elements pcp1, pcp2 belonging to the same collector
# Output: pcp element res such that pcp1 * res = pcp2
InstallGlobalFunction( DTP_PCP_SolveEquation,
function(pcp1, pcp2)
local dtobj;
dtobj := Collector(pcp1);
if not IsDTObj(dtobj) then
Error("Collector(pcp1) must be a DTObj");
elif not Collector(pcp2) = dtobj then
Error("pcp1 and pcp2 must belong to the same DTObj");
else
return PcpElementByExponentsNC(dtobj, DTP_SolveEquation(Exponents(pcp1), Exponents(pcp2), dtobj));
fi;
end );
# Input: - exponent vector x
# - DTObj
# Output: exponent vector of x^{-1}. If DTObj![PC_DTPConfluent] = true, y
# describes a normal form.
InstallGlobalFunction( DTP_Inverse,
function(x, DTObj)
local n;
n := DTObj![PC_NUMBER_OF_GENERATORS];
return DTP_SolveEquation(x, [1 .. n] * 0, DTObj);
end) ;
# Input: pcp element pcp
# Output: inverse of pcp as pcp element
InstallGlobalFunction( DTP_PCP_Inverse,
function(pcp)
local dtobj;
dtobj := Collector(pcp);
if not IsDTObj(dtobj) then
Error("Collector(pcp) must be a DTObj");
else
return PcpElementByExponentsNC(dtobj, DTP_Inverse(Exponents(pcp), dtobj));
fi;
end );
# DTP_IsInNormalFrom checks whether the element described by the exponent
# vector x is in normal form or not.
# It returns "true", if x describes a normal form and otherwise
# the smallest generator index for which the condition
# r[i] <> 0 and (x[i] < 0 or x[i] >= r[i])
# is NOT fulfilled is returned. Here, r = RelativeOrders(coll).
InstallGlobalFunction( DTP_IsInNormalForm,
function(x, coll)
local i, r;
r := RelativeOrders(coll);
# If the relative order r[i] is finite, check whether
# 0 <= x[i] < r[i] is fulfilled.
for i in [1 .. coll![PC_NUMBER_OF_GENERATORS]] do
if r[i] <> 0 then
if x[i] < 0 or x[i] >= r[i] then
return i;
fi;
fi;
od;
return true;
end) ;
# Input: - exponent vector x
# - integer q
# - DTObj
# Output: exponent vector of x^q. If DTObj![PC_DTPConfluent] = true, then
# the result is in normal form.
InstallGlobalFunction( DTP_Exp,
function(x, q, DTObj)
local multiply, y;
multiply := DTP_DetermineMultiplicationFunction(DTObj);
y := [1 .. NumberOfGenerators(DTObj)] *0; # y = 1
if q < 0 then
x := DTP_Inverse(x, DTObj);
q := -q;
fi;
while q > 0 do
if q mod 2 = 1 then
y := multiply(y, x, DTObj);
fi;
q := QuoInt(q, 2);
x := multiply(x, x, DTObj);
od;
return y;
end) ;
# Input: - pcp element pcp
# - integer q
# Output: pcp^q
InstallGlobalFunction( DTP_PCP_Exp,
function(pcp, q)
local dtobj, exp;
dtobj := Collector(pcp);
if not IsDTObj(dtobj) then
Error("Collector(pcp) must be a DTObj");
else
exp := ShallowCopy(Exponents(pcp));
return PcpElementByExponentsNC(dtobj, DTP_Exp(exp, q, dtobj));
fi;
end );
# Input: - exponent vector x
# - DTObj
# - empty list nf = [] where normal form is stored
# - function multiply which is either DTP_Multiply_r or
# DTP_Multiply_rs depending the polynomials used in DTObj
# Output: exponent vector of the normal form of x
_DTP_DetermineNormalForm := function(x, DTObj, nf, multiply)
local n, j, i, q, r, q_list, l, z, pwr, k, w1, w2, w;
# DTObj![PC_DTPPolynomials] = DTpols(coll)
n := DTObj![PC_NUMBER_OF_GENERATORS];
# find j = min{ 1 <= i <= n | s_i < infinity and
# (x_i < 0 or x_i >= s_i) } \cup {infinity}
j := DTP_IsInNormalForm(x, DTObj);
if j <> true then
# replace a_j^x[j] by suitable power of the power relation a_j^s_j
# x[j] = q * rel_orders[j] + r, 0 <= r < rel_orders[j]:
r := x[j] mod RelativeOrders(DTObj)[j];
q := (x[j] - r)/RelativeOrders(DTObj)[j];
# In the following, compute w = w1 * w2, where
# w1 = ( a_j^rel_orders[j] )^q
# = ( a_{j + 1}^{c_{j, j, j + 1}} ... a_n^{c_{j, j, n}} )^q
# and
# w2 = a_{j + 1}^{x_{j + 1}} ... a_n^{x_n}
# Then w only depends on the generators a_{j + 1}, ..., a_n and
# its normal form can be computed (recursively).
pwr := GetPower(DTObj, j);
# z = a_{j + 1}^c_{j, j, j + 1} ... a_n^{c_{j, j, n}}
z := [1 .. n] * 0;
for k in [1, 3 .. (Length(pwr) - 1)] do
z[pwr[k]] := pwr[k + 1];
od;
# Compute w1 = z^q
w1 := DTP_Exp(z, q, DTObj);
# w2 = a_{j + 1}^{x_{j + 1}} ... a_n^{x_n}
w2 := [1 .. j] * 0; # [0, ..., 0] of length j
for i in [(j + 1) .. n] do
Add(w2, x[i]);
od;
# w = w1 * w2
w := multiply(w1, w2, DTObj);
# At this point, nf is a list describing the beginning of the
# exponent vector of the normal form of x. If some relative orders
# are infinite, the corresponding exponents in x are simply added,
# and lastly the exponent r of the generator a_j is added. Afterwards,
# nf is a list of length j, which must be completed in the following
# recursion steps, in which the normal form of "the rest" w" of x is
# computed.
for i in [(Length(nf) + 1) .. (j - 1)] do
Add(nf, x[i]);
od;
Add(nf, r); # j-th entry
return _DTP_DetermineNormalForm(w, DTObj, nf, multiply);
else
# Since all further relative orders are infinite, the word is
# now in normal form and we simply append the exponents to the
# already calculated normal form nf.
for i in [(Length(nf) + 1) .. n] do
Add(nf, x[i]);
od;
return nf;
fi;
end;
# Input: - exponent vector x
# - DTObj
# Output: exponent vector of normal form of x
InstallGlobalFunction( DTP_NormalForm,
function(x, DTObj)
local multiply;
multiply := DTP_DetermineMultiplicationFunction(DTObj);
return _DTP_DetermineNormalForm(x, DTObj, [], multiply);
end );
# Input: pcp element
# Output: pcp element in normal form
InstallGlobalFunction( DTP_PCP_NormalForm,
function(pcp)
local dtobj;
dtobj := Collector(pcp);
if not IsDTObj(dtobj) then
Error("Collector(pcp) must be a DTObj");
elif not dtobj![PC_DTPConfluent] = true then
Error("collector must be confluent");
else
return PcpElementByExponentsNC(dtobj, DTP_NormalForm(Exponents(pcp), dtobj));
fi;
end );
# Input: - exponent vector x (must describe a normal form)
# - DTObj
# Output: order of x in group of coll
_DTP_DetermineOrder := function(x, DTObj, multiply)
local j, s, ord;
ord := 1;
# DTObj![PC_DTPPolynomials] = DTpols(coll)
while x <> [1 .. DTObj![PC_NUMBER_OF_GENERATORS]] * 0 do
j := 1;
while x[j] = 0 do
j := j + 1; # exists, since x <> neutral element
od;
if RelativeOrders(DTObj)[j] = 0 then # relative order s_j = infinity
return infinity;
else
# s = s_j/gcd(s_j, x_j)
s := RelativeOrders(DTObj)[j]/Gcd(RelativeOrders(DTObj)[j], x[j]);
# ord(x) = infinity <=> ord(x^s) = infinity
# ord(x) < infinity => s | ord(x)
# Compute y = x^s:
x := DTP_Exp(x, s, DTObj);
# The normal form of x is needed, i.e. isConfl = true!
# (Otherwise one may run into a infinite recursion, since the
# termination of the algorithm needs the normal form of x to
# begin with a generator with index greater than j.)
ord := ord * s;
fi;
od;
return ord;
end;
# Input: - exponent vector x
# - DTObj
# Output: order of x in group of coll
InstallGlobalFunction( DTP_Order,
function(x, DTObj)
local multiply;
multiply := DTP_DetermineMultiplicationFunction(DTObj);
# check whether x is in normal form, if not call _DTP_DetermineNormalForm
# DTP_IsInNormalForm returns true or an intger, if not in normal form
if DTP_IsInNormalForm(x, DTObj) <> true then
x := _DTP_DetermineNormalForm(x, DTObj, [], multiply);
fi;
return _DTP_DetermineOrder(x, DTObj, multiply);
end );
# Input: pcp element
# Output: order of pcp
InstallGlobalFunction( DTP_PCP_Order,
function(pcp)
local dtobj;
dtobj := Collector(pcp);
if not IsDTObj(dtobj) then
Error("Collector(pcp) must be a DTObj");
elif not dtobj![PC_DTPConfluent] = true then
Error("collector must be confluent");
else
return DTP_Order(Exponents(pcp), dtobj);
fi;
end );
[ Verzeichnis aufwärts0.35unsichere Verbindung
Übersetzung europäischer Sprachen durch Browser
]
|
