Computing on semaphores of Dijkstra with place-transition nets
Abstract
We consider the System V operation over a set of Dijkstra semaphores as a formal system and prove its Turing completeness. In this way, we define place-transition nets with a novel, stepless semantics, which implement transition firing rules similar to those of Petri and Salwicki. Each transition represents a thread, repeating an operation over a set of semaphores, which specify transition's incident arcs. To represent an efficient Sleptsov-Salwicki firing rule, a generalized operation over a set of semaphores is introduced. This opens prospects for fast asynchronous hardware and software implementations for the corresponding graphical language of concurrent programming.
Fields of Study & Subjects
Petri Nets in System Modeling
Logic
programming
and type systems
semigroups and automata theory
Publication details
- Journal / source
- International Journal of Parallel Emergent and Distributed Systems
- Volume
- 41
- Issue
- 3
- Pages
- 291–320
- Publication date
- 14 January 2026
- Language
- EN