In this work we consider modeling of services with workflow modules, which form a Petri net subclass. The service compatibility problem is to answer the question, whether two services fit together, i.e. whether the composed system is correct. We study complementarity of resources, produced/consumed by two services—a necessary condition for the service compatibility. Resources, which are produced/consumed by a service, are represented as a multiset language. We define an algebra of multiset languages and present algorithms for checking conformance of resources for two given well-structured workflow modules.
Атрибутивное исследование свойств функций на множествах.
Автоматы, управляемые ресурсами, (RDA) представляют собой конечные автоматы, которые располагаются в узлах конечной системной сети и асинхронно потребляют/производят через порты (дуги системной сети) некоторые общие ресурсы. При этом RDA сами могут служить ресурсами друг для друга, что делает модель весьма гибкой. Ранее было доказано, что RDA-сети эквивалентны по выразительности сетям Петри.
В этой работе вводится новый формализм клеточных RD-автоматов. Клеточные RD-автоматы – это RDA-сети с бесконечной системной сетью, имеющей некоторую регулярную структуру. Мы строим иерархию классов клеточные RD-автоматов на основе тех или иных ограничений на несущую решетку. В работе изучается выразительность нескольких основных классов одноразмерной решетки.
Вложенные сети Петри (NP-сети) – суть сети Петри с сетевыми фишками. Проблемы живости и ограниченности неразрешимы для двухуровневых NP-сетей. Для обыкновенных сетей Петри проблема ограниченности относится к классу сложности EXPSPACE, а проблема живости не меньше чем EXPSPACE-сложная. Однако для некоторых ограниченных классов, таких как сети Петри со свободным выбором, эти проблемы являются не такими трудными. Проверка ограниченности и живости сетей Петри со свободным выбором разрешима за полиномиальное время.
В этой статье мы доказываем, что для NP-сетей ограниченность может проверяться композиционально, и формулируем условия композициональности живости. Эти результаты могут использоваться для сведения проверки ограниченности и живости NP-сетей к проверке этих свойств для отдельных одноуровневых компонентов. Компоненты NP-сети могут принадлежать легко анализируемым подклассам сетей Петри, или иметь небольшой размер, что позволяет использовать для их анализа методы проверки моделей.