The group action on the range of functionsTopGeneral routinesThe 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 YX can be represented as n-tuples (f(1),...,f(n))Îmn. 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ÎYX 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 Zn´Zn under the action of affine groups.)

harald.fripertinger@kfunigraz.ac.at,
last changed: January 23, 2001

The group action on the range of functionsTopGeneral routinesThe group action on the domain of functions