The MSO+U theory of
- Prelegent(ci)
- Mikołaj Bojańczyk
- Afiliacja
- Uniwersytet Warszawski
- Termin
- 25 marca 2015 14:15
- Pokój
- p. 5870
- Seminarium
- Seminarium „Teoria automatów”
We consider the logic MSO+U, which is monadic second-order logic extended with the unbounding quantifier. The unbounding quantifier is used to say that a property of finite sets holds for sets of arbitrarily large size. We prove that the logic is undecidable on infinite words, i.e. the MSO+U theory of (N,<) is undecidable. This settles an open problem about the logic, and improves a previous undecidability result, which used infinite trees and additional axioms from set theory.