Automatic generation of regular expressions for the Regex Golf challenge using a local search algorithm

Created by W.Langdon from gp-bibliography.bib Revision:1.8129

@Article{deAlmeidaFarzat:GPEM,

• author = "Andre {de Almeida Farzat} and Marcio {de Oliveira Barros}",
• title = "Automatic generation of regular expressions for the Regex Golf challenge using a local search algorithm",
• journal = "Genetic Programming and Evolvable Machines",
• year = "2022",
• volume = "23",
• number = "1",
• pages = "105--131",
• month = mar,
• keywords = "genetic algorithms, genetic programming, Regular expressions, Regex Golf, Local search, Heuristic search",
• ISSN = "1389-2576",
• URL = "https://rdcu.be/cyKF8",
• DOI = "doi:10.1007/s10710-021-09411-x",
• size = "27 pages",
• abstract = "Regular expression is a technology widely used in software development for extracting textual data, validating the structure of textual documents, or formatting data. Regex Golf is a challenge that consists in finding the smallest possible regular expression given a set of sentences to perform matches and another set not to match. An algorithm capable of meeting the Regex Golf requirements is a relevant contribution to the area of semi-structured document data extraction. we propose a heuristic search algorithm based on local search, combined with a regular expression shrinker, to find valid results for Regex Golf problems. An experimental study was conducted to compare the proposed technique with an exact algorithm and a genetic programming algorithm designed for the Regex Golf challenge. The proposed local search was shown to outperform both competing algorithms in six out of fifteen problem instances, tying in another three instances. On the other hand, all algorithms still lack the ability to outperform human software developers in designing regular expressions for the challenge.",
• notes = "Federal University of the State of Rio de Janeiro, Av. Pasteur, 458 Urca, Rio de Janeiro, RJ, 22290-240, Brazil",

}

Genetic Programming entries for Andre de Almeida Farzat Marcio de Oliveira Barros

Citations