Nie jesteś zalogowany |
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.
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.
