2025/11/14 by Pierre J. Talbot, Talbot, Pierre
Computer Science · #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Formal Methods in Verification #Parallel Computing and Optimization Techniques #Symbolic Computation (cs.SC)
paper · pdf · doi:10.48550/arxiv.2511.11872
openalex publication_date 2025/11/14 · openalex created_date 2025/11/19 · openalex updated_date 2026/07/28
Constraint programming is a general and exact method based on constraint propagation and backtracking search. We provide a function decomposing a constraint network into a ternary constraint network (TCN) with a reduced number of operators. TCNs are not new and have been used since the inception of constraint programming, notably in constraint logic programming systems. This work aims to specify formally the decomposition function of discrete constraint network into TCN and its preprocessing. We aim to be self-contained and descriptive enough to serve as the basis of an implementation. Our primary usage of TCN is to obtain a regular data layout of constraints to efficiently execute propagators on graphics processing unit (GPU) hardware.