Monte Carlo Tree Search for Deterministic Finite Automaton Inference

Abstract

Inferring a minimal Deterministic Finite Automaton (DFA) from a set of labelled traces is an NP-complete problem, making heuristic search strategies necessary. The red-blue framework addresses this inference process by sequentially applying merge and extend refinements to a prefix tree acceptor, with the ordering of these refinements determining the compactness of the final automaton. This paper investigates the use of Monte Carlo Tree Search (MCTS) as a heuristic for finding higher-quality refinement orderings. The problem is first formalised as a Markov Decision Process, enabling MCTS to serve as a solver. We evaluate four action-selection policies and two reward metrics across several datasets from the StaMiNa competition. Results show that the uniform-merge-first, weighted-merge-first and weighted-minimal policies outperform the uniform policy, although none of these policies dominates the others. The weighted-minimal sub-policy produces a more compact automaton than the weighted-average sub-policy, confirming that favouring merge over extend refinements during simulation is beneficial. Two reward metrics are compared: the final simulated DFA size and the number of rollout steps. Both perform similarly overall; however, the rollout steps metric has the structural advantage of being immune to reward stagnation, since the reward improves monotonically as the search tree grows. Correlation analysis further reveals that the EDSM scoring function provides no directional signal towards smaller DFAs.