A regular matching constraint for string variables

Roberto Amadini; Peter J. Stuckey

doi:10.24963/ijcai.2023/207

A regular matching constraint for string variables

Roberto Amadini
, Peter J. Stuckey

Department of Data Science & AI

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

1 Citation (Scopus)

Abstract

Using a regular language as a pattern for string matching is nowadays a common-and sometimes unsafe-operation, provided as a built-in feature by most programming languages. A proper constraint solver over string variables should support most of the operations over regular expressions and related constructs. However, state-of-the-art string solvers natively support only the membership relation of a string variable to a regular language. Here we take a step forward by defining a specialised propagator for the match operation, returning the leftmost position where a pattern can match a given string. Empirical evidences show the effectiveness of our approach, implemented within the constraint programming framework, and tested against state-of-the-art string solvers.

Original language	English
Title of host publication	Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence
Editors	Edith Elkind
Place of Publication	Marina del Rey CA USA
Publisher	Association for the Advancement of Artificial Intelligence (AAAI)
Pages	1868-1875
Number of pages	8
ISBN (Electronic)	9781956792034
DOIs	https://doi.org/10.24963/ijcai.2023/207
Publication status	Published - 2023
Event	International Joint Conference on Artificial Intelligence 2023 - Macao, China Duration: 19 Aug 2023 → 25 Aug 2023 Conference number: 32nd https://www.ijcai.org/proceedings/2023/ (Proceedings) https://ijcai-23.org/ (Website)

Conference

Conference	International Joint Conference on Artificial Intelligence 2023
Abbreviated title	IJCAI 2023
Country/Territory	China
City	Macao
Period	19/08/23 → 25/08/23
Internet address	https://www.ijcai.org/proceedings/2023/ (Proceedings) https://ijcai-23.org/ (Website)

Keywords

Constraint Satisfaction and Optimization
CSO
Constraint programming
Constraint optimization
Constraint satisfaction

Access to Document

10.24963/ijcai.2023/207

521471275-oaFinal published version, 280 KB

Cite this

@inproceedings{6a81f7841ffe44baaa258dabbdf18cef,

title = "A regular matching constraint for string variables",

abstract = "Using a regular language as a pattern for string matching is nowadays a common-and sometimes unsafe-operation, provided as a built-in feature by most programming languages. A proper constraint solver over string variables should support most of the operations over regular expressions and related constructs. However, state-of-the-art string solvers natively support only the membership relation of a string variable to a regular language. Here we take a step forward by defining a specialised propagator for the match operation, returning the leftmost position where a pattern can match a given string. Empirical evidences show the effectiveness of our approach, implemented within the constraint programming framework, and tested against state-of-the-art string solvers.",

keywords = "Constraint Satisfaction and Optimization, CSO, Constraint programming, Constraint optimization, Constraint satisfaction",

author = "Roberto Amadini and Stuckey, \{Peter J.\}",

note = "Funding Information: Research partly funded by PNRR - M4C2 - Investimento 1.3, Partenariato Esteso PE00000013 - “FAIR - Future Artificial Intelligence Research” - Spoke 1 “Human-centered AI”, funded by the European Commission under the NextGeneration EU programme. This research was partially funded by the Australian Government through the Australian Research Council Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Project ID IC200100009. Funding Information: Research partly funded by PNRR - M4C2 - Investimento 1.3, Partenariato Esteso PE00000013 - “FAIR – Future Artificial Intelligence Research” - Spoke 1 “Human-centered AI”, funded by the European Commission under the NextGenera-tion EU programme. This research was partially funded by the Australian Government through the Australian Research Council Industrial Transformation Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Project ID IC200100009. Publisher Copyright: {\textcopyright} 2023 International Joint Conferences on Artificial Intelligence. All rights reserved.; International Joint Conference on Artificial Intelligence 2023, IJCAI 2023 ; Conference date: 19-08-2023 Through 25-08-2023",

year = "2023",

doi = "10.24963/ijcai.2023/207",

language = "English",

pages = "1868--1875",

editor = "Edith Elkind",

booktitle = "Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence (AAAI)",

address = "United States of America",

url = "https://www.ijcai.org/proceedings/2023/, https://ijcai-23.org/",

}

Amadini, R & Stuckey, PJ 2023, A regular matching constraint for string variables. in E Elkind (ed.), Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. Association for the Advancement of Artificial Intelligence (AAAI), Marina del Rey CA USA, pp. 1868-1875, International Joint Conference on Artificial Intelligence 2023, Macao, China, 19/08/23. https://doi.org/10.24963/ijcai.2023/207

A regular matching constraint for string variables. / Amadini, Roberto; Stuckey, Peter J.
Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. ed. / Edith Elkind. Marina del Rey CA USA: Association for the Advancement of Artificial Intelligence (AAAI), 2023. p. 1868-1875.

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A regular matching constraint for string variables

AU - Amadini, Roberto

AU - Stuckey, Peter J.

N1 - Conference code: 32nd

PY - 2023

Y1 - 2023

N2 - Using a regular language as a pattern for string matching is nowadays a common-and sometimes unsafe-operation, provided as a built-in feature by most programming languages. A proper constraint solver over string variables should support most of the operations over regular expressions and related constructs. However, state-of-the-art string solvers natively support only the membership relation of a string variable to a regular language. Here we take a step forward by defining a specialised propagator for the match operation, returning the leftmost position where a pattern can match a given string. Empirical evidences show the effectiveness of our approach, implemented within the constraint programming framework, and tested against state-of-the-art string solvers.

AB - Using a regular language as a pattern for string matching is nowadays a common-and sometimes unsafe-operation, provided as a built-in feature by most programming languages. A proper constraint solver over string variables should support most of the operations over regular expressions and related constructs. However, state-of-the-art string solvers natively support only the membership relation of a string variable to a regular language. Here we take a step forward by defining a specialised propagator for the match operation, returning the leftmost position where a pattern can match a given string. Empirical evidences show the effectiveness of our approach, implemented within the constraint programming framework, and tested against state-of-the-art string solvers.

KW - Constraint Satisfaction and Optimization

KW - CSO

KW - Constraint programming

KW - Constraint optimization

KW - Constraint satisfaction

UR - https://www.scopus.com/pages/publications/85170362610

U2 - 10.24963/ijcai.2023/207

DO - 10.24963/ijcai.2023/207

M3 - Conference Paper

AN - SCOPUS:85170362610

SP - 1868

EP - 1875

BT - Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence

A2 - Elkind, Edith

PB - Association for the Advancement of Artificial Intelligence (AAAI)

CY - Marina del Rey CA USA

T2 - International Joint Conference on Artificial Intelligence 2023

Y2 - 19 August 2023 through 25 August 2023

ER -

A regular matching constraint for string variables

Abstract

Conference

Keywords

Access to Document

Other files and links

ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)

Cite this

A regular matching constraint for string variables

Abstract

Conference

Keywords

Access to Document

Other files and links

Projects

ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA)

Cite this