Abstract
We improve an existing propagator for the context-free grammar constraint and demonstrate experimentally the practicality of the resulting propagator. The underlying technique could be applied to other existing propagators for this constraint. We argue that constraint programming solvers are more suitable than existing solvers for verification tools that have to solve string constraints, as they have a rich tradition of constraints for membership in formal languages.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Axelsson, R., Heljanko, K., Lange, M.: Analyzing context-free grammars using an incremental SAT solver. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part II. LNCS, vol. 5126, pp. 410–422. Springer, Heidelberg (2008)
Beldiceanu, N., Carlsson, M., Petit, T.: Deriving filtering algorithms from constraint checkers. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 107–122. Springer, Heidelberg (2004)
Bessière, C.: Arc-consistency and arc-consistency again. Artificial Intelligence 65(1), 179–190 (1994)
Demassey, S., Pesant, G., Rousseau, L.-M.: A cost-regular based hybrid column generation approach. Constraints 11(4), 315–333 (2006)
Fu, X., Powell, M.C., Bantegui, M., Li, C.-C.: Simple linear string constraints. Formal Aspects of Computing (2012), Published on-line in January 2012 and available from http://dx.doi.org/10.1007/s00165-011-0214-3 . Sushi is available from http://people.hofstra.edu/Xiang_Fu/XiangFu/projects/SAFELI/SUSHI.php
Ganesh, V., Dill, D.L.: A decision procedure for bit-vectors and arrays. In: Damm, W., Hermanns, H. (eds.) CAV 2007. LNCS, vol. 4590, pp. 519–531. Springer, Heidelberg (2007), STP is available from https://sites.google.com/site/stpfastprover/
Gange, G., Stuckey, P.J.: Explaining propagators for s-DNNF circuits. In: Beldiceanu, N., Jussien, N., Pinson, É. (eds.) CPAIOR 2012. LNCS, vol. 7298, pp. 195–210. Springer, Heidelberg (2012)
Gecode Team. Gecode: A generic constraint development environment (2006), http://www.gecode.org/
He, J.: Constraints for Membership in Formal Languages under Systematic Search and Stochastic Local Search. PhD thesis, Uppsala University, Sweden (2013), http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-196347
Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison Wesley, New York (1979)
Kadioğlu, S., Sellmann, M.: Grammar constraints. Constraints 15(1), 117–144 (2008); An early version is published in the Proceedings of the 23rd AAAI Conference on Artificial Intelligence in 2008
Katsirelos, G., Narodytska, N., Walsh, T.: Reformulating global grammar constraints. In: van Hoeve, W.-J., Hooker, J.N. (eds.) CPAIOR 2009. LNCS, vol. 5547, pp. 132–147. Springer, Heidelberg (2009)
Katsirelos, G., Narodytska, N., Walsh, T.: The weighted Grammar constraint. Annals of Operations Research 184(1), 179–207 (2011), An early version is published in the Proceedings of the 5th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems in 2008
Kieżun, A., Ganesh, V., Guo, P.J., Hooimeijer, P., Ernst, M.D.: HAMPI: A solver for string constraints. In: Proceedings of the 18th International Symposium on Software Testing and Analysis, Chicago, USA, July 2009, pp. 105–116. ACM Press (2009), Hampi is available from http://people.csail.mit.edu/akiezun/hampi/
Mohr, R., Henderson, T.C.: Arc and path consistency revisited. Artificial Intelligence 28(2), 225–233 (1986)
Pesant, G.: A regular language membership constraint for finite sequences of variables. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 482–495. Springer, Heidelberg (2004)
Quimper, C.-G., Walsh, T.: Global grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 751–755. Springer, Heidelberg (2006)
Quimper, C.-G., Walsh, T.: Decomposing global grammar constraints. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 590–604. Springer, Heidelberg (2007)
Saxena, P., Akhawe, D., Hanna, S., Mao, F., McCamant, S., Song, D.: A symbolic execution framework for javascript. In: Proceedings of the 31st IEEE Symposium on Security and Privacy, California, USA, pp. 513–528. IEEE Press (May 2010), Kaluza is available from http://webblaze.cs.berkeley.edu/2010/kaluza/
Sellmann, M.: The theory of grammar constraints. In: Benhamou, F. (ed.) CP 2006. LNCS, vol. 4204, pp. 530–544. Springer, Heidelberg (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
He, J., Flener, P., Pearson, J., Zhang, W.M. (2013). Solving String Constraints: The Case for Constraint Programming. In: Schulte, C. (eds) Principles and Practice of Constraint Programming. CP 2013. Lecture Notes in Computer Science, vol 8124. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40627-0_31
Download citation
DOI: https://doi.org/10.1007/978-3-642-40627-0_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40626-3
Online ISBN: 978-3-642-40627-0
eBook Packages: Computer ScienceComputer Science (R0)