Abstract
Embedded systems behave very dierently from classical machine models: they
interact with an unpredictable environment, they never terminate, and learn over time. The behavior of embedded systems has been well-studied in concurrency theory but Wegner [29, 30] recently appealed for a new theory, claiming that the computational features of interaction are not adequately captured by traditional models of computation.
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 us to study 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. An interesting inversion theorem is proved. Several connections to the theory of ω-automata are pointed out, placing the subject area in a classical framework.
interact with an unpredictable environment, they never terminate, and learn over time. The behavior of embedded systems has been well-studied in concurrency theory but Wegner [29, 30] recently appealed for a new theory, claiming that the computational features of interaction are not adequately captured by traditional models of computation.
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 us to study 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. An interesting inversion theorem is proved. Several connections to the theory of ω-automata are pointed out, placing the subject area in a classical framework.
| Original language | English |
|---|---|
| Place of Publication | Utrecht |
| Publisher | Utrecht University: Information and Computing Sciences |
| Number of pages | 18 |
| Publication status | Published - Jan 2001 |
Publication series
| Name | Technical report UU-CS |
|---|---|
| No. | 02 |
| Volume | 2001 |
| ISSN (Print) | 0924-3275 |