Weak MSO+U with path quantifiers

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

15 stycznia 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

Over infinite trees, satisfiability is decidable  for weak monadic second-order logic extended by the unbounding quantifier U and  quantification over infinite paths. The proof is by reduction to emptiness for a certain automaton model, while emptiness for the automaton model is decided using profinite trees.

---