The complexity of reachability in distributed communicating processes

DOI10.1007/BF02737107zbMath0637.68032OpenAlexW4253760428MaRDI QIDQ1098622

John H. Reif, Scott A. Smolka

Publication date: 1988

Published in: Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityreachabilityPetri netsdeadlockscommunicating processesdecidable modelsHabermann's path expressions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Theory of operating systems (68N25)

Related Items

Communicating processes, scheduling, and the complexity of nontermination ⋮ Data flow analysis of distributed communicating processes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data flow analysis of distributed communicating processes
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Unboundedness detection for a class of communicating finite-state machines
• Exposure to deadlock for communicating processes is hard to detect
• The complexity of problems in systems of communicating sequential processes
• A calculus of communicating systems
• The covering and boundedness problems for vector addition systems
• A multiparameter analysis of the boundedness problem for vector addition systems
• Boundedness, empty channel detection, and synchronization for communicating finite automata
• The complexity of the word problems for commutative semigroups and polynomial ideals
• On Communicating Finite-State Machines
• Priority Networks of Communicating Finite State Machines
• A Unified Approach to Path Problems
• Fast Algorithms for Solving Path Problems
• Communicating sequential processes
• High level programming for distributed computing
• The complexity of theorem-proving procedures