New conditions for Taylor varieties and CSP

被引：11
|
作者：
Barto, Libor [1 ]
Kozik, Marcin [2 ]
机构：
[1] Charles Univ Prague, Dept Algebra, Prague, Czech Republic
[2] Jagiellonian Univ, TCS Jagiellonian, PL-31007 Krakow, Poland
来源：
25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010) | 2010年
关键词：
Constraint Satisfaction Problem; Taylor conditions; CONSTRAINT SATISFACTION PROBLEMS; FINITE-ALGEBRAS; BOUNDED WIDTH; COMPLEXITY;
D O I：
10.1109/LICS.2010.34
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We provide two new characterizations for finitely generated varieties with Taylor terms. The first characterization is using "absorbing sets" and the second one "cyclic operations". These new conditions allow us to reprove the conjecture of Bang-Jensen and Hell (proved by the authors, comp. STOC'08, SICOMP'09) and the characterization of locally finite Taylor varieties using weak near-unanimity operations (proved by McKenzie and Maroti, Alg.Univ. 2009) in an elementary and self-contained way. The research is closely connected to the algebraic approach to CSP and previous results obtained by authors using similar tools [comp. STOC'08, SICOMP'09, FOCS'09 etc.].
引用
收藏
页码：100 / 109
页数：10
相关论文
共 11 条
  • [1] Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP
    Barto, Libor
    Brady, Zarathustra
    Bulatov, Andrei
    Kozik, Marcin
    Zhuk, Dmitriy
    2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2021,
  • [2] A new algorithm based CSP framework for RFID network planning
    Atef Jaballah
    Aref Meddeb
    Journal of Ambient Intelligence and Humanized Computing, 2021, 12 : 2905 - 2914
  • [3] A new algorithm based CSP framework for RFID network planning
    Jaballah, Atef
    Meddeb, Aref
    JOURNAL OF AMBIENT INTELLIGENCE AND HUMANIZED COMPUTING, 2021, 12 (02) : 2905 - 2914
  • [4] A continuous valued neural network with a new evaluation function of degree of unsatisfaction for solving CSP
    Nakano, T
    Nagamatu, M
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2006, E89D (04): : 1555 - 1562
  • [5] Optimal strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
    Jovanovic, Jelena
    Markovic, Petar
    McKenzie, Ralph
    Moore, Matthew
    ALGEBRA UNIVERSALIS, 2016, 76 (03) : 305 - 325
  • [6] Optimal strong Mal’cev conditions for congruence meet-semidistributivity in locally finite varieties
    Jelena Jovanović
    Petar Marković
    Ralph McKenzie
    Matthew Moore
    Algebra universalis, 2016, 76 : 305 - 325
  • [7] LSVF: LEAST SUGGESTED VALUE FIRST A New Search Heuristic to Reduce the Amount of Backtracking Calls in CSP
    de Oliveira Rodrigues, Cleyton Mario
    Dantas Galvao, Eric Rommel
    de Azevedo, Ryan Ribeiro
    Almeida da Silva, Marcos Aurelio
    ICAART 2010: PROCEEDINGS OF THE 2ND INTERNATIONAL CONFERENCE ON AGENTS AND ARTIFICIAL INTELLIGENCE, VOL 1: ARTIFICIAL INTELLIGENCE, 2010, : 416 - 421
  • [8] A characterization of idempotent strong Mal'cev conditions for congruence meet-semidistributivity in locally finite varieties
    Draganic, Nemanja
    Markovic, Petar
    Uljarevic, Vlado
    Zahirovic, Samir
    ALGEBRA UNIVERSALIS, 2018, 79 (03)
  • [9] A characterization of idempotent strong Mal’cev conditions for congruence meet-semidistributivity in locally finite varieties
    Nemanja Draganić
    Petar Marković
    Vlado Uljarević
    Samir Zahirović
    Algebra universalis, 2018, 79
  • [10] "I had to change so much in my life to live with my new limitations": Multimorbid patients' descriptions of their most bothersome chronic conditions
    Slightam, Cindie A.
    Brandt, Kirsten
    Jenchura, Emily C.
    Lewis, Eleanor T.
    Asch, Steven M.
    Zulman, Donna M.
    CHRONIC ILLNESS, 2018, 14 (01) : 13 - 24
12