On singleton arc consistency for CSPs defined by monotone patterns

Autor: Martin C. Cooper, David Cohen, Clément Carbonnel, Stanislav Zivny
Přispěvatelé: Department of Computer Science [Oxford], University of Oxford [Oxford], Royal Holloway [University of London] (RHUL), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Centre National de la Recherche Scientifique - CNRS (FRANCE), Institut National Polytechnique de Toulouse - Toulouse INP (FRANCE), Université Toulouse III - Paul Sabatier - UT3 (FRANCE), Université Toulouse - Jean Jaurès - UT2J (FRANCE), Université Toulouse 1 Capitole - UT1 (FRANCE), Royal Holloway University of London - RHUL (UNITED KINGDOM), University of Oxford (UNITED KINGDOM), Institut de Recherche en Informatique de Toulouse - IRIT (Toulouse, France), University of Oxford, Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT), Engineering and Physical Sciences Research Council (EPSRC) UK, Grant EPSRC EP/L021226/1, Royal Society University Research Fellowship, ANR-11-LABX-0040,CIMI,Centre International de Mathématiques et d'Informatique (de Toulouse)(2011), ANR-11-IDEX-0002,UNITI,Université Fédérale de Toulouse(2011), European Project: 714532,Horizon 2020, Herbstritt, Marc
Rok vydání: 2018
Předmět:
FOS: Computer and information sciences
General Computer Science
Discrete Mathematics (cs.DM)
Computer Science - Artificial Intelligence
Constraint satisfaction problem
Constraint Satisfaction Problems
Forbidden Patterns
0102 computer and information sciences
02 engineering and technology
Type (model theory)
Computational Complexity (cs.CC)
01 natural sciences
Article
[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Combinatorics
Simple (abstract algebra)
0202 electrical engineering
electronic engineering
information engineering
Mathematics
000 Computer science
knowledge
general works
Singleton
Applied Mathematics
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
Informatique et langage
Apprentissage
Computer Science Applications
Constraint (information theory)
Computer Science - Computational Complexity
Monotone polygon
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
Artificial Intelligence (cs.AI)
010201 computation theory & mathematics
Bounded function
Forbidden pattern
Singleton arc consistency
Computer Science
Local consistency
020201 artificial intelligence & image processing
Singleton Arc Consistency
Computer Science - Discrete Mathematics
Zdroj: 35th Symposium on Theoretical Aspects of Computer Science
International Symposium on Theoretical Aspects of Computer Science (STACS)
International Symposium on Theoretical Aspects of Computer Science (STACS), Feb 2018, Caen, France. pp.19-20, ⟨10.4230/LIPIcs.STACS.2018.19⟩
Algorithmica
Algorithmica, Springer Verlag, 2019, 81 (4), pp.1699-1727. ⟨10.1007/s00453-018-0498-2⟩
35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Algorithmica, 2019, 81 (4), pp.1699-1727. ⟨10.1007/s00453-018-0498-2⟩
ISSN: 0178-4617
1432-0541
DOI: 10.1007/s00453-018-0498-2
Popis: Singleton arc consistency is an important type of local consistency which has been recently shown to solve all constraint satisfaction problems (CSPs) over constraint languages of bounded width. We aim to characterise all classes of CSPs defined by a forbidden pattern that are solved by singleton arc consistency and closed under removing constraints. We identify five new patterns whose absence ensures solvability by singleton arc consistency, four of which are provably maximal and three of which generalise 2-SAT. Combined with simple counter-examples for other patterns, we make significant progress towards a complete classification.
v4: Full version of a STACS'18 paper; improved presentation
Databáze: OpenAIRE
Externí odkaz: