Services as a Paradigm of Computation - Formal Methods and Hybrid Real-Time Systems - page 522

1.2 Proposals to Adjust the Classical Paradigm
Church's thesis has dominated the discussion on the limits of computation since
this kind of discussion has started in the 1950ies. It is overwhelmingly agreed
that this thesis is most convincing when it comes to the computation of functions
over sequences of symbols (for more details on this discussion we refer to [1]).
Nevertheless, it has frequently been argued that the classical paradigm of
computable functions does not comprise all important aspects of the expres-
sive power of information technology. We have discussed one such aspect above
already. Here we survey a number of system models, all contributing to the
non-standard aspects of communication, synchronization, and reactivity.
Petri nets : With his seminal Ph.D. thesis “Communication with Automata” [2],
Carl Adam Petri pointed at the fundamental role of asynchronous, communicat-
ing processes, already in the early 1960ies. This led to the development of Petri
nets as a technique to model concurrent behavior.
The decisive aspect of Petri nets in this context is the local character of its
transitions. A behavior then is not a sequence of global states and steps, but a set
of transition occurrences partially ordered by the relation of causality. This per-
ception brought new insights into the fundamental notions of nondeterminism,
fairness, scenarios, and others.
Omega-automata : ω -Automata [3] capture sequential, infinite computation in
the late 1960ies already, laying ground for infinite, reactive computations.
Stream processing functions : The first proposals to model systems consisting of
interacting components conceive a system component as a stream processing
function (or, in the nondeterministic case, as a relation). This dates back to the
early 1970ies already. As a typical example we refer to [4]. Streams (i.e. finite
or infinite sequences) of data on the input ports of a stream processing function
f are transformed into streams of data on the output ports of f . One system's
output stream may be an other system's input stream. The FOCUS formalism [5]
pursues this line of research. Stream processing functions are most adequate to
describe a single system's semantics in isolation. The formalism properly reflects
that a system's intermediate output can affect later input, via cooperation with
the environment.
Process algebras : First suggested by Robin Milner in the late 1970ies [6] process al-
gebras capture synchronous communication. The fundamental question of equiv-
alence between system models gave rise to the notion of simulation and bisimula-
tion. It has been a matter of surprise that those notions can not be simply captured
in terms of formal language containment or equality.
Interface variables and remote calls : In the framework of programming lan-
guages, reactive behaviour can easily be represented by help of variables, shared
by the program and its environment. This has been done since the late 1960ies. It
has later been adapted by specification techniques such as Lamport's Temporal
Logic of Actions [7], as well as Gurevich's Abstract State Machines [8]. Fairly