Propagating Regular Counting Constraints
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
The Polynomial Counting Capabilities of Message Passing Neural Networks
The counting power of Message Passing Neural Networks (MPNN) has been the subject of many recent papers, showing that they can express logic that involves counting up to a threshold or more generally satisfy a linear ari…
The Regularization of Small Sub-Constraint Satisfaction Problems
This paper describes a new approach on optimization of constraint satisfaction problems (CSPs) by means of substituting sub-CSPs with locally consistent regular membership constraints. The purpose of this approach is to …
Drone-based Object Counting by Spatially Regularized Regional Proposal Network
Existing counting methods often adopt regression-based approaches and cannot precisely localize the target objects, which hinders the further analysis (e.g., high-level understanding and fine-grained classification). In …
Object CountingRegion ProposalVariational Attention: Propagating Domain-Specific Knowledge for Multi-Domain Learning in Crowd Counting
In crowd counting, due to the problem of laborious labelling, it is perceived intractability of collecting a new large-scale dataset which has plentiful images with large diversity in density, scene, etc. Thus, for learn…
Crowd CountingDiversityUncertain Linear Logic via Fibring of Probabilistic and Fuzzy Logic
Beginning with a simple semantics for propositions, based on counting observations, it is shown that probabilistic and fuzzy logic correspond to two different heuristic assumptions regarding the combination of propositio…