@inproceedings{4583e02e01e34e7bab492c1c9dc353f8,
title = "Efficient Enumeration of Regular Expressions for Faster Regular Expression Synthesis",
abstract = "We study the problem of synthesizing regular expressions from a set of positive and negative strings. The previous synthesis algorithm proposed by Lee et al. [12] relies on the best-first enumeration of regular expressions. To improve the performance of the enumeration process, we define a new normal form of regular expressions called the concise normal form which allows us to significantly reduce the search space by pruning those not in the normal form while still capturing the whole class of regular languages. We conduct experiments with two benchmark datasets and demonstrate that our synthesis algorithm based on the proposed normal form outperforms the previous algorithm in terms of runtime complexity and scalability.",
keywords = "Enumerative search, Normal form, Program synthesis, Regular expression",
author = "Kim, {Su Hyeon} and Hyeonseung Im and Ko, {Sang Ki}",
note = "Publisher Copyright: {\textcopyright} 2021, Springer Nature Switzerland AG.; 25th International Conference on Implementation and Application of Automata, CIAA 2021 ; Conference date: 19-07-2021 Through 22-07-2021",
year = "2021",
doi = "10.1007/978-3-030-79121-6_6",
language = "English",
isbn = "9783030791209",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Science and Business Media Deutschland GmbH",
pages = "65--76",
editor = "Sebastian Maneth",
booktitle = "Implementation and Application of Automata - 25th International Conference, CIAA 2021, Proceedings",
address = "Germany",
}