Finite Semigroups of Constant Rank, and the five Basic State Machine types
Abstract
Description
Constant Rank (CR) state machines play an important role in the general structure theory of Finite State Machines. A machine is of constant rank if each input and input-sequence maps the state set onto the same number of next states. CR-machines are analysed via their sequential closure (semigroup), which is a simple semigroup, thus: a semi- direct product (L \times R)*G of a left- and a right-copy semigroup, and a group. . . . So in general a CR-machine is a composition of: a branch-, a reset- and a permutation machine, which are three of the five basic types of state machines, to be derived.
12 pages. Publ.: IFIP Workshop on "Logic and Architecture Synthesis", May 1990, Paris (digest publ: North-Holland, p167-176). See http://www.iae.nl/users/benschop/c-ranksm.dvi, and http://www.iae.nl/users/benschop/ism.htm (on integer state machines M[Z,A]) and http://www.iae.nl/users/benschop/cantor.htm (on 2^N < Z! = {a,b}*/Z). --- V2 corr: thm4.1c
12 pages. Publ.: IFIP Workshop on "Logic and Architecture Synthesis", May 1990, Paris (digest publ: North-Holland, p167-176). See http://www.iae.nl/users/benschop/c-ranksm.dvi, and http://www.iae.nl/users/benschop/ism.htm (on integer state machines M[Z,A]) and http://www.iae.nl/users/benschop/cantor.htm (on 2^N < Z! = {a,b}*/Z). --- V2 corr: thm4.1c