On side effect machines as a representation for evolutionary algorithms

Side Effect Machines (SEMs) have been used as a evolutionary representation in a variety of studies dealing with the classification of data for bioinformatic studies. However, up to this point there has been no formalism of the SEM in terms of its representational ability and placement within the Chomsky hierarchy; only a statement that it is a generalization of a Deterministic Finite Automation (DFA), without proof, has been provided. This paper aims to rectify that situation by presenting a formal look at SEMs in terms of the languages which they are known to accept. We give a constructive proof of how a SEM is a generalization of a DFA and are therefore able to be used to accept languages. Constructive proofs for SEMs accepting families of context-free and context-sensitive languages are also provided.