Propagating regular counting constraints

Nicolas Beldiceanu 1 Pierre Flener 2 Justin Pearson 2 Pascal van Hentenryck 3
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : Constraints over finite sequences of variables are ubiquitous in sequencing and timetabling. Moreover, the wide variety of such constraints in practical applications led to general modelling techniques and generic propagation algorithms, often based on deterministic finite automata (DFA) and their extensions. We consider counter-DFAs (cDFA), which provide concise models for regular counting constraints, that is constraints over the number of times a regular-language pattern occurs in a sequence. We show how to enforce domain consistency in polynomial time for atmost and atleast regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be incremented by transitions. We also prove that the satisfaction of exact regular counting constraints is NP-hard and indicate that an incomplete algorithm for exact regular counting constraints is faster and provides more pruning than the existing propagator from [3]. Regular counting constraints are closely related to the CostRegular constraint but contribute both a natural abstraction and some computational advantages.
Complete list of metadatas

https://hal.inria.fr/hal-00874338
Contributor : Contraintes Lina <>
Submitted on : Thursday, October 17, 2013 - 3:42:43 PM
Last modification on : Friday, June 22, 2018 - 9:31:24 AM

Identifiers

  • HAL Id : hal-00874338, version 1

Citation

Nicolas Beldiceanu, Pierre Flener, Justin Pearson, Pascal van Hentenryck. Propagating regular counting constraints. [Research Report] 2013, pp.16. ⟨hal-00874338⟩

Share

Metrics

Record views

228