Communicating processes, scheduling, and the complexity of nontermination

DOI10.1007/BF02090765MaRDI QIDQ3034829zbMATH OpenOpenAlexFDO

Authors Hsu-Chun Yen

Publication date 1990

Published in Mathematical Systems Theory (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityschedulingcommunicating processesnontermination problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)

Recommendations

• Priority systems with many identical processes
• scientific article; zbMATH DE number 4035113
• Concurrent Probabilistic Programs, Or: How to Schedule If You Must
• Undecidability results for deterministic communicating sequential processes
• Global and local views of state fairness

Cites work

• scientific article; zbMATH DE number 3885321 (Why is no real title available?)
• scientific article; zbMATH DE number 4024804 (Why is no real title available?)
• scientific article; zbMATH DE number 4043216 (Why is no real title available?)
• scientific article; zbMATH DE number 4070338 (Why is no real title available?)
• scientific article; zbMATH DE number 4096790 (Why is no real title available?)
• scientific article; zbMATH DE number 3722109 (Why is no real title available?)
• scientific article; zbMATH DE number 3735115 (Why is no real title available?)
• scientific article; zbMATH DE number 43081 (Why is no real title available?)
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• A multiparameter analysis of the boundedness problem for vector addition systems
• An Algorithm for the General Petri Net Reachability Problem
• An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines
• Boundedness, empty channel detection, and synchronization for communicating finite automata
• Fair termination revisited - with delay
• Gradually intractable problems and nondeterministic log-space lower bounds
• On Communicating Finite-State Machines
• On the complexity of deciding fair termination of probabilistic concurrent finite-state programs
• Priority Networks of Communicating Finite State Machines
• Proof rules and transformations dealing with fairness
• Proving liveness for networks of communicating finite state machines
• Techniques for separating space complexity classes
• Termination of Probabilistic Concurrent Program
• The complexity of problems in systems of communicating sequential processes
• The complexity of reachability in distributed communicating processes
• The covering and boundedness problems for vector addition systems

Cited in

(2)

• scientific article; zbMATH DE number 3874589 (Why is no real title available?)
• scientific article; zbMATH DE number 4035113 (Why is no real title available?)

This page was built for publication: Communicating processes, scheduling, and the complexity of nontermination

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