Маркированная графа

Cтраница 1

Соотношение между сетями Петри, мар кированны. [1]

Маркированные графы были рассмотрены в разд. Как подкласс сетей Петри маркированные графы, очевидно, обладают более ограниченной мощностью моделирования. Маркированные графы непосредственно не сопоставимы с конечными автоматами, но, по-видимому, являются двойственными к ним. Таким образом, мы получаем изображенное на рис. 8.1 соотношение между сетями Петри, конечными автоматами и маркированными графами. [2]

Маркированные графы - это подкласс сетей Петри, в которых проявляется параллелизм, но отсутствуют конфликты. Эта работа является основным источником определения маркированных графов и результатов по этому вопросу. В ней разбираются алгоритмы решения задач безопасности, активности и достижимости и другие вопросы. [3]

Маркированные графы двойственны автоматным сетям Петри в теоретико-графовом смысле, поскольку в автоматных сетях Петри переходы имеют один вход и один выход, в то время как в маркированных графах один вход и один выход имеют позиции. Они являются двойственными также и с точки зрения моделирования. В автоматных сетях Петри легко представить конфликтные ситуации с помощью позиции с несколькими выходами, но нельзя моделировать создание и уничтожение фишек, необходимых для моделирования параллельности, или ожидания, свойственные задачам синхронизации. С другой стороны, маркированные графы могут моделировать параллельность и синхронизацию, но не могут моделировать конфликты или принятие решений, зависящие от данных. [4]

Хотя маркированные графы с заданным распределением подсчитаны Ридом [51], перечисление немаркированных графов с точки зрения этой интересной и важной характеристики осталось незатронутым. Аналогично Рид [52] подсчитал маркированные - окрашенные графы, но для случая немаркированных графов ( задача 8 табл. 1) задача не решена. [5]

Маркированный граф. [6]

Важность циклов в маркированных графах вытекает из следующей теоремы. [7]

Очень хорошее введение в сети Петри и маркированные графы, изложенное с уклоном в теорию переключательных схем. В работе используется матричный подход к представлению сетей Петри и рассматриваются такие понятия, как управляемость в теоретико-системном смысле. Изложение носит учебный характер и является прекрасным примером того, как сети Петри могут широко использоваться в других областях исследований. [8]

Охарактеризуйте класс сетей Петри, которые являются и маркированными графами, и автоматными сетями Петри. [9]

К классу правильных сетей Петри относятся автоматные сети, маркированные графы, сети Петри свободного выбора и сети Петри общего вида. [10]

Сравниваются сети Петри, графы вычислений, схемы параллельных программ и маркированные графы. [11]

Сеть Петри, эквивалентная графу вычислений, изображенному на. [12]

С другой стороны, графы вычислений и конечные автоматы не сопоставимы, как маркированные графы и конечные автоматы. Графы вычислений не могут моделировать принятие решений или условное выполнение - это ограничение справедливо и для маркированных графов. [13]

Достаточно полно изучены только два главных подкласса модели сетей Петри: автоматные сети Петри и маркированные графы. Кроме того, Хэк [107] изучил подкласс, названный сетями Петри со свободным выбором, и сформулировал предположения, что другой подкласс, правильные сети Петри могут иметь хорошие свойства с точки зрения разрешимости. Мы представим каждый из этих классов и укажем их основные свойства, достоинства и недостатки. [14]

Страницы: 1 2