Propagating regular membership with dashed strings

Roberto Amadini, Graeme Gange, Peter J. Stuckey

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

1 Citation (Scopus)

Abstract

Using dashed strings is an approach recently introduced in Constraint Programming (CP) to represent the domain of string variables, when solving combinatorial problems with string constraints. One of the most important string constraints is that of regular membership: regular (x, R) imposes string x to be a member of the regular language defined by automaton R. The regular constraint is useful for specifying complex constraints on fixed length finite sequences, and regularly appears in CP models. Dealing with regular is also desirable in software testing and verification, because regular expressions are often used in modern programming languages for pattern matching. In this paper, we define a regular propagator for dashed string solvers. We show that this propagator, implemented in the G-Strings solver, is substantially better than the current state-of-the-art. We also demonstrate that many regular constraints appearing in string solving benchmarks can actually be tackled by dashed strings solvers without explicitly using REGULAR.

Original languageEnglish
Title of host publicationPrinciples and Practice of Constraint Programming
Subtitle of host publication24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings
EditorsJohn Hooker
Place of PublicationCham Switzerland
PublisherSpringer
Pages13-29
Number of pages17
ISBN (Electronic)9783319983349
ISBN (Print)9783319983332
DOIs
Publication statusPublished - 2018
EventInternational Conference on Principles and Practice of Constraint Programming 2018 - Lille, France
Duration: 27 Aug 201831 Aug 2018
Conference number: 24th
http://cp2018.a4cp.org/

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume11008
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceInternational Conference on Principles and Practice of Constraint Programming 2018
Abbreviated titleCP 2018
CountryFrance
CityLille
Period27/08/1831/08/18
Internet address

Cite this

Amadini, R., Gange, G., & Stuckey, P. J. (2018). Propagating regular membership with dashed strings. In J. Hooker (Ed.), Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings (pp. 13-29). (Lecture Notes in Computer Science ; Vol. 11008 ). Cham Switzerland: Springer. https://doi.org/10.1007/978-3-319-98334-9_2
Amadini, Roberto ; Gange, Graeme ; Stuckey, Peter J. / Propagating regular membership with dashed strings. Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. editor / John Hooker. Cham Switzerland : Springer, 2018. pp. 13-29 (Lecture Notes in Computer Science ).
@inproceedings{3950eb044969419cb71e96138c32fac5,
title = "Propagating regular membership with dashed strings",
abstract = "Using dashed strings is an approach recently introduced in Constraint Programming (CP) to represent the domain of string variables, when solving combinatorial problems with string constraints. One of the most important string constraints is that of regular membership: regular (x, R) imposes string x to be a member of the regular language defined by automaton R. The regular constraint is useful for specifying complex constraints on fixed length finite sequences, and regularly appears in CP models. Dealing with regular is also desirable in software testing and verification, because regular expressions are often used in modern programming languages for pattern matching. In this paper, we define a regular propagator for dashed string solvers. We show that this propagator, implemented in the G-Strings solver, is substantially better than the current state-of-the-art. We also demonstrate that many regular constraints appearing in string solving benchmarks can actually be tackled by dashed strings solvers without explicitly using REGULAR.",
author = "Roberto Amadini and Graeme Gange and Stuckey, {Peter J.}",
year = "2018",
doi = "10.1007/978-3-319-98334-9_2",
language = "English",
isbn = "9783319983332",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "13--29",
editor = "John Hooker",
booktitle = "Principles and Practice of Constraint Programming",

}

Amadini, R, Gange, G & Stuckey, PJ 2018, Propagating regular membership with dashed strings. in J Hooker (ed.), Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. Lecture Notes in Computer Science , vol. 11008 , Springer, Cham Switzerland, pp. 13-29, International Conference on Principles and Practice of Constraint Programming 2018, Lille, France, 27/08/18. https://doi.org/10.1007/978-3-319-98334-9_2

Propagating regular membership with dashed strings. / Amadini, Roberto; Gange, Graeme; Stuckey, Peter J.

Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. ed. / John Hooker. Cham Switzerland : Springer, 2018. p. 13-29 (Lecture Notes in Computer Science ; Vol. 11008 ).

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Propagating regular membership with dashed strings

AU - Amadini, Roberto

AU - Gange, Graeme

AU - Stuckey, Peter J.

PY - 2018

Y1 - 2018

N2 - Using dashed strings is an approach recently introduced in Constraint Programming (CP) to represent the domain of string variables, when solving combinatorial problems with string constraints. One of the most important string constraints is that of regular membership: regular (x, R) imposes string x to be a member of the regular language defined by automaton R. The regular constraint is useful for specifying complex constraints on fixed length finite sequences, and regularly appears in CP models. Dealing with regular is also desirable in software testing and verification, because regular expressions are often used in modern programming languages for pattern matching. In this paper, we define a regular propagator for dashed string solvers. We show that this propagator, implemented in the G-Strings solver, is substantially better than the current state-of-the-art. We also demonstrate that many regular constraints appearing in string solving benchmarks can actually be tackled by dashed strings solvers without explicitly using REGULAR.

AB - Using dashed strings is an approach recently introduced in Constraint Programming (CP) to represent the domain of string variables, when solving combinatorial problems with string constraints. One of the most important string constraints is that of regular membership: regular (x, R) imposes string x to be a member of the regular language defined by automaton R. The regular constraint is useful for specifying complex constraints on fixed length finite sequences, and regularly appears in CP models. Dealing with regular is also desirable in software testing and verification, because regular expressions are often used in modern programming languages for pattern matching. In this paper, we define a regular propagator for dashed string solvers. We show that this propagator, implemented in the G-Strings solver, is substantially better than the current state-of-the-art. We also demonstrate that many regular constraints appearing in string solving benchmarks can actually be tackled by dashed strings solvers without explicitly using REGULAR.

UR - http://www.scopus.com/inward/record.url?scp=85053110907&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-98334-9_2

DO - 10.1007/978-3-319-98334-9_2

M3 - Conference Paper

AN - SCOPUS:85053110907

SN - 9783319983332

T3 - Lecture Notes in Computer Science

SP - 13

EP - 29

BT - Principles and Practice of Constraint Programming

A2 - Hooker, John

PB - Springer

CY - Cham Switzerland

ER -

Amadini R, Gange G, Stuckey PJ. Propagating regular membership with dashed strings. In Hooker J, editor, Principles and Practice of Constraint Programming : 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings. Cham Switzerland: Springer. 2018. p. 13-29. (Lecture Notes in Computer Science ). https://doi.org/10.1007/978-3-319-98334-9_2