Evaluating Formulas on Graphs
Add to your list(s)
Download to your calendar using vCal
If you have a question about this talk, please contact Thomas Tuerk.
We consider the computational complexity of the following problem: given a firstorder formula f in the language of graphs (i.e. with one binary relation) and a finite graph G, determine whether f is satisfied in G. The complexity is generally exponential in the
size of f, though polynomial in the size of G. The problem is quite general and encompasses many known hard decision problems on graphs. I well explain how the problem can be made more tractable on restricted classes of graphs, which will lead us to a brief exploration of graph structure theory.
This talk is part of the Computer Laboratory Automated Reasoning Group Lunches series.
This talk is included in these lists:
Note that exdirectory lists are not shown.
