Cтраница 1
О-сеть называется К-плотной, если в ней любое li - сечение и любое со-сечение пересекаются ровно по одному элементу. С учетом теоремы 7.1 это означает, что / ( - плотная сеть не содержит ни одной пары непересекающихся li - сечений и со-сечений. Легко убедиться непосредственно, что сеть на рис. 7.2 / ( - плотна. [1]
Пример О-сети на рис. 7.3 хорошо иллюстрирует, в чем состоит несоответствие между синтаксисом и семантикой в не - / ( - плотной сети. В соответствии со структурой сети в ней существуют указанные бесконечные со-сечения. [2]
Теорема 7.2. Любая конечная О-сеть К-плотна. [3]
В общем случае О-сети могут быть бесконечными, а среди бесконечных сетей могут быть сети, не имеющие хвостовых мест. Легко видеть из определения О-сети, что в случае, если сеть конечна, она представляет собой частный случай сети Петри, а с учетом структурных ограничений, она является некоторым вариантом ациклического синхронизационного графа. В отличие от последнего, где требуется, чтобы VpS / 3: Р р 1, в О-сети каждое место инцидентно не более чем одной входной и выходной дуге. [4]
Еще один пример О-сети, которая не является АГ-плотной, показан на рис. 7 4, а. В этой сети результат несоответствия топологического сетевого параллелизма отношению параллелизма в процессах приводит к тому, что переходу f не соответствует никакого действия. Действительно, поскольку li - сечение ( р, ti p3, f2 Ps / fa не пересекается с со-сече-нием р2, P. [5]
Теорема 7.3. В К-плотной О-сети, каждый переход которой имеет конечное множество входов, любой переход срабатывает ровно один раз. [6]
Лемма 7.2. Любая S-сеть и любая О-сеть являются правильными. [7]
Теорема 7.10. Результатом развертки параллельной сети является О-сеть. [8]
Так же, как и в случае О-сети, возникает проблема неадекватных S-сетей, которые, если их интерпретировать как последовательно-альтернативные процессы, оказываются неприемлемыми как реальные процессы. Среди О-сетей выделялись - плотные О-сети, для которых синтаксические ( сетевые) и семантические представления соответствовали друг другу. С учетом теоремы 7.4 это означает, что L - плотная сеть не содержит ни одной пары непересекающихся li - сечений и al - сечений. По определению последовательно-альтернативного процесса в каждой полной альтернативе должно реализоваться ровно одно действие. Таким образом, указанные топологические альтернативы могут в действительности не иметь места. [9]
Точно так же, как и в случае О-сетей, S-сети являются некоторой синтаксической формой представления процессов, а именно - последовательно-альтернативных процессов. Отношение следования II выражается через отношение F в S-сетях так же, как и в случае О-сетей. [10]
Определения li - сечений, со-сечений, данные выше для О-сетей и S-сетей, переносятся на случай Л - сетей. Al-сечение в XI-сети определяется несколько иначе. [11]
Сети, предназначенные для описания параллельных процессов с конкуренцией, строятся на основе О-сетей с добавлением в них специальных мест, называемых ресурсами, и дуг, связывающих эти места с переходами особым способом. [12]
Опускаем доказательство этой теоремы, поскольку оно весьма похоже на доказательство теоремы 7.2 о / ( - плотности конечных О-сетей. [13]
Для S-сетей можно определить понятие li - сечения, и это определение полностью совпадает с определением li - сечения для О-сетей. Множество А элементов S-сети назовем альтернативным разрезом, если Vx, у А: х al у, т.е. любые два элемента из А альтернативны. В графическом представлении S-сети все элементы, образующие альтернативный разрез, попарно не соединены никаким путем. В множестве всех разрезов S-сети выделим максимальные, т.е. такие, которые не содержатся ни в каких других, и будем называть их э - сечениями. [14]
Так же, как и в случае О-сети, возникает проблема неадекватных S-сетей, которые, если их интерпретировать как последовательно-альтернативные процессы, оказываются неприемлемыми как реальные процессы. Среди О-сетей выделялись - плотные О-сети, для которых синтаксические ( сетевые) и семантические представления соответствовали друг другу. С учетом теоремы 7.4 это означает, что L - плотная сеть не содержит ни одной пары непересекающихся li - сечений и al - сечений. По определению последовательно-альтернативного процесса в каждой полной альтернативе должно реализоваться ровно одно действие. Таким образом, указанные топологические альтернативы могут в действительности не иметь места. [15]