Generalised Arc Consistency via the Synchronised Product of Finite Automata wrt a Constraint

Abstract

Given an $m$ by $n$ matrix $V$ of domain variables $v_{i,j}$ (with $i$ from $1$ to $m$ and $j$ from $1$ to $n$), where each row $i$ must be accepted by a specified Deterministic Finite Automaton (DFA) ${\mathcal{A}}_i$ and each column $j$ must satisfy the same constraint $\text{ctr}$, we show how to use the \emph{synchronised product of DFAs wrt constraint} $\text{ctr}$ to obtain a Berge-acyclic decomposition ensuring Generalised Arc Consistency (GAC). Such decomposition consists of one \texttt{regular} and $n$ \texttt{table} constraints. We illustrate the effectiveness of this method by solving a hydrogen distribution problem, finding optimal solutions and proving optimality quickly.

arXiv comment18 pages, 2 figures, 1 table