2023/07/12 by Baudouin Le Charlier, Charlier, Baudouin Le
Computer Science · #FOS: Computer and information sciences #Natural Language Processing Techniques #Symbolic Computation (cs.SC) #Text and Document Classification Technologies #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2307.06436
openalex publication_date 2023/07/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents the main features of a system that aims to transform regular expressions into shorter equivalent expressions. The system is also capable of computing other operations useful for simplification, such as checking the inclusion of regular languages. The main novelty of this work is that it combines known but distinct ways of representing regular languages into a global unified data structure that makes the operations more efficient. In addition, representations of regular languages are dynamically reduced as operations are performed on them. Expressions are normalized and represented by a unique identifier (an integer). Expressions found to be equivalent (i.e. denoting the same regular language) are grouped into equivalence classes from which a shortest representative is chosen. The article briefly describes the main algorithms working on the global data structure. Some of them are direct adaptations of well-known algorithms, but most of them incorporate new ideas, which are really necessary to make the system efficient. Finally, to show its usefulness, the system is applied to some examples from the literature. Statistics on randomly generated sets of expressions are also provided.