Defining the Crick-Franklin-Watson genes of any robot (equals a finite state machine) and defining the Shannon genetic code attached to each gene. We also define the Krohn-Rhodes complexity of any regular maximal prefix code
Formal Languages and Automata Theory
Summary
The authors explore surprising links between three areas of mathematics: code and automata theory studied by Schutzenberger and colleagues, random walks on finite semigroups researched by Diaconis and others, and finite semigroup theory methods used by Margolis, Schilling, and the author to decide Krohn-Rhodes complexity. They focus on how a key lemma about complexity relates to concepts in Markov chains, including Diaconis' strong stationary time and a genetic structure in finite automata called Crick-Franklin-Watson genes. This work connects algebraic structures with probabilistic and automata theory ideas in new ways.
Authors
John Rhodes
Abstract
This paper will discuss the relationships among three pillars of mathematics: important research in codes and automata by Marcel-Paul Schutzenberger and others; random walks on finite semigroups by Persi Diaconis and others; and advanced techniques from finite semigroup theory used in proving Krohn-Rhodes complexity c is decidable by Stuart Margolis, Anne Schilling, and myself. Very surprising connections exist between the Fundamental Lemma of Complexity c (epimorphisms between finite semigroups that are one-to-one on subgroups preserve c) and coupling from the past in Markov chains, Diaconis' strong stationary time, and the Crick-Franklin-Watson genes of a finite automaton (which will be defined in the paper).