8.8. Расширенные модели сетей Петри

В качестве последнего дополнения к нашей иерархии вспомним о моделях расширенных сетей Петри, изученных в гл. 7: сети Петри с областями ограничений, переходами исключающее ИЛИ, переключателями, сдерживающими дугами, приоритетами или временными ограничениями. Мы видели, что все эти модели эквивалентны машинам Тьюринга. Таким образом, эти модели строго включают модели сетей Петри. Окончательная иерархия моделей изображена на рис. 8.21.

8.9. Замечания к литературе

Исследования [240, 5, 178] должны быть прочитаны в первую очередь, поскольку наиболее тесно связаны с тематикой главы. Следует также прочесть обзоры [41, 20] и работы [197, 198]. В этих статьях имеются ссылки на оригинальные работы по отдельным моделям.

Модель Риддла [258] кажется наиболее предпочтительной для моделирования больших программных систем и заслуживает детального изучения.

8.10. Темы для дальнейшего изучения

1. Расширьте иерархию, приведенную на рис. 8.21, включив в нее ограниченные модели сетей Петри, обсужденные в гл. 7: сети Петри со свободным выбором и правильные сети Петри.

2. Исследуйте свойства языков, определенных классами моделей, рассмотренных в этой главе, и соотнесите их с регулярными, контекстно-свободными и контекстно-связанными языками.

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

4. Расширьте работу, проделанную в этой главе, и включите модели, описанные в [2, 3, 180, 260, 271, 284].