Minimization of symbolic automata

Symbolic Automata extend classical automata by using symbolic alphabets instead of finite ones. Most of the classical automata al-gorithms rely on the alphabet being finite, and generalizing them to the symbolic setting is not a trivial task. In this paper we study the problem of minimizing symbolic automata. We formally define and prove the basic properties of minimality in the symbolic set-ting, and lift classical minimization algorithms (Huffman-Moore’s and Hopcroft’s algorithms) to symbolic automata. We also intro-duce a completely new minimization algorithm that takes full ad-vantage of the symbolic representation of the alphabet, and prove its correctness. We provide comprehensive performance evaluation of all the algorithms over large benchmarks and against existing state-of-the-art implementations. The experiments show how the new symbolic algorithm is faster than previous implementations. 1