https://deepai.org/publication/search-based-regular-expression-inference-on-a-gpu https://deepai.org/publication/search-based-regular-expressi... Here is the f

https://deepai.org/publication/search-based-regular-expression-inference-on-a-gpu https://deepai.org/publication/search-based-regular-expressi... Here is the full text. Regexps aren't even Turing complete as far as I know, if whatever they have in their paper works for arbitrary programs it would be shocking. I'll give it a read. *Edit*: The algorithm in the paper is a DP like algorithm for building regexes. They use a matrix, and it has all the potential strings to be checked on one axis, and all the potential regex programs on the other axis, and in-between values (the actual matrix values) are booleans saying whether the string matches the program. The algorithm builds the matrix iteratively. I haven't understood how regex evaluation is done, probably directly, but obviously this algorithm is only for checking whether a particular regex program matches an output rather than general purpose synthesis. We'll have to wait for AI chips to really scale genetic programming, GPUs won't cut it.