Logic in Computer Science (LICS 1989)

Paper: Nets and data flow interpreters (at LICS 1989)

Authors: Rabinovich, A. Trakhtenbrot, B.A.

Abstract

The authors investigate and compare two ways of specifying stream relations (in particular, stream functions). The first uses relational programs, i.e., netlike program schemes in which the signature primitives are interpreted as relations over a given CPO. No stream domains are assumed; semantics is in fixed-point style. The second is through data flow nets, i.e., nets whose nodes are interpreted as processes (computational stations). The authors prove the existence of an adequate data flow interpreter for relational programs over all relations and its uniqueness. When dealing with functions the interpreter is modular and obeys the Kahn principle, the authors identify two kinds of anomalies. The first (meagerness anomaly) is caused by the defect of the used processes (computational stations) and holds in fact for arbitrary input-output behaviors. The second (ambiguity anomaly) is rooted in the semantics of relational nets over arbitrary CPO. It is unavoidable in any extension beyond functional behaviors

BibTeX

  @InProceedings{RabinovichTrakhtenb-Netsanddataflowinte,
    author = 	 {Rabinovich, A. and Trakhtenbrot, B.A.},
    title = 	 {Nets and data flow interpreters},
    booktitle =  {Proceedings of the Fourth Annual IEEE Symp. on Logic in Computer Science, {LICS} 1989},
    year =	 1989,
    editor =	 {Rohit Parikh},
    month =	 {June}, 
    pages =      {164--174},
    location =   {Pacific Grove, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }