Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, November 08, 2007, 12:15 pm
Duration: This information is not available in the database
Location: OAT S15/S16/S17
Speaker: Jan Foniok
Some polynomial cases of the Constraint Satisfaction Problem are characterised by the existence of a suitable complete set of obstructions. One of the polynomial cases is when there exists a complete set of obstructions that are all trees. In this case the template is said to have tree duality. If a digraph H has tree duality, then also its arc-graph delta(H) has tree duality.
A construction called Sproink is developed such that if H has tree duality, then the set of all Sproinks of all the tree obstructions for H is a complete set of tree obstructions for the arc-graph delta(H). Moreover, starting from digraphs with finite duality repeatedly using products and the arc-graph functor generates a class of digraphs with tree duality. These are definitely not all digraphs with tree duality (because all generated digraphs have the near-unanimity function and have bounded height of tree obstructions) but it remains to see what particular subclass this process actually generates.
Joint work with Claude Tardif.
Automatic MiSe System Software Version 1.4803M | admin login