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
_______________________________________________
Gecode users mailing list
[email protected]
https://www.gecode.org/mailman/listinfo/gecode-users
