Computational Holonomy Decomposition of Transformation Semigroups
Preprint
Abstract
We present an understandable, efficient, and streamlined proof of the Holonomy Decomposition for finite transformation semigroups and automata. This constructive proof closely follows the existing computational implementation. Its novelty lies in the strict separation of several different ideas appearing in the holonomy method. The steps of the proof and the constructions are illustrated with computed examples.Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- The q-theory of Finite Semigroups2009
- Handbook of Computational Group Theory2005
- HOLONOMY EMBEDDING OF ARBITRARY STABLE SEMIGROUPSInternational Journal of Algebra and Computation, 2002
- Groups and actions in transformation semigroupsMathematische Zeitschrift, 1998
- Finite-automaton aperiodicity is PSPACE-completeTheoretical Computer Science, 1991
- Prime decomposition theorem for arbitrary semigroups: general holonomy decomposition and synthesis theoremJournal of Pure and Applied Algebra, 1988
- A Krohn-Rhodes Theorem for categoriesJournal of Algebra, 1980
- Algebraic Theory of Automata1968
- Cascade synthesis of finite-state machinesInformation and Control, 1967