Sweep-Based Propagation for String Constraint Solving

Roberto Amadini, Graeme Gange, Peter J. Stuckey

AAAI 2018 pp. 6557-6564

doi:10.1609/AAAI.V32I1.12201 /aaai/2018/amadini2018aaai-sweep/

Abstract

Solving constraints over strings is an emerging important field. Recently, a Constraint Programming approach based on dashed strings has been proposed to enable a compact domain representation for potentially large bounded-length string variables. In this paper, we present a more efficient algorithm for propagating equality (and related constraints) over dashed strings. We call this propagation sweep-based. Experimental evidences show that sweep-based propagation is able to significantly outperform state-of-the-art approaches for string constraint solving.

PDF AAAI Semantic Scholar

Cite

Text

Amadini et al. "Sweep-Based Propagation for String Constraint Solving." AAAI Conference on Artificial Intelligence, 2018. doi:10.1609/AAAI.V32I1.12201

Markdown

[Amadini et al. "Sweep-Based Propagation for String Constraint Solving." AAAI Conference on Artificial Intelligence, 2018.](https://mlanthology.org/aaai/2018/amadini2018aaai-sweep/) doi:10.1609/AAAI.V32I1.12201

BibTeX

@inproceedings{amadini2018aaai-sweep,
  title     = {{Sweep-Based Propagation for String Constraint Solving}},
  author    = {Amadini, Roberto and Gange, Graeme and Stuckey, Peter J.},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2018},
  pages     = {6557-6564},
  doi       = {10.1609/AAAI.V32I1.12201},
  url       = {https://mlanthology.org/aaai/2018/amadini2018aaai-sweep/}
}