Heuristic Universality Detection over Regular Expressions Specified by Systems
摘要
In this article, we provide a computational approach for evaluating the expressivity of systems of equations for generating random regular expressions. More concretely, we obtain bounds on the proportion of universal expressions these systems produce. These bounds rely on the heuristic proposed by Koechlin et al., 2021, extended here to more general systems of several equations, which are harder to analyze. We have developed a tool that enables one to automatically test many of them. We discuss the results obtained for several systems from the literature.