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. This led to general modelling techniques and generic propagators, 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 at-most and at-least regular counting constraints based on the frequent case of a cDFA with only accepting states and a single counter that can be increased by transitions. We also show that the satisfaction of exact regular counting constraints is NP-hard and that an incomplete propagator for exact regular counting constraints is faster and provides more pruning than the existing propagator from (Beldiceanu, Carlsson, and Petit 2004). Finally, by avoiding the unrolling of the cDFA used by COSTREGULAR, the space complexity reduces from O(n · |Σ| · |Q|) to O(n · (|Σ| + |Q|)), where Σ is the alphabet and Q the state set of the cDFA.
Type de document :
Communication dans un congrès
Carla E. Brodley and Peter Stone. Twenty-Eighth AAAI Conference on Artificial Intelligence, Jul 2014, Québec, Canada. AAAI Publications, 2014, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. 〈http://www.aaai.org/ocs/index.php/AAAI/AAAI14/〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01086758
Contributeur : Contraintes Lina <>
Soumis le : lundi 24 novembre 2014 - 18:03:58
Dernière modification le : vendredi 22 juin 2018 - 09:32:18

Identifiants

  • HAL Id : hal-01086758, version 1

Citation

Nicolas Beldiceanu, Pierre Flener, Justin Pearson, Pascal Van Hentenryck. Propagating Regular Counting Constraints. Carla E. Brodley and Peter Stone. Twenty-Eighth AAAI Conference on Artificial Intelligence, Jul 2014, Québec, Canada. AAAI Publications, 2014, Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence. 〈http://www.aaai.org/ocs/index.php/AAAI/AAAI14/〉. 〈hal-01086758〉

Partager

Métriques

Consultations de la notice

209