---
abstract: '> A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a *constraint language*. In this article, we study arc consistency, a heavily investigated inference method, and three extensions thereof from the perspective of constraint languages. We conduct a comparison of the studied methods on the basis of which constraint languages they solve, and we present new polynomial-time tractability results for singleton arc consistency, the most powerful method studied.'
author:
- 'Hubie Chen[^1], Victor Dalmau[^2], Berit Grußien[^3]'
bibliography:
- 'local.bib'
title: Arc Consistency and Friends
---

\[theorem\] [Lemma]{} \[theorem\] [Remark]{} \[theorem\] [Fact]{} \[theorem\] [Claim]{} \[theorem\] [Corollary]{} \[theorem\] [Definition]{} \[theorem\] [Proposition]{} \[theorem\] [Warning]{} \[theorem\] [Example]{}

Introduction
============

Background
----------

The constraint satisfaction problem (CSP) involves deciding, given a set of variables and a set of constraints on the variables, whether or not there is an assignment to the variables satisfying all of the constraints. Cases of the constraint satisfaction problem appear in many fields of study, including artificial intelligence, spatial and temporal reasoning, logic, combinatorics, and algebra. Indeed, the constraint satisfaction problem is flexible in that it admits a 