23.10.2003

Systemy tranzycji bez tranzycji

Andrzej Ehrenfeucht i Grzegorz Rozenberg badali częściowe 2-struktury, czyli właściwie systemy tranzycji, podając warunki kiedy mogą być one reprezentowane jako grafy których wierzchołki są zbiorami -- są to aksjomaty oddzielania, takie systemy tranzycji mogą być realizowane za pomocą sieci Petriego. Przedstawię wyniki badań prowadzonych wspólnie z Philipem Darondeau, w których badaliśmy możliwość przedstawienia częściowej 2-struktury jako grafu
(a) pełnego
(b) spełniającego aksjomaty oddzielania.
Spełnienie pierwszego warunku można rozumieć jako chęć uważania podawanych jawnie tranzycji jedynie jako generatorów możliwych tranzycji. W ten sposób system tranzycji jest jakby ich pozbawiony -- wszystkie przejścia są dopuszczalne. Prezentowane wyniki bazują na i uzupełniają klasyczne wyniki Ehrenfeuchta i Rozenberga.