Department of Computer Science | Institute of Theoretical Computer Science | CADMO

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.

Upcoming talks | All previous talks | Talks by speaker | Upcoming talks in iCal format (beta version!)

Previous talks by year: 2024 2023 2022 2021 2020 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M | admin login