Канальная система (информатика)

«Система каналов» перенаправляется сюда. Чтобы узнать о морском дне Земли, см. канал Бездны .

В информатике канальная система — это конечный автомат, аналогичный взаимодействующему конечному автомату , в котором существует одна система, взаимодействующая сама с собой, а не множество систем, взаимодействующих друг с другом. Канальная система аналогична автомату с выталкиванием вниз , где вместо стека используется очередь. Эти очереди называются каналами . Интуитивно понятно, что каждый канал представляет собой последовательность сообщений, которые необходимо отправить и прочитать в том порядке, в котором они были отправлены.

Определение

Канальная система

Формально канальная система (или совершенная канальная система ) $S$ определяется как кортеж $\langle Q,C,\Sigma ,\Delta \rangle$ с:

• $Q=\{q_{1},\dots ,q_{m}\}$ конечное множество состояний управления ,
• $q_{0}\in Q$ состояние исходное ,
• $A$ конечный алфавит (для простоты обозначений пусть $\epsilon \in A$),
• $C=\{c_{1},\dots ,c_{n}\}$ конечное множество каналов ,
• $\Sigma =\{a_{1},\dots ,a_{p}\}$ конечный алфавит сообщений ,
• $\Delta \subseteq Q\times C\times \{?,!\}\times \Sigma ^{*}\times A\times Q$ конечное множество правил перехода с $\Sigma ^{*}$ being the set of finite (potentially empty) words over the alphabet $\Sigma$.

Depending on the author, a channel system may have no initial state and may have an empty alphabet.

Configuration

A configuration or global state of the channel system is a $n+1$ tuple belonging to $Q\times \prod _{i=1}^{n}(\Sigma ^{*})$. Intuitively, a configuration $\gamma =(q,w_{1},\dots ,w_{m})$ represents that a run is in state $q$ and that its $i$-th channel contains the word $w_{i}$.

The initial configuration is $(q_{0},\epsilon ,\dots ,\epsilon )$, with $\epsilon$ the empty word.

Step

Intuitively, a transition $(q,c_{i},!,u,a,q')$ means that the system may goes to control state $q$ to $q'$ by writing an $u$ to the end of the channel $c_{i}$. Similarly $(q,c_{i},?,u,a,q')$ means that the system may goes to control state $q$ to $q'$ by removing a $u$ starting the word $c_{i}$.

Formally, given a configuration $(q,w_{1},\dots ,w_{m})$, and a transition $(q,c_{i},!,u,q')$, there is a perfect step $(q,w_{1},\dots ,w_{i-1},w_{i},w_{i+1},\dots ,w_{m}){\xrightarrow {a}}_{\mathtt {perf}}(q',w_{1},\dots ,w_{i-1},w_{i}u,w_{i+1},\dots ,w_{m})$, where the step adds a letter $u$ to the end of the $i$-th word. Similarly, given a transition $(q,c_{i},?,u,q')$, there is a perfect step $(q,w_{1},\dots ,w_{i-1},uw_{i},w_{i+1},w_{m}){\xrightarrow {a}}_{\mathtt {perf}}(q',w_{1},\dots ,w_{i-1},w_{i},w_{i+1},\dots ,w_{m})$ where the first letter of the $i$-th word is $u$ and has been removed during the step.

Run

A perfect run is a sequence of perfect step, of the form $\gamma _{0}{\xrightarrow {a_{0}}}_{\mathtt {perf}}\gamma _{1}\dots$. We let $\gamma {\xrightarrow[{\mathtt {perf}}]{*}}\gamma '$ denote that there is a perfect run starting at $\gamma$ and ending at $\gamma '$.

Languages

Given a perfect or a lossy channel system $S$, multiple languages may be defined.

A word over $A^{*}$ is accepted by $S$ if it is the concatenation of the labels of a run of $S$. The language defined by $S$ is the set of words accepted by $S$.

The set of reachable configuration of $S$, denoted $R(S)$ is defined as the set of configuration $\gamma$ reachable from the initial state. I.e. as the set of configurations $\gamma '$ such that $(q_{0},\epsilon ,\dots ,\epsilon ){\xrightarrow {*}}\gamma '$.

Given a channel $c$, the channel of $c$ is the set of tuples $(w_{1},\dots w_{m})$ such that $(c,w_{1},\dots ,w_{m})\in R(S)$.

Channel system and Turing machine

Most problem related to perfect channel system are undecidable. 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 $M$, there exists a perfect channel system $S$ such that any run of $M$ of length $n$ can be simulated by a run of $S$ of length $O(n^{2})$. Intuitively, this simulation consists simply in having the entire tape of the simulated Turing machine in a channel. 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.

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 machines. We call such systems counter machines. This same definition applies for all variants of channel system.

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 $(q,w_{1},\dots ,a\cdot w_{i},\dots ,w_{m})\rightsquigarrow (q,w_{1},\dots ,w_{i},\dots ,w_{m})$.

Looseness

A lossy channel system or machine capable of lossiness 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, $(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})$.

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 $c$, a run is said to be channel fair with respect to $c$ if, assuming there are infinitely many steps in which a letter is sent to $c$ then there are infinitely many steps in which a letter is read from $c$.

A computation is said to be channel fair if it is channel fair with respect to each channel $c$.

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 $m$ and a channel $c$, a run is said to be impartial with respect to $c$ and $m$ if, assuming there are infinitely many steps in which $m$ is sent to $c$ then there are infinitely many steps in which $m$ is read from $c$.

A computation is said to be impartial with respect to a channel $c$ if it is impartial with respect to $c$ and a messages $m$. It is said to be impartial if it is impartial with respect to every channels $c$.

Справедливость сообщений

Свойство справедливости сообщения аналогично беспристрастности, но это условие должно выполняться только в том случае, если существует бесконечное число шагов, на которых $m$ можно прочитать. Формально прогон называется ярмаркой сообщений по отношению к $c$ и $m$ если, предполагая, что существует бесконечно много шагов, в которых $m$ отправляется в $c$, и бесконечно много шагов $i$ которое происходит в состоянии $q$ такой, что существует переход $(q,m,q')$, то существует бесконечно много шагов, за которые $m$ читается из $c$.

Ограниченность

Говорят, что прогон имеет ограниченные потери, если количество букв, удаленных между двумя совершенными шагами, ограничено.

Внесение ошибок

Машина , способная вносить ошибки, представляет собой расширение системы каналов, в которой буквы могут появляться где угодно.

Машина, способная вносить ошибку, допускает два типа шагов. Идеальные шаги, как определено выше, и шаги вставки. Обозначим шаг вставки через $(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})$.

Ошибки дублирования

Машина , способная дублировать ошибку, — это расширение машины, способной вставлять ошибку, в которой вставленная буква является копией предыдущей буквы.

Машина, способная вносить ошибку, допускает два типа шагов. Совершенные шаги, как определено выше, и шаги дублирования. Обозначим шаг вставки через $(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})$.

