link.springer.com

The Weighted Cfg Constraint

Abstract

We introduce the weighted Cfg constraint and propose a propagation algorithm that enforces domain consistency in O(n 3|G|) time. We show that this algorithm can be decomposed into a set of primitive arithmetic constraints without hindering propagation.

Preview

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Cote, M.-C., Bernard, G., Claude-Guy, Q., Louis-Martin, R.: Formal languages for integer programming modeling of shift scheduling problems. Technical Report, Center for Research on Transportation, Montreal (2007)

    Google Scholar 

  2. Demassey, S., Pesant, G., Rousseau, L.-M.: Constraint programming based column generation for employee timetabling. In: Barták, R., Milano, M. (eds.) CPAIOR 2005. LNCS, vol. 3524, Springer, Heidelberg (2005)

    Google Scholar 

  3. Ney, H.: Dynamic programming parsing for context-free grammars in continuous speech recognition. IEEE Trans. on Signal Processing 39(2), 336–340 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  4. Pesant, G.: A regular language membership constraint for finite sequences of variables. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, Springer, Heidelberg (2004)

    Google Scholar 

  5. Quimper, C.-G., Louis-Martin, R.: A large neighbourhood search approach to the multi-activity shift scheduling problem. Technical Report, Center for Research on Transportation, Montreal (2007)

    Google Scholar 

  6. Quimper, C.-G., Walsh, T.: Global Grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  7. Quimper, C.-G., Walsh, T.: Decomposing Global Grammar constraints. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  8. Sellmann, M.: The theory of Grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, Springer, Heidelberg (2006)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of New South Wales and NICTA, Sydney, Australia

    George Katsirelos, Nina Narodytska & Toby Walsh

Authors

  1. George Katsirelos

    You can also search for this author in PubMed Google Scholar

  2. Nina Narodytska

    You can also search for this author in PubMed Google Scholar

  3. Toby Walsh

    You can also search for this author in PubMed Google Scholar

Editor information

Laurent Perron Michael A. Trick

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Katsirelos, G., Narodytska, N., Walsh, T. (2008). The Weighted Cfg Constraint. In: Perron, L., Trick, M.A. (eds) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. CPAIOR 2008. Lecture Notes in Computer Science, vol 5015. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68155-7_31

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-68155-7_31

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-68154-0

  • Online ISBN: 978-3-540-68155-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us