Priority systems with many identical processes (Q758201)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Priority systems with many identical processes |
scientific article |
Statements
Priority systems with many identical processes (English)
0 references
1991
0 references
We consider the termination problem for systems with an arbitrary number of identical priority finite-state processes. In our model, the number of finite-state processes involved in the computation is arbitrary, and a priority is assigned to each transition of a process to indicate the degree of importance or urgency. We show that the termination problem is undecidable for such systems, even when the underlying interprocess communication structure is a star. The undecidability result holds for systems with acyclic processes as well. However, if we require that no two processes reside in the same state (except the starting state) during the course of the computation, the termination problem is PSPACE- complete. Finally, we show that if the priority relation is empty, the problem become PTIME-complete.
0 references
priority systems
0 references
processes
0 references
termination
0 references
0 references