ALCOMFT-TR-03-195

Peter Verbaan, Jan van Leeuwen and Ji\vr\'\i Wiedermann
Lineages of Automata
Utrecht. Work package 4. December 2003.

Abstract: While in the series of previous papers we designed and studied a number of models of evolving interactive systems, in the present paper we concentrate on an in-depth study of a single model that turned out to be a distinguished model of evolving interactive computing: lineages of automata. A lineage consists of a sequence of interactive finite automata, with a mechanism of passing information from each automaton to its immediate successor. In this paper, we develop the theory of lineages. We give some means to construct new lineages out of given ones and prove several properties of translations that are realized by lineages. Lineages enable a definition of a suitable complexity measure for evolving systems. We show several complexity results, including a hierarchy result. Lineages are equivalent to interactive Turing machines with advice, but they stand out because they demonstrate the aspect of evolution explicitly.

Postscript file: ALCOMFT-TR-03-195.ps.gz (229 kb).