Realization with Feedback Encoding. I: Analogues of the Classical Theory
Dennis P. Geller · SIAM Journal on Computing · 1975
For a finite state machine M to realize a machine $M'$, we usually precede M by a memory-less input encoder to translate inputs intended for $M'$ into the input alphabet of M. In this paper we introduce a modification to this paradigm by introducing feedback from the state of the realizing machine to the input encoder. The resulting form of realization depends in a very strong way on (graph) structural properties of the two machines. The characterization theorem, giving necessary and sufficient conditions for one machine to realize another in this way, involves a new class of mappings between digraphs. We also investigate a corresponding algebraic structure theory.