ALCOMFT-TR-01-161

Jan van Leeuwen and Jiri Wiedermann
A Computational Model of Interaction in Embedded Systems
Utrecht. Work package 4. June 2001.

Abstract: Embedded systems behave very differently from classical machine models: they interact with an unpredictable environment, they never terminate, and learn over time. We describe a simple model of interactive computing consisting of one component C and one environment E, interacting using single streams of input and output signals. The model enables a study of the computational implications of interaction. Viewing components as interactive transducers, we show that the interactive recognition and generation capabilities of components are identical. We also show that, in the given model, all interactively computable functions are limit-continuous. Several connections to the theory of omega- automata are pointed out.

Postscript file: ALCOMFT-TR-01-161.ps.gz (113 kb).