On the skeleton of a finite transformation semigroup. (English) Zbl 1208.20056

Egri-Nagy, Attila; Nehaniv, Chrystopher L.

Ann. Math. Inform. 37, 77-84 (2010).

Summary: There are many ways to construct hierarchical decompositions of transformation semigroups. The holonomy algorithm is especially suitable for computational implementations and it is used in our software package. The structure of the holonomy decomposition is determined by the action of the semigroup on certain subsets of the state set. Here we focus on this structure, the skeleton, and investigate some of its properties that are crucial for understanding and for efficient calculations.

MSC:

20M20	Semigroups of transformations, relations, partitions, etc.
20M35	Semigroups in automata theory, linguistics, etc.
68W30	Symbolic computation and algebraic computation

Keywords:

finite transformation semigroups; Krohn-Rhodes decompositions; holonomy algorithms

Software:

Krohn-Rhodes