Skip to main content

Trajectory domains: describing the behavior of computing systems

Levin Hornischer ( University of Amsterdam )

Possibly nondeterministic discrete dynamical systems (in the most general sense) subsume (almost) all forms of computing systems (computers, neural networks, etc.). We work toward a novel general framework to uniformly describe the behavior of these systems—which is an increasingly important task. 

To do so, we first provide a notion of when two trajectories in a possibly non-deterministic system are behaviorally equivalent. We then consider the partial order of “behaviors” (equivalence classes of trajectories) ordered by extension. We identify unboundedly nondeterministic subsystems that are absent if and only if this behavior poset (capturing the long-term behavior of the system) and its order dual (capturing the history of the system) are algebraic and directed complete—whence the name “trajectory domain.” We combine these two orders in a single structure which provides a logic to reason about the behavior of the system.

Curiously, the trajectory domains bare many similarities to the causality order of spacetimes in general relativity (e.g., roughly relating cosmic censorship and bounded nondeterminism). This potentially fruitful bridge between systems and spacetimes is in need of further exploration.

Share this: