Skip to main content
SpringerLink
Log in

The weighted Grammar constraint

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

We introduce the WeightedGrammar constraint and propose propagation algorithms based on the CYK parser and the Earley parser. We show that the traces of these algorithms can be encoded as a weighted negation normal form (WNNF), a generalization of NNF that allows nodes to carry weights. Based on this connection, we prove the correctness and complexity of these algorithms. Specifically, these algorithms enforce domain consistency on the WeightedGrammar constraint in time O(n 3). Further, we propose that the WNNF constraint can be decomposed into a set of primitive arithmetic constraint without hindering propagation.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Bertoni, A., Goldwurm, M., & Santini, M. (2000). Random generation and approximate counting of ambiguously described combinatorial structures. In STACS 2000, 17th annual symposium on theoretical aspects of computer science : Vol. 1770 (pp. 567–580). Berlin: Springer.

    Google Scholar 

  • Cote, M. C., Bernard, G., Claude-Guy, Q., & Louis-Martin, R. (2007). Formal languages for integer programming modeling of shift scheduling problems. In TR.

  • Darwiche, A., & Marquis, P. (2002). A knowledge compilation map. Journal of Artificial Intelligence Research, 17, 229–264.

    Google Scholar 

  • Demassey, S., Pesant, G., & Rousseau, L. M. (2005). Constraint programming based column generation for employee timetabling. In Second international conference, CPAIOR 2005: Vol. 3524/2005, Prague, Czech Republic (pp. 140–154).

  • Demassey, S., Pesant, G., & Rousseau, L. M. (2006). A cost-regular based hybrid column generation approach. Constraints, 11(4), 315–333.

    Article  Google Scholar 

  • Earley, J. (1970). An efficient context-free parsing algorithm. Communications of the ACM, 13(2), 94–102.

    Article  Google Scholar 

  • Eén, N., & Sörensson, N. (2006). Translating pseudo-boolean constraints into sat. Journal on Satisfiability, Boolean Modeling and Computation 2, 1–26.

    Google Scholar 

  • Fargier, H., & Marquis, P. (2007). On valued negation normal form formulas. In M.M. Veloso (Ed.), Proceedings of the 20th international joint conference on artificial intelligence (IJCAI07), Hyderabad, India (pp. 360–365).

  • Gore, V., Jerrum, M., Kannan, S., Sweedyk, Z., & Mahaney, S. (1997). A quasi-polynomial-time algorithm for sampling words from a context-free language. Information and Computation, 134(1), 59–74.

    Article  Google Scholar 

  • Hopcroft, J. E., & Ullman, J. D. (1990). Introduction to automata theory, languages, and computation. Boston: Addison-Wesley, Longman.

    Google Scholar 

  • Jung, J. C. (2008). Value ordering based on solution counting. PhD thesis, University Nova de Lisboa.

  • Kadioglu, S., & Sellmann, M. (2008). Efficient context-free grammar constraints. In: Proceedings of the 23rd national conference on artificial intelligence (pp. 310–316).

  • Katsirelos, G., Narodytska, N., & Walsh, T. (2008). The weighted cfg constraint. In Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, 5th international conference, CPAIOR 2008 : Vol. 5015, Paris, France (pp. 323–327). Berlin: Springer.

    Chapter  Google Scholar 

  • Katsirelos, G., Maneth, S., Narodytska, N., & Walsh, T. (2009). Restricted global grammar constraints. In Proceedings of the 15th international conference on principles and practice of constraint programming, CP 2009 : Vol. 5732, Lisbon, Portugal (pp. 501–508). Berlin: Springer.

    Chapter  Google Scholar 

  • Métivier, J. P., Boizumault, P., & Loudni, S. (2009). Solving nurse rostering problems using soft global constraints. In Proceedings of the 15th international conference on principles and practice of constraint programming, CP 2009 : Vol. 5732, Lisbon, Portugal (pp. 73–87). Berlin: Springer.

    Chapter  Google Scholar 

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

    Article  Google Scholar 

  • Ossowski, J., & Baier, C. (2006). Symbolic reasoning with weighted and normalized decision diagrams. In: Proceedings of the 12th symposium on the integration of symbolic computation and mechanized reasoning: Vol. 151 (pp. 39–56).

  • Pesant, G. (2004). A regular language membership constraint for finite sequences of variables. In M. Wallace (Ed.), Proceedings of 10th international conference on principles and practice of constraint programming (CP’04) : Vol. 3258 (pp. 482–495). Berlin: Springer.

    Google Scholar 

  • Quimper, C. G., & Louis-Martin, R. (2007). A large neighbourhood search approach to the multi-activity shift scheduling problem. In TR.

  • Quimper, C. G., & Walsh, T. (2006). Global Grammar constraints. In F. Benhamou (Ed.), Proceedings of the 12th international conference on principles and practice of constraint programming : Vol. 4204 (pp. 751–755). Berlin: Springer.

    Google Scholar 

  • Quimper, C. G., & Walsh, T. (2007). Decomposing global grammar constraints. In Proceedings of the 13th international conference on principles and practice of constraint programming, CP 2007.

  • Sellmann, M. (2006). The theory of Grammar constraints. In Proceedings of the 12th international conference on the principles and practice of constraint programming (CP06) : Vol. 4204 (pp. 530–544). Berlin: Springer.

    Google Scholar 

  • Van Hentenryck, P., & Michel, L. (2005). Constraint-based local search. Cambridge: The MIT Press.

    Google Scholar 

  • van Hoeve, W. J. (2009). Soft global constraints, tutorial at principles and practice of constraint programming. In CP 2007, 15th international conference.

  • Walsh, T. (2000). Sat v csp. In R. Dechter (Ed.), Principles and practice of constraint programming—CP 2000, 6th international conference, Singapore : Vol. 1894 (pp. 441–456). Berlin: Springer.

    Chapter  Google Scholar 

  • Zanarini, A., & Pesant, G. (2007). Solution counting algorithms for constraint-centered search heuristics. In C. Bessiere (Ed.), Principles and practice of constraint programming—CP 2007, 13th international conference: Vol. 4741, Providence, RI, USA. Berlin: Springer.

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
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nina Narodytska
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Toby Walsh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nina Narodytska.

Additional information

NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council. This paper is an extension of work previously published in Katsirelos et al. (5th international conference, CPAIOR 5015: 323–327, 2008).

Rights and permissions

Reprints and permissions

About this article

Cite this article

Katsirelos, G., Narodytska, N. & Walsh, T. The weighted Grammar constraint. Ann Oper Res 184, 179–207 (2011). https://doi.org/10.1007/s10479-010-0697-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-010-0697-y

Keywords

Search

Navigation