Ultrametric Convergence of Guarded Automata and Applications to Structural Input Validation
TL;DR
This work equips language-equivalence classes of deterministic finite automata with a distinguishing-word ultrametric and identifies the resulting space isometrically with the regular languages, and outlines a practical WAF pipeline combining learned grammar models, finite-state construction, and \(O(1)\)-memory runtime validation.
Abstract
We equip language-equivalence classes of deterministic finite automata with a distinguishing-word ultrametric and identify the resulting space isometrically with the regular languages. This space is incomplete, while its metric completion is naturally identified with the complete ultrametric space of all formal languages. Guarded language operators induce contractions on the automaton space, and their Picard iterates converge in the completion to the unique language fixed point, which is represented by a finite automaton exactly when it is regular. Motivated by structural input validation, we use this framework to construct depth-capped deterministic finite automata with certified finite-depth correctness. These automata provide efficient pre-filters for nested input structures, such as parenthesised SQL parameters, while avoiding the backtracking risks of regular-expression engines and the runtime overhead of full context-free parsers. We also outline a practical WAF pipeline combining learned grammar models, finite-state construction, and \(O(1)\)-memory runtime validation.