Formal Models of Understanding
Algebraic Hierarchical Decomposition of Finite Automata

The theory of algebraic hierarchical decomposition of finite state automata is an important and well developed branch of theoretical computer science (Krohn-Rhodes Theory). Beyond this it gives a general model for some important aspects of our cognitive capabilities and also provides possible means for constructing artificial cognitive systems: a Krohn-Rhodes decomposition serves as a formal model of understanding since we comprehend the world around us in terms of hierarchical representations. In order to investigate formal models of understanding using this approach, we need efficient tools but despite the significance of the theory there has been no computational implementation until this work.

  1. [ENG] Algebraic Hierarchical Decomposition of Finite State Automata PhD thesis PS PDF
  2. [HUN] A megértés koordináta-rendszerei elõadásPDF
  3. [ENG] Coordinate Systems of Understanding UH Research Colloqium Seminar 2006.03.08 PDF

  • Krohn-Rhodes VUT decomposition implemented in GAP as a package (in CVS as grasp)
  • engine for working with finite ts's including the Holonomy decomposition with the mapping back implemented in JAVA (in CVS as jgrasp, as experimental tool it's hard to point out a particular state of the source and release. It may eventually happen of course.) It happened, it can be downloaded from sourceforge.
  • The final version of the holonomy decomposition will be written as a GAP package.
Example decompositions:
2005.12.03. Mátraderecske,Hungary,Earth
Attila Egri-Nagy
Chrystopher L. Nehaniv

Computational Semigroup Theory

Beware of Combinatorial Explosions!!! Logo