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

[Christian Schulte]

Hi Pierre,

Thanks for the announcement. If there is anybody who is interested, maybe
that person could also be interested to clean the implementation up, design
a nice interface to the propagator for CFGs (in the style of regular
expressions or DFAs in Gecode).

If you are interested, please get in touch with me!

Cheers
Christian

--
Christian Schulte, www.ict.kth.se/~cschulte/

> -----Original Message-----
> From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On
> Behalf Of Pierre Flener
> Sent: Tuesday, September 23, 2014 8:55 AM
> To: users at gecode.org
> Cc: Jun He
> Subject: [gecode-users] a propagator for the Context-Free-Grammar
constraint
> 
> 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
> users at gecode.org
> https://www.gecode.org/mailman/listinfo/gecode-users