Scholarlink

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 \(\texttt {ctr}\) , we show how to use the synchronised product of DFAs wrt constraint \(\texttt {ctr}\) to obtain a Berge-acyclic decomposition ensuring Generalised Arc Consistency (GAC). Such decomposition consists of one regular and n table constraints. We illustrate the effectiveness of this method by solving a hydrogen distribution problem, finding optimal solutions and proving optimality quickly.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Generalised Arc Consistency via the Synchronised Product of Finite Automata with Respect to a Constraint

  • 会议论文

  • 发表日期：

    2026年

查看全文
  • Nicolas Beldiceanu

摘要

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 \(\texttt {ctr}\) , we show how to use the synchronised product of DFAs wrt constraint \(\texttt {ctr}\) to obtain a Berge-acyclic decomposition ensuring Generalised Arc Consistency (GAC). Such decomposition consists of one regular and n table constraints. We illustrate the effectiveness of this method by solving a hydrogen distribution problem, finding optimal solutions and proving optimality quickly.