Design and implementation of bounded-length sequence variables. (English) Zbl 06756575

Salvagnin, Domenico (ed.) et al., Integration of AI and OR techniques in constraint programming. 14th international conference, CPAIOR 2017, Padua, Italy, June 5–8, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10335, 51-67 (2017).
Summary: We present the design and implementation of bounded length sequence (BLS) variables for a CP solver. The domain of a BLS variable is represented as the combination of a set of candidate lengths and a sequence of sets of candidate characters. We show how this representation, together with requirements imposed by propagators, affects the implementation of BLS variables for a copying CP solver, most importantly the closely related decisions of data structure, domain restriction operations, and propagation events. The resulting implementation outperforms traditional bounded-length string representations for CP solvers, which use a fixed-length array of candidate characters and a padding symbol.
For the entire collection see [Zbl 1364.68017].


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Full Text: DOI Link


[1] Abdulla, P.A., Atig, M.F., Chen, Y.-F., Holík, L., Rezine, A., Rümmer, P., Stenman, J.: Norn: an SMT solver for string constraints. In: Kroening, D., Păsăreanu, C.S. (eds.) CAV 2015. LNCS, vol. 9206, pp. 462–469. Springer, Cham (2015). doi: 10.1007/978-3-319-21690-4_29
. http://user.it.uu.se/ jarst116/norn · Zbl 06845676
[2] Amadini, R., Flener, P., Pearson, J., Scott, J.D., Stuckey, P.J., Tack, G.: MiniZinc with strings. In: Hermenegildo, M., López-García, P. (eds.) LOPSTR 2016. LNCS, vol. 10184, pp. 52–67 (2016). Post-proceedings, Pre-proceedings Version at Computing Research Repository. https://arxiv.org/abs/1608.03650
[3] Bisht, P., Hinrichs, T., Skrupsky, N., Venkatakrishnan, V.N.: WAPTEC: whitebox analysis of web applications for parameter tampering exploit construction. In: Chen, Y., Danezis, G., Shmatikov, V. (eds.) Computer and Communications Security (CCS 2011), pp. 575–586. ACM (2011)
[4] Bjørner, N., Tillmann, N., Voronkov, A.: Path feasibility analysis for string-manipulating programs. In: Kowalewski, S., Philippou, A. (eds.) TACAS 2009. LNCS, vol. 5505, pp. 307–321. Springer, Heidelberg (2009). doi: 10.1007/978-3-642-00768-2_27 · Zbl 1234.68070
[5] Demeulenaere, J., Hartert, R., Lecoutre, C., Perez, G., Perron, L., Régin, J.-C., Schaus, P.: Compact-table: efficiently filtering table constraints with reversible sparse bit-sets. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 207–223. Springer, Cham (2016). doi: 10.1007/978-3-319-44953-1_14
[6] van Dongen, M.: CSPLib problem 033: word design for DNA computing on surfaces. http://www.csplib.org/Problems/prob033
[7] Emmi, M., Majumdar, R., Sen, K.: Dynamic test input generation for database applications. In: Rosenblum, D.S., Elbaum, S.G. (eds.) Software Testing and Analysis (ISSTA 2007), pp. 151–162. ACM (2007)
[8] Fu, X., Powell, M.C., Bantegui, M., Li, C.C.: Simple linear string constraints. Formal Aspects Comput. 25, 847–891 (2013) · Zbl 1298.68172
[9] Ganesh, V., Kie\.zun, A., Artzi, S., Guo, P.J., Hooimeijer, P., Ernst, M.: HAMPI: a string solver for testing, analysis and vulnerability detection. In: Gopalakrishnan, G., Qadeer, S. (eds.) CAV 2011. LNCS, vol. 6806, pp. 1–19. Springer, Heidelberg (2011). doi: 10.1007/978-3-642-22110-1_1 · Zbl 05940699
[10] Gange, G., Navas, J.A., Stuckey, P.J., Søndergaard, H., Schachte, P.: Unbounded model-checking with interpolation for regular language constraints. In: Piterman, N., Smolka, S.A. (eds.) TACAS 2013. LNCS, vol. 7795, pp. 277–291. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-36742-7_20 · Zbl 1381.68162
[11] Golden, K., Pang, W.: A constraint-based planner applied to data processing domains. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, p. 815. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-30201-8_93
[12] He, J., Flener, P., Pearson, J., Zhang, W.M.: Solving string constraints: the case for constraint programming. In: Schulte, C. (ed.) CP 2013. LNCS, vol. 8124, pp. 381–397. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-40627-0_31 · Zbl 06294290
[13] Hopcroft, J., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison Wesley, Redwood City (2007) · Zbl 0980.68066
[14] Liang, T., Reynolds, A., Tinelli, C., Barrett, C., Deters, M.: A DPLL(T) theory solver for a theory of strings and regular expressions. In: Biere, A., Bloem, R. (eds.) CAV 2014. LNCS, vol. 8559, pp. 646–662. Springer, Cham (2014). doi: 10.1007/978-3-319-08867-9_43 · Zbl 06349539
[15] Monette, J.-N., Flener, P., Pearson, J.: Towards solver-independent propagators. In: Milano, M. (ed.) CP 2012. LNCS, pp. 544–560. Springer, Heidelberg (2012). doi: 10.1007/978-3-642-33558-7_40
. http://www.it.uu.se/research/group/astra/software#indexicals · Zbl 06122863
[16] Negrevergne, B., Guns, T.: Constraint-based sequence mining using constraint programming. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 288–305. Springer, Cham (2015). doi: 10.1007/978-3-319-18008-3_20 · Zbl 1427.68068
[17] Nethercote, N., Stuckey, P.J., Becket, R., Brand, S., Duck, G.J., Tack, G.: MiniZinc: towards a standard CP modelling language. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 529–543. Springer, Heidelberg (2007). doi: 10.1007/978-3-540-74970-7_38
. http://www.minizinc.org · Zbl 05318838
[18] Saxena, P., Akhawe, D., Hanna, S., Mao, F., McCamant, S., Song, D.: A symbolic execution framework for JavaScript. In: Security and Privacy (S&P 2010), pp. 513–528. IEEE Computer Society (2010)
[19] Schulte, C., Carlsson, M.: Finite domain constraint programming systems. In: Rossi, F., van Beek, P., Walsh, T. (eds.) Handbook of Constraint Programming, pp. 495–526. Elsevier, Amsterdam (2006). Chap. 14
[20] Schulte, C., Stuckey, P.J.: Efficient constraint propagation engines. Trans. Program. Lang. Syst. 31(1), 2:1–2:43 (2008)
[21] Schulte, C., Tack, G.: Implementing efficient propagation control. In: Proceedings of TRICS: Techniques for Implementing Constraint programming Systems, a Conference Workshop of CP 2010, St Andrews, UK (2010)
[22] Scott, J.: Other things besides number: abstraction, constraint propagation, and string variable types. Ph.D. thesis, Uppsala University, Sweden (2016). http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-273311
[23] Scott, J.D., Flener, P., Pearson, J.: Constraint solving on bounded string variables. In: Michel, L. (ed.) CPAIOR 2015. LNCS, vol. 9075, pp. 375–392. Springer, Cham (2015). doi: 10.1007/978-3-319-18008-3_26 · Zbl 1459.68194
[24] Tack, G.: Constraint propagation: models, techniques, implementation. Ph.D. thesis, Saarland University, Germany (2009)
[25] The Gecode Team: Gecode: a generic constraint development environment (2006). http://www.gecode.org
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.