|dc.description.abstract||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
may serve 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.
Here the main aim was to open up the vast space of these decompositions
by developing a computational toolkit and to make the initial steps of the
exploration. Two different decomposition methods were implemented: the
VuT and the holonomy decomposition. Since the holonomy method, unlike
the VUT method, gives decompositions of reasonable lengths, it was chosen
for a more detailed study.
In studying the holonomy decomposition our main focus is to develop
techniques which enable us to calculate the decompositions efficiently, since
eventually we would like to apply the decompositions for real-world problems.
As the most crucial part is finding the the group components we
present several different ways for solving this problem. Then we investigate
actual decompositions generated by the holonomy method: automata with
some spatial structure illustrating the core structure of the holonomy decomposition,
cases for showing interesting properties of the decomposition
(length of the decomposition, number of states of a component), and the
decomposition of finite residue class rings of integers modulo n.
Finally we analyse the applicability of the holonomy decompositions as
formal theories of understanding, and delineate the directions for further
|dc.publisher||University of Hertfordshire||en_US
|dc.title||Algebraic hierarchical decomposition of finite state automata : a computational approach||en_US