Szanowni Państwo,
Serdecznie zapraszamy na Seminarium Instytutu Informatyki, które odbędzie się w poniedziałek 31 marca 2025 r. o godzinie 12:00 w sali 105MAT. Referat pt. „Probabilistyczna wersja twierdzenie Rabina o drzewach” wygłosi zaproszony gość dr hab. Paweł Parys z Instytutu Informatyki Uniwersytetu Warszawskiego.
Streszczenie: Twierdzenie Rabina o drzewach daje algorytm rozwiązujący problem spełnialności dla logiki monadycznej drugiego rzędu na drzewach nieskończonych. Niedawno rozwiązaliśmy probabilistyczną odmianę tego problemu. Mianowicie pokazaliśmy, jak obliczyć prawdopodobieństwo, że losowo wybrane drzewo spełnia daną formułę. Dodatkowo pokazaliśmy, że to prawdopodobieństwo jest liczbą algebraiczną. Zamyka to pewną linię badań, w której podobne wyniki uzyskano dla formalizmów słabszych niż pełna logika monadyczna drugiego rzędu. Referat będzie oparty na pracy wspólnej z Damianem Niwińskim i Michałem Skrzypczakiem (LICS 2023).
Uniwersytet Opolski
plac Kopernika 11a
45-040 Opole
Rektorat
tel.: 77 541 59 03
Biuro Kanclerza
tel.: 77 541 60 70
NIP: 754-000-71-79
Regon: 000001382
