Priority systems with many identical processes

DOI10.1007/BF01178682MaRDI QIDQ758201zbMATH OpenOpenAlexFDO

Authors Hsu-Chun Yen

Publication date 1991

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01178682

zbMATH Keywords

priority systemsprocessestermination

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• Communicating processes, scheduling, and the complexity of nontermination
• Priority Networks of Communicating Finite State Machines
• scientific article; zbMATH DE number 3881887
• The Power of Priority Channel Systems
• On the complexity of deciding fair termination of probabilistic concurrent finite-state programs

Cites work

• Automatic verification of finite-state concurrent systems using temporal logic specifications
• Complete problems for deterministic polynomial time
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
• Priority Networks of Communicating Finite State Machines
• Reasoning about networks with many identical finite state processes

Cited in

(5)

• Communicating processes, scheduling, and the complexity of nontermination
• Termination and Divergence Are Undecidable Under a Maximum Progress Multi-step Semantics for LinCa
• The power of priority channel systems
• Deciding bisimulation and trace equivalences for systems with many identical processes
• Deciding bisimulation and trace equivalences for systems with many identical processes

This page was built for publication: Priority systems with many identical processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q758201)