No satisfiability measure for first-order logic on graphs

Speaker(s)

Mikołaj Bojańczyk

Affiliation

Uniwersytet Warszawski

Date

March 23, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Consider MSO on graphs,  with quantification over sets of edges and
sets of nodes.
Tree-width is a good measure of graphs for this logic because: a) for every k,
satisfiability is decidable over graphs of tree-width at most k; and b)
satisfiability is undecidable over any class of graphs that has unbounded
tree-width. I will show that no measure on graphs exists that has
similar properties for first-order logic.

---