Недублирующаяся машина, допускающая ошибку дублирования, — это машина, которая гарантирует, что в каждом канале буквы чередуются между специальной новой буквой # и обычной буквой из алфавита сообщения. Если это не так, это означает, что произошло дублирование и запуск отклонен. Этот процесс позволяет закодировать любую систему каналов в машину, способную к ошибкам дублирования, при этом гарантируя, что в ней не будет ошибок. Поскольку канальные системы могут моделировать машины, отсюда следует, что машины, способные к ошибке дублирования, могут моделировать машину Тьюринга.

Характеристики

Набор достижимых конфигураций узнаваем для машин с каналами с потерями. и машины, способные вносить ошибки . Он рекурсивно перечислим для машины, способной к ошибке дублирования. .

Проблемы и их сложность

В этом разделе содержится список задач о канальной системе и их разрешимость по сложности для вариантов таких систем.

Проблема с завершением

Задача завершения состоит в том, чтобы при заданной канальной системе решить $S$ и первоначальная конфигурация $\gamma$ все ли пробеги $S$ начиная с $\gamma$ конечны. Эта проблема неразрешима для идеальных канальных систем, даже если система представляет собой встречную машину. или когда это одноканальная машина .

Эта проблема разрешима , но она не является примитивно-рекурсивной по системе каналов с потерями. Эта проблема тривиально разрешима на машине, способной вносить ошибки. .

Проблема с достижимостью

Задача достижимости состоит в решении по заданной канальной системе $S$ и две начальные конфигурации $\gamma$ и $\gamma '$ есть ли пробег $S$ от $\gamma$ к $\gamma '$. Эта проблема неразрешима в идеальных системах каналов и разрешима, но не примитивно-рекурсивно в системах каналов с потерями. Эта проблема разрешима на машине, способной вносить ошибки.

Проблема с достижимостью

Проблема тупика состоит в том, чтобы решить, существует ли достижимая конфигурация без преемника. Эта проблема разрешима в системе каналов с потерями. и тривиально разрешимо на машине, способной вносить ошибки . Это также разрешимо на встречной машине.

Проблема с проверкой модели

Задача проверки модели состоит в том, чтобы решить, является ли данная система $S$ и CTL* *-формула или LTL -формула $\phi$ или язык, определенный $S$ удовлетворяет $\phi$. Эта проблема неразрешима в системе каналов с потерями.

Повторяющаяся проблема состояния

Задача рекуррентного состояния состоит в решении по заданной канальной системе $S$ и первоначальная конфигурация $\gamma$ и государство $s$ существует ли пробег $S$, начиная с $\gamma$, бесконечно часто проходя через состояние $s$. Эта проблема неразрешима в системе каналов с потерями, даже при наличии одного канала.

Эквивалентный конечный автомат

Учитывая систему $S$, не существует алгоритма, который вычисляет конечный автомат, представляющий $R(S)$ для класса системы каналов с потерями. Эта проблема разрешима на машине, способной вносить ошибки.

Проблема ограниченности

Проблема ограниченности состоит в том, чтобы решить, конечно ли множество достижимых конфигураций. Т.е. длина контента каждого канала ограничена. Эта проблема тривиально разрешима на машине, способной вносить ошибки. . Это также разрешимо на встречной машине.

В конечном итоге свойства

Свойство эвентуальности , или свойство неизбежности, состоит в том, чтобы принять решение по заданной канальной системе $S$ и набор $\Gamma$ конфигураций, все ли запущены $S$ начиная с $\gamma$ проходит настройку $\Gamma$. Эта проблема неразрешима для беспристрастной системы каналов с потерями. и с двумя другими ограничениями справедливости.

Свойство безопасности

Задача о безопасности состоит в решении по заданной канальной системе $S$ и обычный набор $R$ ли

Структурное завершение

Задача структурного завершения заключается в решении по заданной системе каналов $S$ если проблема завершения сохраняется в течение $S$ для каждой начальной конфигурации. Эта проблема неразрешима даже на безрецептурной машине.

Коммуникационный иерархический конечный автомат

Иерархические автоматы — это конечные автоматы, состояния которых сами могут быть другими автоматами. Поскольку взаимодействующий конечный автомат характеризуется параллелизмом, наиболее примечательной чертой взаимодействующего иерархического конечного автомата является сосуществование иерархии и параллелизма. Это было сочтено очень подходящим, поскольку означает более сильное взаимодействие внутри машины.

Однако было доказано, что сосуществование иерархии и параллелизма по своей сути обходится включением языка, языковой эквивалентностью и всей универсальностью.