You are not logged in |
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.
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.
