Causal nets or what is a deterministic computation

[摘要] 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.

[学科分类] 计算机科学（综合）