In computer science, a channel system is a finite state machine similar to communicating finite-state machine in which there is a single system communicating with itself instead of many systems communicating with each other. A channel system is similar to a pushdown automaton where a queue is used instead of a stack. Those queues are called channels. Intuitively, each channel represents a sequence a message to be sent, and to be read in the order in which they are sent.
Communicating Hierarchical State Machine
Hierarchical state machines are finite state machines whose states themselves can be other machines. 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.
However, it was proved that the coexistence of hierarchy and concurrency intrinsically costs language inclusion, language equivalence, and all of universality.
- ^ Jump up to:ab Abdulla, Parosh Aziz; Jonsson, Bengt (1996). “Verifying Programs with Unreliable Channels”. Information and Computation. 127 (2): 91–101. doi:10.1006/inco.1996.0053.
- ^ Jump up to:ab c d Schnoebelen, Ph (15 September 2002). “Verifying Lossy Channel Systems has Nonprimitive Recursive Complexity”. Information Processing Letters. 83 (5): 251–261. doi:10.1016/S0020-0190(01)00337-4.
- ^ Jump up to:ab c d e f g h i j k l m n o Cécé, Gérard; Finkel, Alain (10 January 1996). “Unreliable Channels Are Easier to Verify Than Perfect Channels”. Information and Computation. 124 (1): 20–31. doi:10.1006/inco.1996.0003.
- ^ Jump up to:ab c d Mayr, Richard (17 March 2008). “Undecidable problems in unreliable computations”. Theoretical Computer Science. 297 (1–3): 337–354. doi:10.1016/S0304-3975(02)00646-1.
- ^ Jump up to:ab c d e f g Abdulla, Parosh Aziz; Jonsson, Bengt (10 October 1996). “Undecidable Verification Problems for Programs with Unreliable Channels”. Information and Computation. 130 (1): 71–90. doi:10.1006/inco.1996.0083.
- ^ Jump up to:ab Rosier, Louis E.; Gouda, Mohamed G (1983). Deciding progress for a class of communicating finite state machines (Report).
- ^Alur, Rajeev; Kannan, Sampath; Yannakakis, Mihalis. “Communicating hierarchical state machines,” Automata, Languages and Programming. Prague: ICALP, 1999