Channel system (computer science): Difference between revisions

Revision as of 05:36, 27 September 2021

Latest revision as of 02:46, 26 December 2024

(One intermediate revision by one other user not shown)

Line 1:

{{redirect|Channel system|Earth's sea floor|Abyssal channel}}

{{short description|Finite-state machine with fifo buffers for memory}}

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.

== Definition ==

Line 13 ⟶ 14:

* <math>\Delta\subseteq Q\times C\times\{?,!\}\times\Sigma^*\times A \times Q</math> a finite set of transition rules with <math>\Sigma^*</math> being the set of finite (potentially empty) words over the alphabet <math>\Sigma</math>.<ref name="decidable">{{cite journal |last1=Abdulla |first1=Parosh Aziz |last2=Jonsson|first2=Bengt|title=Verifying Programs with Unreliable Channels|journal =Information and Computation |year=1996 |volume=127 |issue=2 |pages=91–101 |doi=10.1006/inco.1996.0053|doi-access=free }}</ref>

Depending ofon the author, a '''channel system''' may have no initial state and may have an empty alphabet.<ref name="Nonprimitive recursive">{{cite journal |last1=Schnoebelen |first1=Ph |title=Verifying Lossy Channel Systems has Nonprimitive Recursive Complexity |journal =Information Processing Letters |date=15 September 2002 |volume=83 |issue=5 |pages=251–261 |doi=10.1016/S0020-0190(01)00337-4}}</ref>

=== Configuration ===

Line 117 ⟶ 118:

The '''recurrent state problem''' consists in deciding, given a channel system <math>S</math> and an initial configuration <math>\gamma</math> and a state <math>s</math> whether there exists a run of <math>S</math>, starting at <math>\gamma</math>, going infinitely often through state <math>s</math>. This problem is undecidable over lossy channel system, even with a single channel.{{r|easier|p=23}}{{r|Undecidable over unreliable channels|p=80}}

=== Equivalent finite -state machine ===

Given a system <math>S</math>, there is no algorithm which computes a [[finite -state machine]] representing <math>R(S)</math> for the class of lossy channel system.{{r|easier|p=24}} This problem is decidable over machine capable of insertion of error .{{r|easier|p=26}}

=== Boundedness problem ===

Line 134 ⟶ 135:

==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.<ref>Alur, Rajeev; Kannan, Sampath; Yannakakis, Mihalis. "Communicating hierarchical state machines," Automata, Languages and Programming. Prague: ICALP, 1999</ref>