A channel system is similar to a pushdown automaton where a queue is used instead of a stack.
Intuitively, each channel represents a sequence a message to be sent, and to be read in the order in which they are sent.
with: Depending on the author, a channel system may have no initial state and may have an empty alphabet.
Most problem related to perfect channel system are undecidable[1]: 92 .
The content channel is then entirely read and immediately rewritten in the channel, with one exception, the part of the content representing the head of the Turing machine is changed, to simulate a step of the Turing machine computation.
The two variants introduced below does not allow to simulate a Turing machine and thus allows multiple problem of interest to be decidable.
[4]: 337 A completely specified protocol (CSP) is defined exactly as a channel system.
A lossy channel system admits two kinds of steps.
The message fairness property is similar to impartiality, but the condition only have to hold if there is an infinite number of step at which
[4]: 339 A machine capable of insertion of error is an extension of channel system in which letters may appear anywhere.
A machine capable of insertion of error admits two kinds of steps.
[3]: 25 A machine capable of duplication error is an extension of machine capable of insertion of error in which the inserted letter is a copy of the previous letter.
A machine capable of insertion of error admits two kinds of steps.
It is recursively enumerable for machine capable of duplication error[3]: 27 .
The termination problem consists in deciding, given a channel system
This problem is decidable but nonprimitive recursive over lossy channel system.
[2]: 10 This problem is trivially decidable over machine capable of insertion of errors[3]: 26 .
The reachability problem consists in deciding, given a channel system
[2]: 10 This problem is decidable over machine capable of insertion of errors .
[3]: 26 The deadlock problem consists in deciding whether there is a reachable configuration without successor.
[6] The model checking problem consists in deciding whether given a system
[3]: 23 [5] The recurrent state problem consists in deciding, given a channel system
[3]: 24 This problem is decidable over machine capable of insertion of error .
[3]: 26 The boundedness problem consists in deciding whether the set of reachable configuration is finite.
This problem is trivially decidable over machine capable of insertion of errors[3]: 26 .
This problem is undecidable for lossy channel system with impartiality[5]: 84 and with the two other fairness constraints.
[5]: 87 The safety property problem consists in deciding, given a channel system
whether The structural termination problem consists in deciding, given a channel system
Since a communicating finite-state machine is characterized by concurrency, the most notable trait in a communicating hierarchical state machine is the coexistence of hierarchy and concurrency.
This had been considered highly suitable as it signifies stronger interaction inside the machine.