Priority Networks of Communicating Finite State Machines
- 1 August 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (3), 569-584
- https://doi.org/10.1137/0214042
Abstract
Consider a network of two communicating finite state machines which exchange messages over two one-directional, unbounded channels, and assume that each machine receives the messages from its input channel based on some fixed (partial) priority relation. We address the problem of whether the communication of such a network is deadlock-free and bounded. We show that the problem is undecidable if the two machines exchange two types of messages. The problem is also undecidable if the two machines exchange three types of messages, and one of the channels is known to be bounded. However, if the two machines exchange two (or less) types of messages, and one channel is known to be bounded, then the problem becomes decidable. The problem is also decidable if one machine sends one type of message and the second machine sends two (or less) types of messages; the problem becomes undecidable if the second machine sends three types of messages. The problem is also decidable if the message priority relation is empty. We also address the problem of whether there is a message priority relation such that the priority network behaves like a FIFO network. We show that the problem is undecidable in general, and present some special cases for which the problem becomes decidable.Keywords
This publication has 11 references indexed in Scilit:
- Unboundedness detection for a class of communicating finite-state machinesInformation Processing Letters, 1983
- On Communicating Finite-State MachinesJournal of the ACM, 1983
- Deadlock Detection for a Class of Communicating Finite State MachinesIEEE Transactions on Communications, 1982
- On restricted one-counter machinesTheory of Computing Systems, 1981
- Finite state description of communication protocolsComputer Networks (1976), 1978
- The covering and boundedness problems for vector addition systemsTheoretical Computer Science, 1978
- Reversal-Bounded Multicounter Machines and Their Decision ProblemsJournal of the ACM, 1978
- Deterministic one-counter automataJournal of Computer and System Sciences, 1975
- Relationships between nondeterministic and deterministic tape complexitiesJournal of Computer and System Sciences, 1970
- Parallel program schemataJournal of Computer and System Sciences, 1969