|
GSO-2011: Chrystopher Nehaniv
Hierarchical Coordinate Systems on Symmetry Structures and Automata Discrete dynamical systems and computational structures can be mathematically understood, decomposed manipulated, and synthesized with the help of algebraic automata theory. Symmetries lead to hierarchical coordinate systems, invariants, and conservation laws. In the realm of reversible computation, we illustrate how every symmetry structure (permutation group) can be decomposed in the iterated wreath product (feedforward cascade) of simple permutation components, and how to compute with the resulting "Frobenius-Lagrange" coordinate system. (For example, for the Rubik's cube permutation puzzle, solving strategies appear to correspond to the use of such coordinate systems in which one can solve the cube via successive approximation in coordinate-form according to a given subgroup chain.) More generally, any discrete dynamical system can similarly be decomposed using the iterated wreath product permutation groups and identity-reset automata. In the finite case, this is a Krohn-Rhodes decomposition that allows us to find the fundamental building blocks of the system and how they can be put to together to achieve its behaviour. These hierarchical coordinate systems allow one to manipulate the dynamical system via coarse-level to successively finer-level, convergent approximations. [These results, original formulated for finitary deterministic systems, generalize in various ways to non-deterministic or probabilistic and to infinite systems.] Applications include understanding the dynamics of numerous physical and geometric systems, biological networks (e.g. biochemical and genetic regulatory systems), permutation puzzles, and von Neumann games. The methods also give rise to a natural complexity theory for finitary computation. Open-source computer algebraic software to carry out these decompositions has been developed at the University of Hertfordshire together with Attila Egri-Nagy. References John Rhodes (2009). Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games. Edited by C. L. Nehaniv, Foreword by M. W. Hirsch. Singapore: World Scientific Publishing Company. Attila Egri-Nagy, Chrystopher L. Nehaniv(2008) "Hierarchical Coordinate Systems for Understanding Complexity and its Evolution with Applications to Genetic Regulatory Networks". Artificial Life (Massachusetts Institute of Technology) 14 (3): 299тАУ312. doi:10.1162/artl.2008.14.3.14305. ISSN 1064-5462. Attila Egri-Nagy, Chrystopher L. Nehaniv, "SgpDec - Hierarchical Composition and Decomposition of Permutation Groups and Transformation Semigroups", Open Source Package for the GAP computer algebra system. http://sgpdec.sourceforge.net/ Attila Egri-Nagy, Chrystopher L. Nehaniv, (2009) "Subgroup Chains and Lagrange Coordinatizations of Finite Permutation Groups", arXiv:0911.5433v1 [math.GR] http://arxiv.org/abs/0911.5433 |