Projects per year
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 language | English |
---|---|
Title of host publication | Principles and Practice of Constraint Programming |
Subtitle of host publication | 24th International Conference, CP 2018 Lille, France, August 27–31, 2018 Proceedings |
Editors | John Hooker |
Place of Publication | Cham Switzerland |
Publisher | Springer |
Pages | 13-29 |
Number of pages | 17 |
ISBN (Electronic) | 9783319983349 |
ISBN (Print) | 9783319983332 |
DOIs | |
Publication status | Published - 2018 |
Event | International Conference on Principles and Practice of Constraint Programming 2018 - Lille, France Duration: 27 Aug 2018 → 31 Aug 2018 Conference number: 24th http://cp2018.a4cp.org/ |
Publication series
Name | Lecture Notes in Computer Science |
---|---|
Publisher | Springer |
Volume | 11008 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | International Conference on Principles and Practice of Constraint Programming 2018 |
---|---|
Abbreviated title | CP 2018 |
Country/Territory | France |
City | Lille |
Period | 27/08/18 → 31/08/18 |
Internet address |
Projects
- 1 Finished
-
Towards reliability in combinatorial optimisation
Gange, G. (Primary Chief Investigator (PCI))
1/04/16 → 3/12/21
Project: Research