No satisfiability measure for first-order logic on graphs

Prelegent(ci)

Mikołaj Bojańczyk

Afiliacja

Uniwersytet Warszawski

Termin

23 marca 2011 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---