Dear All,
You are cordially invited to the Seminar of the Institute of Computer Science, which will be held on Monday, March 31, 2025 at 12:00 pm in room 105MAT. The paper entitled. “Probabilistic version of Rabin’s theorem about trees” will be given by invited guest Dr. Paweł Parys from the Institute of Computer Science, University of Warsaw.
Abstract: Rabin’s tree theorem gives an algorithm to solve the satisfiability problem for second-order monadic logic on infinite trees. We recently solved a probabilistic variant of this problem. Namely, we showed how to calculate the probability that a randomly selected tree satisfies a given formula. In addition, we showed that this probability is an algebraic number. This closes a line of research in which similar results were obtained for formalisms weaker than full second-order monadic logic. The paper will be based on joint work with Damian Niwinski and Michal Skrzypczak (LICS 2023).
Institute of Computer Science
Oleska 48 st.,
45-052 Opole, Poland
tel. +48 77 45 27 205,
e-mail: ii@uni.opole.pl
University of Opole
Kopernika 11a st.
45-040 Opole, Poland
Rectorate
tel.: +48 77 541 59 03
Chancellor’s Office
tel.: +48 77 541 60 70
TAX ID: 754-000-71-79
Regon: 000001382
carefully created by University of Opole