Recursion Schemes and the WMSO+U Logic
- Prelegent(ci)
- Paweł Parys
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 4 kwietnia 2018 14:15
- Pokój
- p. 5050
- Seminarium
- Seminarium „Teoria automatów”
We study the weak MSO logic extended by the unbounding quantifier (WMSO+U), expressing the fact that there exist arbitrarily large finite sets satisfying a given property. We prove that it is decidable whether the tree generated by a given higher-order recursion scheme satisfies a given sentence of WMSO+U.