Cтраница 2
Маркированные графы были рассмотрены в разд. Как подкласс сетей Петри маркированные графы, очевидно, обладают более ограниченной мощностью моделирования. Маркированные графы непосредственно не сопоставимы с конечными автоматами, но, по-видимому, являются двойственными к ним. Таким образом, мы получаем изображенное на рис. 8.1 соотношение между сетями Петри, конечными автоматами и маркированными графами. [16]
Конечно, существует очень много трудных задач о маркированных графах, например задача Лизинга. Некоторые задачи перечисления маркированных графов, однако, так просты, что могут быть немедленно решены. [17]
Описываются и сравниваются структуры управления нескольких моделей параллельных вычислений. Эти модели включают конечные автоматы, сети Петри, графы UCLA, системы сообщений, графы вычислений, схемы параллельных программ, маркированные графы и сети координации. [18]
Маркированные графы были рассмотрены в разд. Как подкласс сетей Петри маркированные графы, очевидно, обладают более ограниченной мощностью моделирования. Маркированные графы непосредственно не сопоставимы с конечными автоматами, но, по-видимому, являются двойственными к ним. Таким образом, мы получаем изображенное на рис. 8.1 соотношение между сетями Петри, конечными автоматами и маркированными графами. [19]
Хотя в исследовании свойств языков сетей Петри сделано уже немало, многое еще предстоит сделать. Из всех определенных классов языков изучены только два - Р - и L-типа, и они только для обычных сетей. Было определено несколько подмножеств множества обычных сетей Петри: маркированные графы, бесконфликтные сети, простые сети, сети со свободным выбором ( гл. Каждый из этих классов сетей Петри, по-видимому, имеет свой класс языков с присущими им отличительными особенностями. Некоторые исследования этих классов уже проведены. Извести о [115], что классы L, Z /, G, Gx, Р и Рх для простых сетей Петри ( без петель и кратных дуг, все комплекты - множества, и для каждого tj I ( tj) Л 0 ( tj) 0) идентичны соответствующим классам для обычных сетей Петри. Нетрудно видеть также, что классы Lx, Gx и Рх не изменятся при ограничении сетей до сетей со свободным выбором ( см. разд. Остаются не изученными еще многие интересные случаи. В частности, языки, порождаемые маркированными графами или в общем случае бесконфликтными сетями, как оказалось, имеют структуру, напоминающую структуру детерминированных контекстно-свободных языков, их исследование многообещающе. [20]
В нем собраны вместе работы Ижбики, Хенхапля, Хансаля и Шваба. Изложение очень формальное, наполненное таинственными обозначениями и теоремами и связано с маркированными графами. [21]
Маркированные графы двойственны автоматным сетям Петри в теоретико-графовом смысле, поскольку в автоматных сетях Петри переходы имеют один вход и один выход, в то время как в маркированных графах один вход и один выход имеют позиции. Они являются двойственными также и с точки зрения моделирования. В автоматных сетях Петри легко представить конфликтные ситуации с помощью позиции с несколькими выходами, но нельзя моделировать создание и уничтожение фишек, необходимых для моделирования параллельности, или ожидания, свойственные задачам синхронизации. С другой стороны, маркированные графы могут моделировать параллельность и синхронизацию, но не могут моделировать конфликты или принятие решений, зависящие от данных. [22]
Работа Хольта по развитию науки об информации и системах называется систематикой. В данной статье имеется превосходное изложение основ этой работы и начал теории сетей Петри. Сети Петри определяются и иллюстрируются. На протяжении всей работы рассматриваются маркированные графы и автоматы. [23]
Монография обобщает результаты исследований в области распределенных вычислений в масштабируемых средах, к которым можно отнести мультикомпьютеры, кластеры, симметричные мультипроцессоры, системы с распределенной памятью и ресурсы метакомпьютинга. Основное внимание уделяется различным формам модели обмена сообщениями и ее реализуемости, в том числе архитектурами с общей памятью. Рассматриваются вопросы семантики, однозначности результата и блокировки вычислений. Изучаются методы анализа свойств распределенных программ на маркированных графах и исследуется проблема алгоритмической разрешимости задачи анализа. Обосновываются принципы прогнозирования времени выполнения программ и их отображения на целевую архитектуру. Предлагаются методы планирования параллельных процессов в распределенных средах на основе масштабируемых моделей обработки. [24]
Маркированные графы были рассмотрены в разд. Как подкласс сетей Петри маркированные графы, очевидно, обладают более ограниченной мощностью моделирования. Маркированные графы непосредственно не сопоставимы с конечными автоматами, но, по-видимому, являются двойственными к ним. Таким образом, мы получаем изображенное на рис. 8.1 соотношение между сетями Петри, конечными автоматами и маркированными графами. [25]
Хотя в исследовании свойств языков сетей Петри сделано уже немало, многое еще предстоит сделать. Из всех определенных классов языков изучены только два - Р - и L-типа, и они только для обычных сетей. Было определено несколько подмножеств множества обычных сетей Петри: маркированные графы, бесконфликтные сети, простые сети, сети со свободным выбором ( гл. Каждый из этих классов сетей Петри, по-видимому, имеет свой класс языков с присущими им отличительными особенностями. Некоторые исследования этих классов уже проведены. Извести о [115], что классы L, Z /, G, Gx, Р и Рх для простых сетей Петри ( без петель и кратных дуг, все комплекты - множества, и для каждого tj I ( tj) Л 0 ( tj) 0) идентичны соответствующим классам для обычных сетей Петри. Нетрудно видеть также, что классы Lx, Gx и Рх не изменятся при ограничении сетей до сетей со свободным выбором ( см. разд. Остаются не изученными еще многие интересные случаи. В частности, языки, порождаемые маркированными графами или в общем случае бесконфликтными сетями, как оказалось, имеют структуру, напоминающую структуру детерминированных контекстно-свободных языков, их исследование многообещающе. [26]