Boundedness, empty channel detection, and synchronization for communicating finite automata
From MaRDI portal
Publication:1819939
DOI10.1016/0304-3975(86)90110-6zbMath0614.68049OpenAlexW2017140475MaRDI QIDQ1819939
Publication date: 1986
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(86)90110-6
decision procedurevector addition systemscommunicating finite state machinesdecidability of the boundedness problemFIFO queuesrestricted 3-counter machine
Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)
Related Items (8)
Eliminating the storage tape in reachability constructions. ⋮ The complexity of reachability in distributed communicating processes ⋮ A methodology for constructing communication protocols with multiple concurrent functions ⋮ Reduction and covering of infinite reachability trees ⋮ Testing for unboundedness of fifo channels ⋮ Communicating processes, scheduling, and the complexity of nontermination ⋮ Boundedness, hierarchy of fairness, and communication networks with delay ⋮ Undecidable verification problems for programs with unreliable channels
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unboundedness detection for a class of communicating finite-state machines
- Exposure to deadlock for communicating processes is hard to detect
- On the reachability problem for 5-dimensional vector addition systems
- On tape-bounded complexity classes and multihead finite automata
- Deterministic one-counter automata
- The covering and boundedness problems for vector addition systems
- Relationships between nondeterministic and deterministic tape complexities
- Parallel program schemata
- On Communicating Finite-State Machines
- Priority Networks of Communicating Finite State Machines
- New problems complete for nondeterministic log space
- Time, clocks, and the ordering of events in a distributed system
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
This page was built for publication: Boundedness, empty channel detection, and synchronization for communicating finite automata
