Dr Wojciech Czerwiński i prof. Sławomir Lasota z Wydziału Matematyki, Informatyki i Mechaniki są współautorami artykułu o nowym dolnym ograniczeniu na złożoność fundamentalnego problemu osiągalności w sieciach Petriego. Otrzymali nagrodę za najlepszą pracę na konferencji ACM Symposium on Theory of Computing, której komitet wyróżnia autorów artykułów o najbardziej odkrywczych badaniach z informatyki teoretycznej.
Komitet programowy konferencji ACM STOC przyznał nagrodę za najlepszą pracę autorom artykułu „The Reachability Problem for Petri Nets is Not Elementary”. Napisali go dr Wojciech Czerwiński i prof. Sławomir Lasota z Instytutu Informatyki UW we współpracy z partnerami z zagranicy: Rankiem Lazicem z Uniwersytetu Warwick, Jerome’em Leroux z Uniwersytetu w Bordeaux i Filipem Mazowieckim z Uniwersytetu w Bordeaux, absolwentem WMIM.
W pracy autorzy dowodzą nowego dolnego ograniczenia na złożoność fundamentalnego problemu osiągalności w sieciach Petriego. Wcześniejsze dolne ograniczenie udowodnione przez Richarda Liptona w 1976 roku dotąd pozostawało niepoprawione, podejrzewano nawet, że jest optymalne. Nowy wynik nieoczekiwanie obala tę hipotezę i pokazuje, że ten i wiele innych problemów obliczeniowych, z takich dziedzin jak języki formalne, logika, systemy współbieżne i algebra liniowa, są istotnie trudniejsze, niż dotąd przypuszczano.
Na konferencji STOC (oraz równorzędnej FOCS) co roku prezentowanych jest około 100 najważniejszych aktualnych odkryć w informatyce teoretycznej wybranych w konkursie. Od 2003 roku dodatkowo przyznawane są nagrody za najlepszą pracę. Dotąd nie było wśród nich nagrody dla uczonych afiliowanych przy polskiej instytucji naukowej. Tegoroczna nagroda zostanie wręczona podczas konferencji w czerwcu, w Pheonix, w Stanach Zjednoczonych.
Zobacz listę nagrodzonych w ubiegłych latach autorów i ich prac >>
Przeczytaj artukuł „The Reachability Problem for Petri Nets is Not Elementary” >>