Recursion Schemes and the WMSO+U Logic

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

April 4, 2018, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

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.

 

---