zbMATH — the first resource for mathematics

Interaction and realizability. (English) Zbl 1132.68031
van Leeuwen, Jan (ed.) et al., SOFSEM 2007: Theory and practice of computer science. 33rd conference on current trends in theory and practice of computer science, Harrachov, Czech Republic, January 20–26, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-69506-6/pbk). Lecture Notes in Computer Science 4362, 29-50 (2007).
Summary: We deal with the issue of realizability and computability of interactive interface behaviors as described in [M. Broy and K. Stølen, Specification and development of interactive systems. Focus on streams, interfaces, and refinement. New York, NY: Springer (2001; Zbl 0981.68115)]. We treat the following aspects of interactive behaviors that are represented by relations between communication streams:
– Causality between input and output streams
– Realizability of single output histories for given input histories
– The role of non-realizable output in specific system contexts and for composition
– Relating non-realizable behaviors to state machines
– The concept of interactive computation and computability
Finally, we relate our results to classical notions of computability. The main goal of this paper is the characterization of a general concept of interactive interface behavior as basis for the extension and generalization of the notion of computability to interactive behaviors.
For the entire collection see [Zbl 1129.68007].

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI