Sieci Petriego to stosunkowo prosty model obliczeń, a przy tym wciąż słabo zrozumiany ze strony teoretycznej i przez to ciekawy. Opowiem o problemie osiągalności w sieciach Petriego, który pyta, czy zaczynając z zadanej konfiguracji początkowej można osiągnąć zadaną konfigurację końcową po skończonej liczbie ruchów. Pokażę, że problem ten pomimo prostego sformułowania jest dalece nietrywialny i postaram się przybliżyć idee, które stoją
za niedawną poprawą dolnego ograniczenia na jego złożoność obliczeniową.
Petri nets are relatively simple computation model, which is still not well understood from the theoretical point of view, and therefore interesting. I will tell about reachability problem in Petri nets, which asks whether one can reach
in finitely many moves a given final configuration when starting from a given initial configuration. I will show that this problem is highly nontrivial
despite a simple formulation and I will try to explain ideas, which stay behind recent improvement of the lower bound for the computational complexity
of this problem.
Nie jesteś zalogowany |
