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-boun...@gecode.org [mailto:users-boun...@gecode.org] On > Behalf Of Pierre Flener > Sent: Tuesday, September 23, 2014 8:55 AM > To: users@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@gecode.org > https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
