[gecode-users] a propagator for the Context-Free-Grammar constraint

[Pierre Flener]

Hi all,

As a useful complement to the built-in REGULAR constraint of Gecode, constraining a fixed-length sequence of variables to form a word that belongs to the regular language defined by a regular expression (RE) or (non-)deterministic finite automaton (NFA/DFA), there exists the CFG constraint, which constrains a fixed-length sequence of variables to form a word that belongs to the context-free language defined by a context-free grammar (CFG).  Languages of words of fixed length are finite, and hence regular, so a CFG constraint over fixed-length sequences is theoretically not needed.  However, there are languages where a context-free grammar is much more compact than an RE/DFA/NFA, to the point that the cubic-time propagation of the CFG constraint pays off versus the much lower time complexity of a REGULAR propagator.  So far, Gecode unfortunately lacks a CFG constraint.

The state-of-the-art propagator for the CFG constraint described in

	J. He, P. Flener, J. Pearson, and W. M. Zhang.
	Solving string constraints: The case for constraint programming.
	In: Ch. Schulte (editor), CP 2013, pages 381-397. Lecture Notes in Computer Science, volume 8124.
	Springer, 2013.
	http://dx.doi.org/10.1007/978-3-642-40627-0_31
	http://www.it.uu.se/research/group/astra/publications/CP13cfg.pdf
	http://cp2013.a4cp.org/slides/44.pdf

was implemented in Gecode by Jun He (Cc:ed) and is made available at http://www.it.uu.se/research/group/astra/software#cfg : note that the implementation is provided as is, and does not fully comply yet with Gecode style, but we hope it will already be useful to some.

Cheers,
Pierre