29.04.2004

Spiski w sieciach Petriego i ich unikanie

Spiski to obliczenia lokalnie uczciwe, które nie są globalnie uczciwe. Dokładniej: akcje umożliwione bezpośrednio są wykonywane, akcje potencjalnie (tzn. kiedyś później) umożliwione nie muszą być wykonywane. Precyzyjne definicje podamy na wykładzie. Sieć nazwiemy bezspiskową jeśli każde jej obliczenie lokalnie uczciwe jest globalnie uczciwe. Pokażemy, że problem "Czy dana sieć jest bezspiskowa?" jest rozstrzygalny dla sieci elementarnych (EN-sieci) i nierozstrzygalny dla sieci dowolnie markowanych (PT-sieci). Opiszemy metody zapewniania bezspiskowej pracy dowolnej sieci, zarowno EN jak i PT. Metody te uwzgledniają, obok uczciwości względem tranzycji, również uczciwość względem miejsc.