zpravodaj ČSKI
aktuální číslo
přednáška
archiv
  - 2019
  - 2018
  - 2017
  - 2016
  - 2015
  - 2014
  - 2013
  - 2012
  - 2011
  - 2010
  - 2009
  - 2008
  - 2007
  - 2006
  - 2005
  - 2004
  - 2003
  - 2002
  - 2001
  - 2000
  - 1999
  - 1998
  - 1997
  - 1996
  - 1995
  - 1994
 
 
zpravodaj ČSKI - leden 2017 [ pdf ]
[ zaslat oznámení o přednášce ]
leden|únor|duben|květen|červen|listopad|prosinec


datum: 18.1.2017 v 10:00
název: Algebraic Approach to Valued CSP via Nonclassical Logics
přednášející: Rostislav Horčík (UI)
místo konání: UI, 2.patro, místnost č.318

souhrn: CSP provides a uniform framework to analyze and solve many combinatorial problems. Similarly valued CSP might be seen as a uniform framework to study a wide class of problems coming from combinatorial optimization such as Maximum Independent Set. A major research line in CSP tries to find a boundary between tractable and intractable problems. One of the most successful approaches to classify tractable problems is the algebraic one based on Geiger’s result characterizing pp-definability via polymorphisms. A similar approach was investigated also in valued CSP but only for problems using as a valuation structure the set of positive rational numbers extended with infinity endowed with the usual addition. We show that this approach can be taken to a wider setting by generalizing Geiger’s result. It turns out that valued CSP can be viewed as CSP over a non-classical logic. Consequently, we obtain the generalization of Geiger’s result by characterizing ppdefinability in relational structures over this logic.