【Move to another page】
Quote
https://ift.tt/2I3JbSt
Channel system (computer science)
Arthur MILCHIOR: ←Created page with 'In computer science, a '''channel system''' is a finite state machine similar to communicating finite-state machine in which there is a single system...'
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 ==
=== Channel system ===
Formally, a '''channel system''' (or '''perfect channel system''') <math>S</math> is defined as a tuple <math>\langle Q,C,\Sigma,\Delta</math> with:
* <math>Q=\{q_1,\dots,q_m\}</math> a finite set of '''control states''',
* <math>q_0\in Q</math> an '''initial state''',
* <math>A</math> a finite alphabet,
* <math>C=\{c_1,\dots,c_n\}</math> a finite set of '''channels''',
* <math>\Sigma=\{a_1,\dots,a_p\}</math> a finite alphabet of '''messages''',
* <math>\Delta\subseteq Q\times C\times\{?,!\}\times\Sigma^*\times (A\cup\{\epsilon\})\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"></ref>
Depending of the author, a '''channel system''' may have no initial state and may have an empty alphabet.<ref name="Nonprimitive recursive">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Configuration ===
A '''configuration''' or '''global state''' of the channel system is a <math>n+1</math> tuple belonging to <math>Q\times\prod_{i=1}^n(\Sigma^*)</math>. Intuitively, a configuration <math>\gamma=(q,w_1,\dots,w_m)</math> represents that a run is in state <math>q</math> and that its <math>i</math>-th channel contains the word <math>w_i</math>.
The initial configuration is <math>(q_0,\epsilon,\dots,\epsilon)</math>, with <math>\epsilon</math> the empty word.
=== Step ===
Intuitively, a transition <math>(q,c_i,!,u,a,q')</math> means that the system may goes to control state <math>q</math> to <math>q'</math> by writting an <math>u</math> to the end of the channel <math>c_i</math>. Similarly <math>(q,c_i,?,u,a,q')</math> means that the system may goes to control state <math>q</math> to <math>q'</math> by removing a <math>u</math> starting the word <math>c_i</math>.
Formally, given a configuration <math>(q,w_1,\dots,w_m)</math>, and a transition <math>(q,c_i,!,u,q')</math>, there is a perfect step <math>(q,w_1,\dots,w_m)\xrightarrow{a}_{\mathtt{perf}}(q',w_1,\dots,w_{i-1},w_iu,w_{i+1},\dots,w_m)</math>. Given a transition <math>(q,c_i,!,u,q')</math>, if <math>w_i=uw'_i</math>, there is a perfect step <math>(q,w_1,\dots,w_m)\xrightarrow{a}_{\mathtt{perf}}(q',w_1,\dots,w_{i-1},w_i',w_{i+1},\dots,w_m)</math>.
=== Run ===
A '''perfect run''' is a sequence of perfect step, of the form <math>\gamma_0\xrightarrow{a_0}_{\mathtt{perf}}\gamma_1\dots</math>. We let <math>\gamma\xrightarrow[\mathtt{perf}]{*}\gamma'</math> denote that there is a perfect run starting at <math>\gamma</math> and ending at <math>\gamma'</math>.
=== Languages ===
Given a perfect or a lossy channel system <math>S</math>, multiple languages may be defined.
A word over <math>A^*</math> is accepted by <math>S</math> if it is is the concatenation of the labels of a run of <math>S</math>. The language defined by <math>S</math> is the set of words accepted by <math>S</math>.
The set of reachable configuration of <math>S</math>, denoted <math>R(S)</math> is defined as the set of configuration <math>\gamma</math> reachable from the initial state. I.e. as the set of configurations <math>\gamma'</math> such that <math>(q_0,\epsilon,\dots,\epsilon)\xrightarrow{*}\gamma'</math>.
Given a channel <math>c</math>, the channel of <math>c</math> is the set of tuples <math>(w_1,\dots w_m)</math> such that <math>(c,w_1,\dots,w_m)\in R(S)</math>.
== Channel system and Turing machine ==
Most problem related to perfect channel system are undecidable<ref name="easier">Liquid error: wrong number of arguments (1 for 2)</ref>. This is due to the fact that such a machine may simulates the run of a [[Turing machine]]. This simulation is now sketched.
Given a [[Turing machine]] <math>M</math>, there exists a perfect channel system <math>S</math> such that any run of <math>M</math> of length <math>n</math> can be simulated by a run of <math>S</math> of length <math>O(n^2)</math>. Intuitively, this simulation consists simply in having the entire tape in a channel. The channel is then entirely read, and a step is simulated while it is read.
== Variants ==
Multiple variants of channel systems have been introduced. The two variants introduced below does not allow to simulate a Turing machine and thus allows multiple problem of interest to be decidable.
=== One channel machine ===
A one-channel machine is a channel system using a single channel. The same definition also applies for all variants of channel system.
=== Counter machine ===
When the alphabet of a channel system contains a single message, then each channel is essentially a counter. It follows that those systems are essentially [[Minsky machine]]s. We call such systems '''counter machines'''. This same definition applies for all variants of channel system.<ref name="Counter">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Completely specified protocol ===
A '''completely specified protocol'''(CSP) is defined exactly as a channel system. However, the notion of step and of run are defined differently.
A CSP admits two kinds of steps. Perfect steps, as defined above, and a '''message loss transition''' step. We denote a message loss transition step by <math>(q,w_1,\dots,a\cdot w_i,\dots,w_m)\rightsquigarrow(q,w_1,\dots,w_i,\dots,w_m)</math>.
=== Looseness ===
A '''lossy channel system''' or '''machine capable of lossinness error'' is an extension of completely specified protocol in which letters may disappear anywhere.
A lossy channel system admits two kinds of steps. Perfect steps, as defined above, and lossy step. We denote a lossy step, <math>(q,w_1,\dots,w_i\cdot a\cdot w'_i\dots,,w_m)\rightsquigarrow(q,w_1,\dots,w_i\cdot w'_i,w'_m)</math>.
It should be noted that a run in which channel are emptied as soon as messages are sent into them is a valid run according to this definition. For this reason, some fairness conditions may be introduced to those systems.
==== Channel fairness ====
Given a message a channel <math>c</math>, a run is said to be channel fair with respect to <math>c</math> if, assuming there are infinitely many steps in which a letter is sent to <math>c</math> then there are infinitely many steps in which a letter is read from <math>c</math>.
A computation is said to be channel fair if it is channel fair with respect to each channel <math>c</math>.
===== Impartiality =====
The impartiality condition is a restriction to the channel fairness condition in which both the channel and the letter are considered.
Given a message <math>m</math> and a channel <math>c</math>, a run is said to be impartial with respect to <math>c</math> and <math>m</math> if, assuming there are infinitely many steps in which <math>m</math> is sent to <math>c</math> then there are infinitely many steps in which <math>m</math> is read from <math>c</math>.
A computation is said to be impartial with respect to a channel <math>c</math> if it is impartial with respect to <math>c</math> and a messages <math>m</math>. It is said to be '''impartial''' if it is impartial with respect to every channels <math>c</math>.
===== Message fairness =====
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 <math>m</math> may be read. Formally, a run is said to be message faire with respect to <math>c</math> and <math>m</math> if, assuming there are infinitely many steps in which <math>m</math> is sent to <math>c</math>, and infinitely many step <math>i</math> which occurs in a state <math>q</math> such that there exists a transition <math>(q,m,q')</math>, then there are infinitely many steps in which <math>m</math> is read from <math>c</math>.
===== Boundedness =====
The run is said to have bounded lossiness if the number of letter removed between two perfect steps is bounded.
=== Insertion of errors ===
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. Perfect steps, as defined above, and insertion steps. We denote an insertion step by <math>(q,w_1,\dots,w_i\cdot w'_i\dots,,w_m)\rightsquigarrow(q,w_1,\dots,w_i\cdot a\cdot w'_i,w'_m)</math>.
=== Duplication errors ===
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. Perfect steps, as defined above, and duplication steps. We denote an insertion step by <math>(q,w_1,\dots,w_i\cdot a\cdot w'_i\dots,,w_m)\rightsquigarrow(q,w_1,\dots,w_i\cdot a\cdot a\cdot w'_i,w'_m)</math>.
A '''non-duplicate machine''' capable of duplication error is a machine which ensures that in each channel, the letters alternate between a special new letter #, and a regular letter from the alphabet of message. If it is not the caes, it means a duplication occured and the run rejects. This process allow to encode any channel system into a machine capable of duplication error, while forcing it not to have errors. Since channel systems can simulate machines, it follows that machines capable of duplication error can simulate Turing machine.
== Properties ==
The set of rechable configurations is recognizable for lossy channel machines and machines capable of insertions of errors. It is recursively enumerable for machine capable of duplication error.
== Problems and their complexity ==
This section contain a list of problems over channel system, and their decidability of complexity over variants of such systems.
=== Termination problem ===
The '''termination problem''' consists in deciding, given a channel system <math>S</math> and an initial configuration <math>\gamma</math> whether all runs of <math>S</math> starting at <math>\gamma</math> are finite. This problem is undecidable over perfect channel systems, even when the system is a counter machine or when it is a one-channel machine.
This problem is [[decidable language|decidable]] but non[[primitive recursive]] over lossy channel system. This problem is trivially decidable over machine capable of insertion of errors.
=== Reachability problem ===
The '''reachability''' problem consists in deciding, given a channel system <math>S</math> and two initial configurations <math>\gamma</math> and <math>\gamma'</math> whether there is a run of <math>S</math> from <math>\gamma</math> to <math>\gamma'</math>. This problem is undecidable over perfect channel systems and [[decidable language|decidable]] but non[[primitive recursive]] over lossy channel system. This problem is decidable over machine capable of insertion of errors .
=== Reachability problem ===
The '''deadlock problem''' consists in deciding whether there is a reachable configuration without successor. This problem is decidable over lossy channel system and trivially decidable over machine capable of insertion of errors. It is also decidable over counter machine.<ref name="Rosier, Gouda">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Model checking problem ===
The '''model checking problem''' consists in deciding whether given a system <math>S</math> and a [[CTL*]]*-formula or a [[LTL]]-formula <math>\phi</math> or a whether the language defined by <math>S</math> satisfies <math>\phi</math>. This problem is undecidable over lossy channel system.<ref name="Undecidable over unreliable channels">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Recurrent state problem ===
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.
=== 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. This problem is decidable over machine capable of insertion of error .
=== Boundedness problem ===
The '''boundedness problem''' consists in deciding whether the set of reachable configuration is finite. I.e. the length of the content of each channel is bounded. This problem is trivially decidable over machine capable of insertion of errors. It is also decidable over counter machine.
=== Eventually properties ===
The '''eventuality property''', or '''inevitability property''' problem consists in deciding, given a channel system <math>S</math> and a set <math>\Gamma</math> of configurations whether all run of <math>S</math> starting at <math>\gamma</math> goes through a configuration of <math>\Gamma</math>. This problem is undecidable for lossy channel system with impartiality and with the two other fairness constraints.
=== Safety property ===
The '''safety property''' problem consists in deciding, given a channel system <math>S</math> and a regular set <math>R</math> whether
=== Structural termination ===
The '''structural termiantion''' problem consists in deciding, given a channel system <math>S</math> if the termination problem holds for <math>S</math> for every initial configuration. This problem is undecidable even over counter machine.
==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>
== References ==
<references />
[[Category:Concurrency (computer science)]]
[[Category:Models of computation]]
== Definition ==
=== Channel system ===
Formally, a '''channel system''' (or '''perfect channel system''') <math>S</math> is defined as a tuple <math>\langle Q,C,\Sigma,\Delta</math> with:
* <math>Q=\{q_1,\dots,q_m\}</math> a finite set of '''control states''',
* <math>q_0\in Q</math> an '''initial state''',
* <math>A</math> a finite alphabet,
* <math>C=\{c_1,\dots,c_n\}</math> a finite set of '''channels''',
* <math>\Sigma=\{a_1,\dots,a_p\}</math> a finite alphabet of '''messages''',
* <math>\Delta\subseteq Q\times C\times\{?,!\}\times\Sigma^*\times (A\cup\{\epsilon\})\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"></ref>
Depending of the author, a '''channel system''' may have no initial state and may have an empty alphabet.<ref name="Nonprimitive recursive">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Configuration ===
A '''configuration''' or '''global state''' of the channel system is a <math>n+1</math> tuple belonging to <math>Q\times\prod_{i=1}^n(\Sigma^*)</math>. Intuitively, a configuration <math>\gamma=(q,w_1,\dots,w_m)</math> represents that a run is in state <math>q</math> and that its <math>i</math>-th channel contains the word <math>w_i</math>.
The initial configuration is <math>(q_0,\epsilon,\dots,\epsilon)</math>, with <math>\epsilon</math> the empty word.
=== Step ===
Intuitively, a transition <math>(q,c_i,!,u,a,q')</math> means that the system may goes to control state <math>q</math> to <math>q'</math> by writting an <math>u</math> to the end of the channel <math>c_i</math>. Similarly <math>(q,c_i,?,u,a,q')</math> means that the system may goes to control state <math>q</math> to <math>q'</math> by removing a <math>u</math> starting the word <math>c_i</math>.
Formally, given a configuration <math>(q,w_1,\dots,w_m)</math>, and a transition <math>(q,c_i,!,u,q')</math>, there is a perfect step <math>(q,w_1,\dots,w_m)\xrightarrow{a}_{\mathtt{perf}}(q',w_1,\dots,w_{i-1},w_iu,w_{i+1},\dots,w_m)</math>. Given a transition <math>(q,c_i,!,u,q')</math>, if <math>w_i=uw'_i</math>, there is a perfect step <math>(q,w_1,\dots,w_m)\xrightarrow{a}_{\mathtt{perf}}(q',w_1,\dots,w_{i-1},w_i',w_{i+1},\dots,w_m)</math>.
=== Run ===
A '''perfect run''' is a sequence of perfect step, of the form <math>\gamma_0\xrightarrow{a_0}_{\mathtt{perf}}\gamma_1\dots</math>. We let <math>\gamma\xrightarrow[\mathtt{perf}]{*}\gamma'</math> denote that there is a perfect run starting at <math>\gamma</math> and ending at <math>\gamma'</math>.
=== Languages ===
Given a perfect or a lossy channel system <math>S</math>, multiple languages may be defined.
A word over <math>A^*</math> is accepted by <math>S</math> if it is is the concatenation of the labels of a run of <math>S</math>. The language defined by <math>S</math> is the set of words accepted by <math>S</math>.
The set of reachable configuration of <math>S</math>, denoted <math>R(S)</math> is defined as the set of configuration <math>\gamma</math> reachable from the initial state. I.e. as the set of configurations <math>\gamma'</math> such that <math>(q_0,\epsilon,\dots,\epsilon)\xrightarrow{*}\gamma'</math>.
Given a channel <math>c</math>, the channel of <math>c</math> is the set of tuples <math>(w_1,\dots w_m)</math> such that <math>(c,w_1,\dots,w_m)\in R(S)</math>.
== Channel system and Turing machine ==
Most problem related to perfect channel system are undecidable<ref name="easier">Liquid error: wrong number of arguments (1 for 2)</ref>. This is due to the fact that such a machine may simulates the run of a [[Turing machine]]. This simulation is now sketched.
Given a [[Turing machine]] <math>M</math>, there exists a perfect channel system <math>S</math> such that any run of <math>M</math> of length <math>n</math> can be simulated by a run of <math>S</math> of length <math>O(n^2)</math>. Intuitively, this simulation consists simply in having the entire tape in a channel. The channel is then entirely read, and a step is simulated while it is read.
== Variants ==
Multiple variants of channel systems have been introduced. The two variants introduced below does not allow to simulate a Turing machine and thus allows multiple problem of interest to be decidable.
=== One channel machine ===
A one-channel machine is a channel system using a single channel. The same definition also applies for all variants of channel system.
=== Counter machine ===
When the alphabet of a channel system contains a single message, then each channel is essentially a counter. It follows that those systems are essentially [[Minsky machine]]s. We call such systems '''counter machines'''. This same definition applies for all variants of channel system.<ref name="Counter">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Completely specified protocol ===
A '''completely specified protocol'''(CSP) is defined exactly as a channel system. However, the notion of step and of run are defined differently.
A CSP admits two kinds of steps. Perfect steps, as defined above, and a '''message loss transition''' step. We denote a message loss transition step by <math>(q,w_1,\dots,a\cdot w_i,\dots,w_m)\rightsquigarrow(q,w_1,\dots,w_i,\dots,w_m)</math>.
=== Looseness ===
A '''lossy channel system''' or '''machine capable of lossinness error'' is an extension of completely specified protocol in which letters may disappear anywhere.
A lossy channel system admits two kinds of steps. Perfect steps, as defined above, and lossy step. We denote a lossy step, <math>(q,w_1,\dots,w_i\cdot a\cdot w'_i\dots,,w_m)\rightsquigarrow(q,w_1,\dots,w_i\cdot w'_i,w'_m)</math>.
It should be noted that a run in which channel are emptied as soon as messages are sent into them is a valid run according to this definition. For this reason, some fairness conditions may be introduced to those systems.
==== Channel fairness ====
Given a message a channel <math>c</math>, a run is said to be channel fair with respect to <math>c</math> if, assuming there are infinitely many steps in which a letter is sent to <math>c</math> then there are infinitely many steps in which a letter is read from <math>c</math>.
A computation is said to be channel fair if it is channel fair with respect to each channel <math>c</math>.
===== Impartiality =====
The impartiality condition is a restriction to the channel fairness condition in which both the channel and the letter are considered.
Given a message <math>m</math> and a channel <math>c</math>, a run is said to be impartial with respect to <math>c</math> and <math>m</math> if, assuming there are infinitely many steps in which <math>m</math> is sent to <math>c</math> then there are infinitely many steps in which <math>m</math> is read from <math>c</math>.
A computation is said to be impartial with respect to a channel <math>c</math> if it is impartial with respect to <math>c</math> and a messages <math>m</math>. It is said to be '''impartial''' if it is impartial with respect to every channels <math>c</math>.
===== Message fairness =====
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 <math>m</math> may be read. Formally, a run is said to be message faire with respect to <math>c</math> and <math>m</math> if, assuming there are infinitely many steps in which <math>m</math> is sent to <math>c</math>, and infinitely many step <math>i</math> which occurs in a state <math>q</math> such that there exists a transition <math>(q,m,q')</math>, then there are infinitely many steps in which <math>m</math> is read from <math>c</math>.
===== Boundedness =====
The run is said to have bounded lossiness if the number of letter removed between two perfect steps is bounded.
=== Insertion of errors ===
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. Perfect steps, as defined above, and insertion steps. We denote an insertion step by <math>(q,w_1,\dots,w_i\cdot w'_i\dots,,w_m)\rightsquigarrow(q,w_1,\dots,w_i\cdot a\cdot w'_i,w'_m)</math>.
=== Duplication errors ===
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. Perfect steps, as defined above, and duplication steps. We denote an insertion step by <math>(q,w_1,\dots,w_i\cdot a\cdot w'_i\dots,,w_m)\rightsquigarrow(q,w_1,\dots,w_i\cdot a\cdot a\cdot w'_i,w'_m)</math>.
A '''non-duplicate machine''' capable of duplication error is a machine which ensures that in each channel, the letters alternate between a special new letter #, and a regular letter from the alphabet of message. If it is not the caes, it means a duplication occured and the run rejects. This process allow to encode any channel system into a machine capable of duplication error, while forcing it not to have errors. Since channel systems can simulate machines, it follows that machines capable of duplication error can simulate Turing machine.
== Properties ==
The set of rechable configurations is recognizable for lossy channel machines and machines capable of insertions of errors. It is recursively enumerable for machine capable of duplication error.
== Problems and their complexity ==
This section contain a list of problems over channel system, and their decidability of complexity over variants of such systems.
=== Termination problem ===
The '''termination problem''' consists in deciding, given a channel system <math>S</math> and an initial configuration <math>\gamma</math> whether all runs of <math>S</math> starting at <math>\gamma</math> are finite. This problem is undecidable over perfect channel systems, even when the system is a counter machine or when it is a one-channel machine.
This problem is [[decidable language|decidable]] but non[[primitive recursive]] over lossy channel system. This problem is trivially decidable over machine capable of insertion of errors.
=== Reachability problem ===
The '''reachability''' problem consists in deciding, given a channel system <math>S</math> and two initial configurations <math>\gamma</math> and <math>\gamma'</math> whether there is a run of <math>S</math> from <math>\gamma</math> to <math>\gamma'</math>. This problem is undecidable over perfect channel systems and [[decidable language|decidable]] but non[[primitive recursive]] over lossy channel system. This problem is decidable over machine capable of insertion of errors .
=== Reachability problem ===
The '''deadlock problem''' consists in deciding whether there is a reachable configuration without successor. This problem is decidable over lossy channel system and trivially decidable over machine capable of insertion of errors. It is also decidable over counter machine.<ref name="Rosier, Gouda">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Model checking problem ===
The '''model checking problem''' consists in deciding whether given a system <math>S</math> and a [[CTL*]]*-formula or a [[LTL]]-formula <math>\phi</math> or a whether the language defined by <math>S</math> satisfies <math>\phi</math>. This problem is undecidable over lossy channel system.<ref name="Undecidable over unreliable channels">Liquid error: wrong number of arguments (1 for 2)</ref>
=== Recurrent state problem ===
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.
=== 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. This problem is decidable over machine capable of insertion of error .
=== Boundedness problem ===
The '''boundedness problem''' consists in deciding whether the set of reachable configuration is finite. I.e. the length of the content of each channel is bounded. This problem is trivially decidable over machine capable of insertion of errors. It is also decidable over counter machine.
=== Eventually properties ===
The '''eventuality property''', or '''inevitability property''' problem consists in deciding, given a channel system <math>S</math> and a set <math>\Gamma</math> of configurations whether all run of <math>S</math> starting at <math>\gamma</math> goes through a configuration of <math>\Gamma</math>. This problem is undecidable for lossy channel system with impartiality and with the two other fairness constraints.
=== Safety property ===
The '''safety property''' problem consists in deciding, given a channel system <math>S</math> and a regular set <math>R</math> whether
=== Structural termination ===
The '''structural termiantion''' problem consists in deciding, given a channel system <math>S</math> if the termination problem holds for <math>S</math> for every initial configuration. This problem is undecidable even over counter machine.
==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>
== References ==
<references />
[[Category:Concurrency (computer science)]]
[[Category:Models of computation]]
April 02, 2019 at 04:36AM
