Sweep-Based Propagation for String Constraint Solving

Authors

  • Roberto Amadini University of Melbourne
  • Graeme Gange University of Melbourne
  • Peter Stuckey University of Melbourne

Keywords:

Artificial Intelligence, Constraint Programming, String Solving

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.

Downloads

Published

2018-04-26

How to Cite

Amadini, R., Gange, G., & Stuckey, P. (2018). Sweep-Based Propagation for String Constraint Solving. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/12201

Issue

Section

Main Track: Search and Constraint Satisfaction