Взаємне блокування: відмінності між версіями

[неперевірена версія][неперевірена версія]
Вилучено вміст Додано вміст
Kostpolt (обговорення | внесок)
мНемає опису редагування
Kostpolt (обговорення | внесок)
мНемає опису редагування
Рядок 33:
=== Мережі Петрі ===
 
В [[Мережа Петрі|мережах Петрі]], ''тупиком'' називається така множина позицій, що кожен перехід, який на виході має одну із позицій тупика, використовує будь-яку позицію тупика в якості входу. Тобто, якщо всі позиції типика в деякий момент спорожніють, то вся ця множина позицій залишиться порожньою назавжди. Жоден із переходів не може пересунути фішку в тупик, оскільки в тупику відсутні фішки, які б дозволили перехід, виходом якого є позиція з тупика.<ref>(Hack 1972)name="hack"></ref><ref>(Питерсон 1984), розділ 7.4.3, стор. 202—203.</ref>
 
''Пасткою'' називається така множина позицій, для якої кожен перехід, входом якого є одна із позицій множини на виході має іншу позицію множини. Тобто, якщо в довільній позиції пастки є фішка, то вона завжди перебуватиме в деякій із позицій пастки.
 
Було доведено<ref>(Hack 1972)name="hack"></ref>, що необхідною і достатньою умовою активності маркованої мережі Петрі з вільним вибором є вимога того, щоб кожен тупик містив пастку з фішкою.
 
== Обробка тупикових ситуацій ==