BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-80-768
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Causal nets or what is a deterministic computation
        TYPE:: Technical Report
      AUTHOR:: Gacs, Peter
      AUTHOR:: Levin, Leonid A.
        DATE:: October 1980
       PAGES:: 16
    ABSTRACT:: We introduce the concept of causal nets - it can be
               considered as the most general and elementary concept of the
               history of a deterministic computation (sequential or
               parallel). Causality and locality are distinguished as the
               only important properties of nets representing such records.
               Different types of complexities of computations correspond to
               different geometrical characteristics of the corresponding
               causal nets - which have the advantage of being finite
               objects. Synchrony becomes a relative notion. Nets can have
               symmetries; therefore it will make sense to ask what can be
               computed from arbitrary symmetric inputs. Here, we obtain a
               complete group-theoretical characterization of the kind of
               symmetries that can be allowed in parallel computations.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-80-768