| | | **The group action on the domain of functions** |

# The group action on the domain of functions

Algorithms and methods for the computation of orbit representatives
of group actions in form of
definition are well studied.
Usually [12]
the sets *X* and *Y* are labelled by the elements of
__n__:={1,...,n} and __m__
such that functions *f* in *Y*^{X} can be represented as *n*-tuples
*(f(1),...,f(n))Î*__m__^{n}. Now the set of these functions
is totally ordered by the lexicographical ordering, and we usually choose
as the *canonic* representative of an orbit its smallest
(or largest) element.
In most cases it is useful to compute a Sims-chain
([20]) of the acting group.
Then all group elements can be represented as nodes in a tree built from
the strong generators of *G*. Listing all elements means running through
this tree.

To compute a transversal of these orbits we have to proceed in the
following way:
For each *fÎY*^{X} we determine whether it is a canonic
representative of
its orbit (i.e. it is the smallest (or largest) element in *G(f)*.)
In other words, *f* is a canonic representative if and only if
*f£f o g* for all *gÎG*.
By using the algorithm of *orderly generation* combined with
*Reads method of recursion*
[3][4][16][17]
[18] some
*learning techniques* [9]
and recursion on the cardinality of the range (by applying the
homomorphism principle)
we get quite an efficient algorithm which
can be used to produce a catalogue of all graphs on *v£10* points
[10]
or a list of all 0-1-matrices under the action of the direct
product of symmetric groups (the *contexts* that are of interest
for the concept analysis) or transversals of *k*-motives
[8]
(which are orbits of *k*-subsets of *Z*_{n}´Z_{n} under the action
of *affine groups*.)

harald.fripertinger@kfunigraz.ac.at,

last changed: January 23, 2001

| | | **The group action on the domain of functions** |