Presheaf automata extend models for concurrent system behavior
Track objects in cubical presheaf automata
Formal Languages and Automata Theory
Summary
Understanding how multiple tasks can run at the same time in computer systems is a complex problem. The authors introduced a new type of mathematical model called presheaf automata to better represent these simultaneous activities. Their approach expands existing models that describe concurrent processes and helps capture the ways distinct tasks interact. They also analyzed the kinds of patterns these models can describe using mathematical structures called posetal cospans.
What this means in practice
- •For distributed system engineers: Model complex interactions of concurrent components in distributed software using enhanced automata frameworks.
- •For programming language designers: Design formal semantics for concurrent programming languages supporting advanced synchronization patterns.
A theory result. No direct application yet.
Authors
Georg Struth, Krzysztof Ziemiański
Abstract
Using the formalism of presheaf automata, we introduce new classes of automata for modelling concurrency that extend higher-dimensional automata and symmetric higher-dimensional automata. We study their languages and characterise these languages in terms of posetal cospans.