
[ ILPnet2 | Library | Newsletter | CSCW | Education | End-User Club | Events | Nodes | Systems | Applications | Members only ]
Linear Dynamic Kahn Networks are Deterministic.
A. de Bruin
and S. H. Nienhuys-Cheng.
Theoretical Computer Science, 195(1):3--32, March 1998.
Abstract
The first part of Kahn principle states that networks with deterministic nodes
are deterministic on the I/O level: for each network, different executions
provided with the same input streams deliver the same output streams. the
Kahn principle has thus far not been proved for dynamic, non-deterministic
networks. We consider a simple language L containing the fork-statement.
For this language we introduce a non-deterministic transition system which
defines all interleavings consisting of baisc steps, for all possible
executions of a program. We prove that, although on the execution level there
is much nondeterminism, this nondeterminism disappears because all executions
deliver the same output stream (or a prefix of it), given the same input
stream. This proves the Kahn principle for linear, nondeterministic dynamic
networks.
BibTeX entry.
Other publications
S-H Nienhuys-Cheng,
cheng@few.eur.nl. Last modified on Wednesday 9 April 2003 at 18:31. © 2003 ILPnet2