Сеть Петри с дугой сброса

Question

Как найти обычную сеть Петри, эквивалентную сети Петри с дугой сброса? Эта обычная сеть должна уважать семантику сброса сети Петри.

С наилучшими пожеланиями.

Answer 1

Невозможно найти обычную сеть Петри, которая была бы эквивалентна произвольной сети Петри с дугами сброса в каком-либо значимом смысле.

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

В своей работе 1977 года Тоширо Араки и Тадао Касами доказали, сводя встречные автоматы Минского (см. Теорему 5) к сетям Петри с дугами сброса, что проблема достижимости для сетей Петри с дугами сброса неразрешима.

В то время как в 1981 году Эрнст Майр представил алгоритм задачи достижимости для обычных сетей Петри.

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

Статьи, приведенные выше, требуют немного технических знаний для чтения, что обычно не ожидается от студентов CompSci. Для справки по этому вопросу я бы предложил оригинал М.Л. Минского "Вычисления: конечные и бесконечные машины" или любой современный вводный текст по логике в информатике.