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.

Keywords: deterministic finite automata; formal languages; guarded language operators; ultrametric spaces; fixed points; Picard iteration; regular languages; structural input validation; Web Application Firewalls

2020 Mathematics Subject Classification: 68Q45; 47H10; 54E50; 68Q60; 68R15

1 Introduction↩︎

Metric and topological methods provide a natural framework for comparing formal languages through the finite words on which they agree or differ. The corresponding length-based ultrametric and Cantor-type topology were studied in the early literature on language spaces [1], [2]. Related metric and fixed-point methods have also been used in the semantics of recursive definitions and domain equations [3], [4], while shortest-distinguishing-input distances appear naturally in quantitative approaches to automata and regular expressions [5], [6].

In recent work, guarded language operators \(T_{S,G}(L)=S\cup\bigcup_{r=1}^{p}u_rLv_r\) were shown to be contractions on the complete length-based ultrametric space of formal languages whenever every recursive occurrence is protected by a guard of positive length [7]. This yields a unique fixed point, quantitative Picard convergence, and finite-depth stabilization. The framework was subsequently extended to positive–negative guarded systems involving both direct and complemented language dependencies [8].

The present paper develops the corresponding automata-theoretic framework. We equip language-equivalence classes of deterministic finite automata with the distinguishing-word ultrametric and identify this space isometrically with the regular languages. We prove that it is dense but not complete and that its metric completion is naturally the complete space of all formal languages. Guarded operators with regular seeds induce contractions on the automaton quotient space, and their Picard iterates form Cauchy sequences converging in the completion to the unique language fixed point.

A fixed point exists inside the automaton space precisely when the limiting language is regular. If the fixed point is nonregular, every finite Picard iterate is nevertheless represented by a deterministic finite automaton and agrees with the limiting language up to an explicitly certified word length. We also consider systems of guarded operators, two-sided approximation, sound iteration from below, state-complexity estimates, and depth-capped finite-state approximations required for the validation application developed later in the paper.

The reliable validation of structured input data remains a fundamental challenge in cybersecurity, particularly in the prevention of injection attacks such as SQL injection (SQLi). Modern industrial systems typically employ Web Application Firewalls (WAFs) as a first line of defense, or analyze network flow data to detect SQLi payloads [9]. However, the underlying mechanisms of these filters present a difficult trade-off between expressiveness, performance, and security. Currently, the industry relies on two primary approaches:

Regex-based Heuristics: Most WAFs utilise Perl-Compatible Regular Expressions (PCRE) to detect malicious payloads. While expressive, PCRE engines employ backtracking algorithms to simulate stack-like memory. This makes them highly susceptible to Regular Expression Denial of Service (ReDoS) attacks [10], [11], where an attacker crafts a specific payload (e.g., asymmetric nested brackets) that forces the engine into exponential evaluation time. Furthermore, standard regular expressions are mathematically incapable of accurately parsing arbitrarily nested structures.
Full Context-Free Grammar (CFG) Parsers: To address the shortcomings of Regex, some advanced systems attempt to parse the entire input using Pushdown Automata (PDA) or abstract syntax trees (ASTs), such as through parse tree validation [12] or runtime monitoring against grammar models [13]. While structurally accurate, CFG parsers require dynamic memory allocation (stack management) at runtime, leading to \(O(N)\) spatial complexity and significant latency bottlenecks, rendering them unsuitable for high-throughput environments where read-heavy operations dominate.

Motivation and Approach. This paper bridges the gap between these two extremes. Our goal is to achieve the structural awareness of a CFG parser while maintaining the strict \(O(N)\) execution time and \(O(1)\) memory footprint of a strictly Deterministic Finite Automaton (DFA). To achieve this, we shift the computational burden from runtime to compile-time. We model nested structures using "guarded language operators" and analyze them as contractions within a complete ultrametric space of formal languages. By deliberately capping the nesting depth (a pragmatic choice, as legitimate application parameters rarely exceed 3 or 4 levels of nesting), we formally guarantee that the context-free language degenerates into a regular language. This concept shares similar motivations with the regular approximation of context-free languages through transformations [14]. This allows us to pre-compute a minimal DFA that acts as an ultra-fast, ReDoS-immune pre-filter, guaranteeing the rejection of overly complex or malicious payloads without ever relying on runtime backtracking.

The remainder of the paper is organised as follows. Section 2 collects the necessary preliminaries on formal languages, the length-based ultrametric, deterministic finite automata, and guarded language operators. Section 3 presents the principal theoretical results for automata. Section 3.1 introduces the distinguishing-word ultrametric on language-equivalence classes of deterministic finite automata, identifies this space isometrically with the regular languages, determines its metric completion, and proves the contraction, Cauchy convergence, fixed-point, regularity, and finite-depth certification results. Section 3.2 illustrates the theory through regular and nonregular fixed-point examples and gives concrete witnesses for the incompleteness of the automaton space. Section 4 develops generalisations and extensions of the guarded framework, including higher language powers, special seed languages, finite systems of guarded operators, two-sided Picard approximation, soundness of iteration from below, state-complexity estimates, and depth-capped approximations. Section 5 applies the theoretical results to the construction of a fixed-point-based structural pre-filter for SQL parameter validation and describes the corresponding DFA construction and deployment pipeline. Finally, Section 6 discusses the theoretical and practical limitations of the framework and outlines directions for further research.

2 Preliminaries↩︎

Throughout the paper, \(\Sigma\) denotes a fixed finite nonempty alphabet, and \(\Sigma^\ast\) denotes the set of all finite words over \(\Sigma\), including the empty word \(\varepsilon\). For a word \(w\in\Sigma^\ast\), its length is denoted by \(|w|\). We write \(\mathcal{L}=\mathcal{P}(\Sigma^\ast)\) for the set of all formal languages over \(\Sigma\). If \(L\subseteq\Sigma^\ast\), its characteristic function is denoted by \(\mathbf{1}_L\).

A formal language over \(\Sigma\) is any subset of \(\Sigma^\ast\). For \(u,v\in\Sigma^\ast\) and \(L\subseteq\Sigma^\ast\), we use the notation \[uLv=\{\,uwv:w\in L\,\}.\]

Definition 1 ([15], [16]). Each language \(L\in\mathcal{L}\) is identified with its characteristic function \[\mathbf{1}_L:\Sigma^\ast\to\{0,1\},\qquad \mathbf{1}_L(w)= \begin{cases} 1,&w\in L,\\ 0,&w\notin L. \end{cases}\]

We recall the length-based ultrametric on the space of all formal languages.

Definition 2 ([1], [2]). For \(L,M\in\mathcal{L}\), define \[d(L,M)= \begin{cases} 0, & L=M,\\[2mm] 2^{-n}, & n=\min\{\,|w|:\mathbf{1}_L(w)\neq\mathbf{1}_M(w)\,\}. \end{cases}\]

If \(L\neq M\), then there exists at least one word \(w\in\Sigma^\ast\) such that \(\mathbf{1}_L(w)\neq\mathbf{1}_M(w)\), so the minimum in Definition 2 is taken over a nonempty subset of \(\mathbb{N}\cup\{0\}\); in particular the formula \(2^{-n}\) is well defined. The two-case structure of the definition is exhaustive: the case \(L=M\) assigns distance zero, and the case \(L\neq M\) assigns \(2^{-n}\) where \(n\) is the length of the shortest distinguishing word. Thus \(d(L,M)\) is defined for all pairs \((L,M)\in\mathcal{L}\times\mathcal{L}\). The distance \(d(L,M)\) is determined by the shortest word on which the two languages differ. In particular, two languages are close when they agree on all words up to a large length.

Definition 3 ([17]). Let \(X\) be a nonempty set. A function \(\rho:X\times X\to[0,\infty)\) is called an ultrametric on \(X\) if, for all \(x,y,z\in X\), the following conditions hold: \(\rho(x,y)=0\) if and only if \(x=y\); \(\rho(x,y)=\rho(y,x)\); and \(\rho(x,z)\le \max\{\rho(x,y),\rho(y,z)\}\). A pair \((X,\rho)\), where \(\rho\) is an ultrametric on \(X\), is called an ultrametric space.

Theorem 4. [1], [2]The function \(d\) is an ultrametric on \(\mathcal{L}\).

Theorem 5 ([1], [2]). The ultrametric space \((\mathcal{L},d)\) is complete.

Remark 6. The completeness of \((\mathcal{L},d)\) can be justified by identifying \(\mathcal{L}=\mathcal{P}(\Sigma^\ast)\) with \(2^{\Sigma^\ast}\) via characteristic functions. The metric/topological structure of language spaces of this type goes back to the Bodnarchuk metric space introduced by Bodnarchuk [18] and discussed by Vianu [1]. More generally, complete metric spaces are a standard tool in computer science for solving domain equations in programming semantics [4]. Fulop and Kephart [2] later describe the corresponding Cantor language topology and recall that it is homeomorphic to the Cantor space; in particular, the language space is compact. Since every compact metric space is complete, this provides a standard justification for the completeness of \((\mathcal{L},d)\).

We also recall Banach’s fixed-point theorem.

Theorem 7 ([19]). Let \((X,\rho)\) be a complete metric space and let \(T:X\to X\) be a contraction; that is, there exists \(q\in(0,1)\) such that \[\rho(Tx,Ty)\le q\rho(x,y) \qquad\text{for all }x,y\in X.\] Then \(T\) has a unique fixed point \(x^\ast\in X\). Moreover, for every \(x_0\in X\), the Picard iteration \(x_{n+1}=Tx_n\) converges to \(x^\ast\).

For extensions of this fixed-point principle to generalized metric spaces or partially ordered settings, we refer the reader to [20].

We now recall the deterministic finite automata used in the sequel.

Definition 8. [21] A deterministic finite automaton, or DFA, over \(\Sigma\) is a tuple \[\mathcal{A}=(Q,\Sigma,\delta,q_0,F),\] where \(Q\) is a finite nonempty set of states, \(\delta:Q\times\Sigma\to Q\) is a total transition function, \(q_0\in Q\) is the initial state, and \(F\subseteq Q\) is the set of accepting states. The transition function is extended to \(\delta:Q\times\Sigma^\ast\to Q\) in the usual way by \[\delta(q,\varepsilon)=q, \qquad \delta(q,wa)=\delta(\delta(q,w),a)\] for all \(q\in Q\), \(w\in\Sigma^\ast\), and \(a\in\Sigma\).

Definition 9. [21] The language recognized by a DFA \(\mathcal{A}=(Q,\Sigma,\delta,q_0,F)\) is \[L(\mathcal{A})=\{\,w\in\Sigma^\ast:\delta(q_0,w)\in F\,\}.\] A language \(L\subseteq\Sigma^\ast\) is called regular if there exists a DFA \(\mathcal{A}\) such that \(L=L(\mathcal{A})\).

We shall use the standard fact that regular languages are closed under finite union and under concatenation with fixed words; see, for example, [21]. In particular, if \(L\) is regular and \(u,v\in\Sigma^\ast\), then \(uLv\) is regular.

Since distinct deterministic finite automata may recognize the same language, we work with automata up to language equivalence. The standard notion of equivalence of automata is based on equality of the languages they recognize; see, for example, [21]. We now introduce the corresponding quotient space of deterministic finite automata.

Definition 10. Two DFAs \(\mathcal{A}\) and \(\mathcal{B}\) over \(\Sigma\) are called language equivalent if \(L(\mathcal{A})=L(\mathcal{B})\). We denote by \(\mathfrak{A}_\Sigma\) the set of equivalence classes of DFAs over \(\Sigma\) under language equivalence, and we write \([\mathcal{A}]\) for the equivalence class of an automaton \(\mathcal{A}\).

For \([\mathcal{A}]\in\mathfrak{A}_\Sigma\), we write \(L([\mathcal{A}]):=L(\mathcal{A})\). This notation is well defined, since all representatives of the same equivalence class recognize the same language.

We finally recall the class of guarded language operators introduced in [7].

Definition 11. [7] Let \(S\subseteq\Sigma^\ast\), let \(p\ge 1\), and let \[G=\{(u_r,v_r):r=1,\dots,p\}\subseteq\Sigma^\ast\times\Sigma^\ast\] be a finite nonempty family of guards. The corresponding guarded language operator is the map \(T_{S,G}:\mathcal{L}\to\mathcal{L}\) defined by \[T_{S,G}(L)=S\cup\bigcup_{r=1}^p u_rLv_r.\] The family \(G\) is said to have guard length at least \(m\ge 1\) if \[\min_{1\le r\le p}(|u_r|+|v_r|)\ge m.\]

The following result is the main fixed-point theorem for guarded language operators from [7]. It will be used as the language-level foundation for the automaton results proved in the present paper.

Theorem 12. [7]Let \(S\subseteq\Sigma^\ast\), and let \(G=\{(u_r,v_r):r=1,\dots,p\}\subseteq\Sigma^\ast\times\Sigma^\ast\) be a finite nonempty family of guards with guard length at least \(m\ge 1\). Then the operator \(T_{S,G}:\mathcal{L}\to\mathcal{L}\) is a contraction on \((\mathcal{L},d)\) with contraction factor \(2^{-m}\). Consequently, \(T_{S,G}\) has a unique fixed point \(L^\ast\in\mathcal{L}\), and for every initial language \(L^{(0)}\in\mathcal{L}\), the Picard iteration \[L^{(n+1)}=T_{S,G}(L^{(n)})\] converges to \(L^\ast\). Moreover, \[d(L^{(n)},L^\ast)\le 2^{-mn}d(L^{(0)},L^\ast) \qquad\text{for all }n\ge 0.\]

Remark 13. A potential concern is whether the empty word \(\varepsilon\) could distinguish \(T_{S,G}(L)\) from \(T_{S,G}(M)\) and thereby break the contraction estimate. This cannot occur: \(\varepsilon\in T_{S,G}(L)\) if and only if \(\varepsilon\in S\) or \(\varepsilon\in u_r L v_r\) for some \(r\), the latter requiring \(u_r=v_r=\varepsilon\) and \(\varepsilon\in L\). Since all guards have length \(|u_r|+|v_r|\ge m\ge 1\), the condition \(u_r=v_r=\varepsilon\) is excluded. Therefore \(\varepsilon\in T_{S,G}(L)\) if and only if \(\varepsilon\in S\), independently of \(L\). Hence \(\varepsilon\) can never distinguish \(T_{S,G}(L)\) from \(T_{S,G}(M)\), and the contraction argument is unaffected by the \(\varepsilon\) case.

3 Ultrametric Fixed-Point Theory for Guarded Automata↩︎

3.1 The Distinguishing-Word Ultrametric and Its Completion↩︎

Definition 14. For \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\), define \[d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])= \begin{cases} 0, & L([\mathcal{A}])=L([\mathcal{B}]),\\[2mm] 2^{-n}, & n=\min\{\,|w|:\mathbf{1}_{L([\mathcal{A}])}(w)\neq \mathbf{1}_{L([\mathcal{B}])}(w)\,\}. \end{cases}\]

Note that if the shortest distinguishing word is the empty word \(\varepsilon\), then \(n=0\) and the distance evaluates to \(2^{-0} = 1\).

The quantity \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])\) measures the length of the shortest input word on which the two automata differ in acceptance. It depends only on the recognized languages and is therefore well defined on equivalence classes.

Lemma 15. The function \(d_{\mathrm{aut}}\) is an ultrametric on \(\mathfrak{A}_\Sigma\).

Proof. We first show that \(d_{\mathrm{aut}}\) is well defined. Let \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\), and suppose that \(\mathcal{A}'\in[\mathcal{A}]\) and \(\mathcal{B}'\in[\mathcal{B}]\) are different representatives of the same equivalence classes. By the definition of language equivalence, we have \(L(\mathcal{A}')=L(\mathcal{A})\) and \(L(\mathcal{B}')=L(\mathcal{B})\). Hence the set of words on which \(\mathcal{A}\) and \(\mathcal{B}\) differ in acceptance is the same as the set of words on which \(\mathcal{A}'\) and \(\mathcal{B}'\) differ in acceptance. Therefore the value of \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])\) does not depend on the chosen representatives.

Non-negativity is immediate, since by definition \(d_{\mathrm{aut}}\) takes only the values \(0\) and \(2^{-n}\) for integers \(n\ge 0\). Symmetry is also immediate, because the condition \(\mathbf{1}_{L([\mathcal{A}])}(w)\neq \mathbf{1}_{L([\mathcal{B}])}(w)\) is symmetric in \([\mathcal{A}]\) and \([\mathcal{B}]\). We next verify the identity of indiscernibles. If \([\mathcal{A}]=[\mathcal{B}]\), then \(L([\mathcal{A}])=L([\mathcal{B}])\), and therefore \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=0\). Conversely, if \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=0\), then by the definition of \(d_{\mathrm{aut}}\) we have \(L([\mathcal{A}])=L([\mathcal{B}])\). Hence \(\mathcal{A}\) and \(\mathcal{B}\) are language equivalent, and therefore \([\mathcal{A}]=[\mathcal{B}]\).

It remains to prove the strong triangle inequality. Define \(\iota:\mathfrak{A}_\Sigma\to\mathcal{L}\) by \(\iota([\mathcal{A}])=L([\mathcal{A}])\). This map is well defined because all representatives of the same automaton class recognize the same language. By the definition of \(d_{\mathrm{aut}}\) and by the definition of the language ultrametric \(d\), for all \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\) we have \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=d(\iota([\mathcal{A}]),\iota([\mathcal{B}]))\). Now let \([\mathcal{A}],[\mathcal{B}],[\mathcal{C}]\in\mathfrak{A}_\Sigma\) be arbitrary. Since \(d\) is an ultrametric on \(\mathcal{L}\) by Theorem 4, we have \(d(\iota([\mathcal{A}]),\iota([\mathcal{C}]))\le \max\{d(\iota([\mathcal{A}]),\iota([\mathcal{B}])),d(\iota([\mathcal{B}]),\iota([\mathcal{C}]))\}\). Using the equality between \(d_{\mathrm{aut}}\) and the pullback of \(d\) under \(\iota\), this becomes \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{C}])\le \max\{d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}]),d_{\mathrm{aut}}([\mathcal{B}],[\mathcal{C}])\}\). Thus \(d_{\mathrm{aut}}\) satisfies non-negativity, symmetry, the identity of indiscernibles, and the strong triangle inequality. Therefore \(d_{\mathrm{aut}}\) is an ultrametric on \(\mathfrak{A}_\Sigma\). ◻

Proposition 16. The map \(\iota:\mathfrak{A}_\Sigma\to\mathcal{L}\), defined by \(\iota([\mathcal{A}])=L([\mathcal{A}])\), is an isometric embedding of \(\mathfrak{A}_\Sigma\) onto the subspace \(\mathcal{L}_{\mathrm{reg}}:=\{\,L\subseteq\Sigma^\ast : L \text{ is regular}\,\}\).

Proof. We first prove that the map \(\iota\) is well defined. Let \([\mathcal{A}]\in\mathfrak{A}_\Sigma\). By definition, \([\mathcal{A}]\) is an equivalence class of deterministic finite automata under language equivalence. Suppose that \(\mathcal{A}'\) is another representative of the same class, that is, \([\mathcal{A}']=[\mathcal{A}]\). Then \(\mathcal{A}'\) and \(\mathcal{A}\) are language equivalent, so \(L(\mathcal{A}')=L(\mathcal{A})\). Therefore the value assigned by \(\iota\) does not depend on the chosen representative of the class. Hence \(\iota([\mathcal{A}])=L([\mathcal{A}])\) is well defined.

Next we prove that \(\iota\) is injective. Let \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\) and assume that \(\iota([\mathcal{A}])=\iota([\mathcal{B}])\). By the definition of \(\iota\), this means that \(L([\mathcal{A}])=L([\mathcal{B}])\). Equivalently, \(L(\mathcal{A})=L(\mathcal{B})\). Hence \(\mathcal{A}\) and \(\mathcal{B}\) are language equivalent. By the definition of the equivalence relation on deterministic finite automata, this implies \([\mathcal{A}]=[\mathcal{B}]\). Thus \(\iota\) is injective.

We now prove that the image of \(\iota\) is exactly \(\mathcal{L}_{\mathrm{reg}}\). First, let \([\mathcal{A}]\in\mathfrak{A}_\Sigma\). Since \(\mathcal{A}\) is a DFA, the language \(L(\mathcal{A})\) recognized by \(\mathcal{A}\) is regular. Hence \(\iota([\mathcal{A}])=L([\mathcal{A}])=L(\mathcal{A})\in\mathcal{L}_{\mathrm{reg}}\). Therefore \(\iota(\mathfrak{A}_\Sigma)\subseteq\mathcal{L}_{\mathrm{reg}}\).

Conversely, let \(L\in\mathcal{L}_{\mathrm{reg}}\). By the definition of a regular language, there exists a DFA\(\mathcal{A}\) over \(\Sigma\) such that \(L(\mathcal{A})=L\). Then \([\mathcal{A}]\in\mathfrak{A}_\Sigma\), and by the definition of \(\iota\) we have \(\iota([\mathcal{A}])=L([\mathcal{A}])=L(\mathcal{A})=L\). Hence every regular language belongs to the image of \(\iota\), so \(\mathcal{L}_{\mathrm{reg}}\subseteq\iota(\mathfrak{A}_\Sigma)\). Combining the two inclusions, we obtain \(\iota(\mathfrak{A}_\Sigma)=\mathcal{L}_{\mathrm{reg}}\).

It remains to prove that \(\iota\) preserves distances. Let \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\) be arbitrary. We consider two cases.

First, suppose that \([\mathcal{A}]=[\mathcal{B}]\). Then \(L([\mathcal{A}])=L([\mathcal{B}])\), and by Definition 14 we have \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=0\). On the other hand, \(\iota([\mathcal{A}])=\iota([\mathcal{B}])\), so \(d(\iota([\mathcal{A}]),\iota([\mathcal{B}]))=0\). Hence in this case \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=d(\iota([\mathcal{A}]),\iota([\mathcal{B}]))\).

Second, suppose that \([\mathcal{A}]\neq[\mathcal{B}]\). Then \(L([\mathcal{A}])\neq L([\mathcal{B}])\). By the definition of \(d_{\mathrm{aut}}\), the distance \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])\) is equal to \(2^{-n}\), where \(n\) is the minimum length of a word \(w\in\Sigma^\ast\) such that \(\mathbf{1}_{L([\mathcal{A}])}(w)\neq\mathbf{1}_{L([\mathcal{B}])}(w)\). Since \(\iota([\mathcal{A}])=L([\mathcal{A}])\) and \(\iota([\mathcal{B}])=L([\mathcal{B}])\), the same word \(w\) is precisely a distinguishing word between the languages \(\iota([\mathcal{A}])\) and \(\iota([\mathcal{B}])\). Therefore, by the definition of the language ultrametric \(d\), we also have \(d(\iota([\mathcal{A}]),\iota([\mathcal{B}]))=2^{-n}\). Hence again \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=d(\iota([\mathcal{A}]),\iota([\mathcal{B}]))\).

Thus, for all \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\), we have \(d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])=d(\iota([\mathcal{A}]),\iota([\mathcal{B}]))\). Therefore \(\iota\) is distance preserving. Since we have already proved that \(\iota\) is injective and that its image is exactly \(\mathcal{L}_{\mathrm{reg}}\), it follows that \(\iota\) is an isometric embedding of \(\mathfrak{A}_\Sigma\) onto \(\mathcal{L}_{\mathrm{reg}}\). ◻

The automaton space is naturally identified with the regular languages. The next result shows that this space is not complete with respect to the distinguishing-word ultrametric.

Proposition 17. The ultrametric space \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) is not complete.

Proof. Since \(\Sigma\) is nonempty, choose a letter \(a\in\Sigma\). Consider the language \(K=\{a^{n^2}:n\ge 0\}\). We first show that \(K\) is not regular. Indeed, suppose for contradiction that \(K\) is regular, and let \(P\) be its pumping length. Choose an integer \(r>P\) and consider the word \(a^{r^2}\in K\). By the pumping lemma, there exist words \(x,y,z\in\Sigma^\ast\) such that \(a^{r^2}=xyz\), \(|xy|\le P\), \(|y|\ge 1\), and \(xy^iz\in K\) for all \(i\ge 0\). Since \(a^{r^2}\) is a unary word, we have \(y=a^t\) for some integer \(t\) with \(1\le t\le P\). Pumping once gives \(xy^2z=a^{r^2+t}\). Because \(1\le t\le P<r\), we have \(r^2<r^2+t<r^2+r<(r+1)^2\). Hence \(r^2+t\) is not a square, so \(a^{r^2+t}\notin K\). This contradicts the pumping lemma. Therefore \(K\) is not regular.

For each integer \(N\ge 1\), define \(K_N:=K\cap\{\,w\in\Sigma^\ast:|w|<N\,\}\). Each language \(K_N\) is finite, because there are only finitely many words of length strictly less than \(N\) over the finite alphabet \(\Sigma\). Hence each \(K_N\) is regular. Therefore, for every \(N\ge 1\), there exists a DFA \(\mathcal{A}_N\) such that \(L(\mathcal{A}_N)=K_N\). Let \([\mathcal{A}_N]\in\mathfrak{A}_\Sigma\) be its equivalence class.

We prove that the sequence \(([\mathcal{A}_N])_{N\ge 1}\) is Cauchy in \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\). Let \(\varepsilon>0\) be arbitrary. Choose an integer \(N_0\) such that \(2^{-N_0}<\varepsilon\). Now let \(M,N\ge N_0\). By the definition of \(K_M\) and \(K_N\), both languages agree with \(K\) on all words of length strictly less than \(N_0\). Therefore \(K_M\) and \(K_N\) agree on all words of length strictly less than \(N_0\). Hence the first possible disagreement between \(K_M\) and \(K_N\), if any, can occur only at length at least \(N_0\). By the definition of \(d_{\mathrm{aut}}\), this gives \(d_{\mathrm{aut}}([\mathcal{A}_M],[\mathcal{A}_N])\le 2^{-N_0}<\varepsilon\). Thus \(([\mathcal{A}_N])_{N\ge 1}\) is a Cauchy sequence in \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\).

It remains to show that this Cauchy sequence has no limit in \(\mathfrak{A}_\Sigma\). Suppose, for contradiction, that there exists \([\mathcal{A}]\in\mathfrak{A}_\Sigma\) such that \([\mathcal{A}_N]\to[\mathcal{A}]\) in \(d_{\mathrm{aut}}\). By Proposition 16, the map \(\iota([\mathcal{B}])=L([\mathcal{B}])\) is an isometry from \(\mathfrak{A}_\Sigma\) onto \(\mathcal{L}_{\mathrm{reg}}\). Therefore the convergence \([\mathcal{A}_N]\to[\mathcal{A}]\) implies \(K_N=L([\mathcal{A}_N])\to L([\mathcal{A}])\) in \((\mathcal{L},d)\).

On the other hand, the sequence \((K_N)\) converges to \(K\) in \((\mathcal{L},d)\). Indeed, for every \(N\ge 1\), the languages \(K_N\) and \(K\) agree on all words of length strictly less than \(N\), because \(K_N\) is exactly the restriction of \(K\) to words of length less than \(N\). Hence \(d(K_N,K)\le 2^{-N}\), and therefore \(d(K_N,K)\to 0\) as \(N\to\infty\). Thus \((K_N)\) has the limit \(K\) in \((\mathcal{L},d)\). Since limits in a metric space are unique, we obtain \(L([\mathcal{A}])=K\). But \(L([\mathcal{A}])\) is recognized by a DFA and is therefore regular, while \(K\) is not regular. This contradiction shows that the Cauchy sequence \(([\mathcal{A}_N])_{N\ge 1}\) does not converge in \(\mathfrak{A}_\Sigma\). Consequently, \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) is not complete. ◻

Proposition 18. The subspace \(\mathcal{L}_{\mathrm{reg}}\) is dense in \((\mathcal{L},d)\). Consequently, the completion of \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) can be naturally identified with \((\mathcal{L},d)\).

Proof. We first prove that \(\mathcal{L}_{\mathrm{reg}}\) is dense in \((\mathcal{L},d)\). Let \(L\subseteq\Sigma^\ast\) be arbitrary. We have to show that, for every accuracy level, there exists a regular language which is sufficiently close to \(L\) in the metric \(d\). Let \(N\ge 1\) be fixed, and define \(L^{<N}:=L\cap\{\,w\in\Sigma^\ast:|w|<N\,\}\). Since \(\Sigma\) is finite, there are only finitely many words over \(\Sigma\) of length strictly less than \(N\). Hence the set \(\{\,w\in\Sigma^\ast:|w|<N\,\}\) is finite, and therefore \(L^{<N}\) is also finite. Every finite language is regular, so \(L^{<N}\in\mathcal{L}_{\mathrm{reg}}\). By construction, \(L^{<N}\) contains exactly those words of \(L\) whose length is strictly less than \(N\). Hence, for every word \(w\in\Sigma^\ast\) with \(|w|<N\), we have \(w\in L^{<N}\) if and only if \(w\in L\). Equivalently, \(\mathbf{1}_{L^{<N}}(w)=\mathbf{1}_L(w)\) for all \(w\in\Sigma^\ast\) with \(|w|<N\). Therefore the first possible disagreement between \(L^{<N}\) and \(L\), if such a disagreement exists, can occur only at a word of length at least \(N\). By the definition of the language ultrametric, this implies \(d(L^{<N},L)\le 2^{-N}\). Since \(N\) can be chosen arbitrarily large, the regular languages \(L^{<N}\) approximate \(L\) arbitrarily well in \((\mathcal{L},d)\). More precisely, for every \(\varepsilon>0\), we may choose \(N\) so large that \(2^{-N}<\varepsilon\), and then the regular language \(L^{<N}\) satisfies \(d(L^{<N},L)<\varepsilon\). Thus every language \(L\in\mathcal{L}\) lies in the closure of \(\mathcal{L}_{\mathrm{reg}}\), and consequently \(\mathcal{L}_{\mathrm{reg}}\) is dense in \((\mathcal{L},d)\).

We now identify the completion of the automaton space. By Proposition 16, the map \(\iota:\mathfrak{A}_\Sigma\to\mathcal{L}\) given by \(\iota([\mathcal{A}])=L([\mathcal{A}])\) is an isometry from \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) onto \(\mathcal{L}_{\mathrm{reg}}\) equipped with the restriction of the metric \(d\). Therefore \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) and \((\mathcal{L}_{\mathrm{reg}},d)\) have the same metric completion up to canonical isometry.

By Theorem 5, the space \((\mathcal{L},d)\) is complete. Since we have just proved that \(\mathcal{L}_{\mathrm{reg}}\) is dense in \((\mathcal{L},d)\), the complete space \((\mathcal{L},d)\) is precisely the completion of \((\mathcal{L}_{\mathrm{reg}},d)\). Using the isometry between \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) and \((\mathcal{L}_{\mathrm{reg}},d)\), it follows that the completion of \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) can be naturally identified with \((\mathcal{L},d)\). ◻

3.2 Guarded Automaton Contractions and Fixed Points↩︎

We now pass from the language-level guarded operators recalled in Theorem 12 to their induced action on automata classes.

Definition 19. Let \(S\subseteq\Sigma^\ast\) be a regular language and let \(G=\{(u_r,v_r):r=1,\dots,p\}\subseteq\Sigma^\ast\times\Sigma^\ast\) be a finite family of guards. The guarded language operator \(T_{S,G}\) maps regular languages to regular languages, because regular languages are closed under finite union and concatenation with fixed words. Hence it induces an operator \(\mathbb{T}_{S,G}:\mathfrak{A}_\Sigma\to\mathfrak{A}_\Sigma\) by \(\mathbb{T}_{S,G}([\mathcal{A}])=[\mathcal{B}]\), where \(\mathcal{B}\) is any DFA recognizing \(T_{S,G}(L([\mathcal{A}]))\).

Remark 20. The operator \(\mathbb{T}_{S,G}\) is well defined. Indeed, if \(\mathcal{A}'\) is another representative of \([\mathcal{A}]\), then \(L(\mathcal{A}')=L(\mathcal{A})\), and hence \(T_{S,G}(L(\mathcal{A}'))=T_{S,G}(L(\mathcal{A}))\). Moreover, if \(\mathcal{B}\) and \(\mathcal{B}'\) are two deterministic finite automata recognizing \(T_{S,G}(L([\mathcal{A}]))\), then \(L(\mathcal{B})=L(\mathcal{B}')\), so \([\mathcal{B}]=[\mathcal{B}']\). Therefore \(\mathbb{T}_{S,G}([\mathcal{A}])\) does not depend on any of the choices involved.

Theorem 21. Let \(S\subseteq\Sigma^\ast\) be regular, and let \(G=\{(u_r,v_r):r=1,\dots,p\}\) be a finite family of guards with guard length at least \(m\ge 1\). Then the induced automaton operator \(\mathbb{T}_{S,G}\) is a contraction on \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) with contraction factor \(2^{-m}\); that is, \(d_{\mathrm{aut}}(\mathbb{T}_{S,G}([\mathcal{A}]),\mathbb{T}_{S,G}([\mathcal{B}]))\le 2^{-m}d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])\) for all \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\).

Proof. Let \([\mathcal{A}],[\mathcal{B}]\in\mathfrak{A}_\Sigma\) be arbitrary. We have to prove that applying the induced operator \(\mathbb{T}_{S,G}\) decreases the automaton distance by at least the factor \(2^{-m}\). By Definition 19, the class \(\mathbb{T}_{S,G}([\mathcal{A}])\) is represented by any DFA recognizing the language \(T_{S,G}(L([\mathcal{A}]))\). Therefore the language recognized by the class \(\mathbb{T}_{S,G}([\mathcal{A}])\) is exactly \(T_{S,G}(L([\mathcal{A}]))\). In the same way, the language recognized by the class \(\mathbb{T}_{S,G}([\mathcal{B}])\) is exactly \(T_{S,G}(L([\mathcal{B}]))\). Thus we have \(L(\mathbb{T}_{S,G}([\mathcal{A}]))=T_{S,G}(L([\mathcal{A}]))\) and \(L(\mathbb{T}_{S,G}([\mathcal{B}]))=T_{S,G}(L([\mathcal{B}]))\). Now, by the definition of the automaton metric \(d_{\mathrm{aut}}\), the distance between two automaton classes is the language ultrametric distance between the languages recognized by these classes. Hence \[d_{\mathrm{aut}}(\mathbb{T}_{S,G}([\mathcal{A}]),\mathbb{T}_{S,G}([\mathcal{B}]))=d(L(\mathbb{T}_{S,G}([\mathcal{A}])),L(\mathbb{T}_{S,G}([\mathcal{B}]))).\] Using the two identities above, this becomes \[d_{\mathrm{aut}}(\mathbb{T}_{S,G}([\mathcal{A}]),\mathbb{T}_{S,G}([\mathcal{B}]))=d(T_{S,G}(L([\mathcal{A}])),T_{S,G}(L([\mathcal{B}]))).\]

Since the family of guards \(G\) has guard length at least \(m\), Theorem 12 applies to the language operator \(T_{S,G}\). Therefore \(T_{S,G}\) is a contraction on \((\mathcal{L},d)\) with contraction factor \(2^{-m}\). Applying this result to the two languages \(L([\mathcal{A}])\) and \(L([\mathcal{B}])\), we obtain \[d(T_{S,G}(L([\mathcal{A}])),T_{S,G}(L([\mathcal{B}])))\le 2^{-m}d(L([\mathcal{A}]),L([\mathcal{B}])).\]

Finally, by Proposition 16, the map \(\iota:\mathfrak{A}_\Sigma\to\mathcal{L}\) given by \(\iota([\mathcal{C}])=L([\mathcal{C}])\) is an isometry onto \(\mathcal{L}_{\mathrm{reg}}\). Hence, for the two automaton classes \([\mathcal{A}]\) and \([\mathcal{B}]\), we have \(d(L([\mathcal{A}]),L([\mathcal{B}]))=d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])\).

Combining the previous estimates gives \(d_{\mathrm{aut}}(\mathbb{T}_{S,G}([\mathcal{A}]),\mathbb{T}_{S,G}([\mathcal{B}]))\le 2^{-m}d_{\mathrm{aut}}([\mathcal{A}],[\mathcal{B}])\). Since \([\mathcal{A}]\) and \([\mathcal{B}]\) were arbitrary, the induced operator \(\mathbb{T}_{S,G}\) is a contraction on \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) with contraction factor \(2^{-m}\). ◻

The previous theorem shows that the induced automaton operator is contractive. However, Proposition 17 shows that the automaton space is not complete. Thus Banach’s fixed-point theorem cannot in general be applied inside \(\mathfrak{A}_\Sigma\). The correct fixed-point object lies in the completion, which is naturally identified with the full language space \((\mathcal{L},d)\). Thus the automaton iteration does not necessarily converge to an automaton, but it always determines a convergent sequence after passing to the completion.

Theorem 22. Under the assumptions of Theorem 21, let \([\mathcal{A}^{(0)}]\in\mathfrak{A}_\Sigma\) be arbitrary and define the Picard iteration by \([\mathcal{A}^{(n+1)}]=\mathbb{T}_{S,G}([\mathcal{A}^{(n)}])\) for \(n\ge 0\). Then the sequence \(([\mathcal{A}^{(n)}])_{n\ge 0}\) is Cauchy in \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\). More precisely, for all integers \(q>n\ge 0\), one has \(d_{\mathrm{aut}}([\mathcal{A}^{(q)}],[\mathcal{A}^{(n)}])\le 2^{-mn}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\). Moreover, if \(L_n:=L([\mathcal{A}^{(n)}])\), then \(L_{n+1}=T_{S,G}(L_n)\) for all \(n\ge 0\), and the sequence \((L_n)\) converges in \((\mathcal{L},d)\) to the unique language fixed point \(L^\ast\) of \(T_{S,G}\).

Proof. Let \([\mathcal{A}^{(0)}]\in\mathfrak{A}_\Sigma\) be fixed, and let \(([\mathcal{A}^{(n)}])_{n\ge 0}\) be the Picard sequence generated by the induced automaton operator \(\mathbb{T}_{S,G}\). By Theorem 21, the operator \(\mathbb{T}_{S,G}\) is a contraction on \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\) with contraction factor \(2^{-m}\). Therefore, for every \(j\ge 1\), we have \(d_{\mathrm{aut}}([\mathcal{A}^{(j+1)}],[\mathcal{A}^{(j)}])\le 2^{-m}d_{\mathrm{aut}}([\mathcal{A}^{(j)}],[\mathcal{A}^{(j-1)}])\).

We first prove by induction that, for every \(j\ge 0\), the distance between two consecutive iterates satisfies \(d_{\mathrm{aut}}([\mathcal{A}^{(j+1)}],[\mathcal{A}^{(j)}])\le 2^{-mj}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\). For \(j=0\), this is just the identity \(d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\le d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\). Suppose now that the estimate holds for some \(j\ge 0\). Applying the contraction property to the pair \([\mathcal{A}^{(j+1)}]\) and \([\mathcal{A}^{(j)}]\), we get \[d_{\mathrm{aut}}([\mathcal{A}^{(j+2)}],[\mathcal{A}^{(j+1)}])\le 2^{-m}d_{\mathrm{aut}}([\mathcal{A}^{(j+1)}],[\mathcal{A}^{(j)}])\le 2^{-m}2^{-mj}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}]).\] Thus \(d_{\mathrm{aut}}([\mathcal{A}^{(j+2)}],[\mathcal{A}^{(j+1)}])\le 2^{-m(j+1)}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\), which completes the induction.

We now prove the announced estimate for two arbitrary iterates. Let \(q>n\ge 0\). Since \(d_{\mathrm{aut}}\) is an ultrametric by Lemma 15, repeated use of the strong triangle inequality gives \[d_{\mathrm{aut}}([\mathcal{A}^{(q)}],[\mathcal{A}^{(n)}])\le \max_{n\le j\le q-1}d_{\mathrm{aut}}([\mathcal{A}^{(j+1)}],[\mathcal{A}^{(j)}]).\] By the estimate for consecutive iterates proved above, for every \(j\) with \(n\le j\le q-1\), we have \(d_{\mathrm{aut}}([\mathcal{A}^{(j+1)}],[\mathcal{A}^{(j)}])\le 2^{-mj}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\). Since \(j\ge n\) and \(m\ge 1\), we have \(2^{-mj}\le 2^{-mn}\). Hence each term in the maximum is bounded above by \(2^{-mn}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])\). Therefore \[d_{\mathrm{aut}}([\mathcal{A}^{(q)}],[\mathcal{A}^{(n)}])\le 2^{-mn}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}]).\] This proves the quantitative estimate.

We now show that the sequence is Cauchy. Let \(\varepsilon>0\) be arbitrary. Since \(m\ge 1\), we have \(2^{-mn}\to 0\) as \(n\to\infty\). Hence there exists an integer \(N\) such that \(2^{-mN}d_{\mathrm{aut}}([\mathcal{A}^{(1)}],[\mathcal{A}^{(0)}])<\varepsilon\). If \(q>n\ge N\), then the estimate above gives \(d_{\mathrm{aut}}([\mathcal{A}^{(q)}],[\mathcal{A}^{(n)}])<\varepsilon\). If \(q=n\), the distance is \(0\), and if \(q<n\), the same conclusion follows by symmetry of \(d_{\mathrm{aut}}\). Thus \(([\mathcal{A}^{(n)}])_{n\ge 0}\) is a Cauchy sequence in \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\).

It remains to identify the limit in the completion. Define \(L_n:=L([\mathcal{A}^{(n)}])\) for every \(n\ge 0\). By the definition of the induced operator \(\mathbb{T}_{S,G}\), the class \([\mathcal{A}^{(n+1)}]=\mathbb{T}_{S,G}([\mathcal{A}^{(n)}])\) recognizes the language \(T_{S,G}(L([\mathcal{A}^{(n)}]))\). Therefore \(L_{n+1}=T_{S,G}(L_n)\) for every \(n\ge 0\). Hence the sequence \((L_n)\) is exactly the Picard iteration of the guarded language operator \(T_{S,G}\) starting from \(L_0=L([\mathcal{A}^{(0)}])\). By Theorem 12, the language operator \(T_{S,G}\) has a unique fixed point \(L^\ast\in\mathcal{L}\), and its Picard iteration from any initial language converges to \(L^\ast\) in \((\mathcal{L},d)\). Applying this to the initial language \(L_0\), we obtain \(L_n\to L^\ast\) in \((\mathcal{L},d)\). Thus the automaton Picard sequence is Cauchy in the automaton space, and its image under the natural embedding into the completion converges to the unique language fixed point \(L^\ast\). ◻

Theorem 23. Under the assumptions of Theorem 21, the following are equivalent:

the induced automaton operator \(\mathbb{T}_{S,G}\) has a fixed point in \(\mathfrak{A}_\Sigma\);
the unique fixed point \(L^\ast\) of the language operator \(T_{S,G}\) is regular.

In this case the fixed point in the automaton quotient space is unique.

Proof. We prove the equivalence in two directions. First, assume that the induced automaton operator \(\mathbb{T}_{S,G}\) has a fixed point in \(\mathfrak{A}_\Sigma\). Thus there exists an automaton class \([\mathcal{A}^\ast]\in\mathfrak{A}_\Sigma\) such that \(\mathbb{T}_{S,G}([\mathcal{A}^\ast])=[\mathcal{A}^\ast]\). By the definition of the induced operator, the class \(\mathbb{T}_{S,G}([\mathcal{A}^\ast])\) recognizes the language \(T_{S,G}(L([\mathcal{A}^\ast]))\). Since this class is equal to \([\mathcal{A}^\ast]\), the two classes recognize the same language. Therefore \(T_{S,G}(L([\mathcal{A}^\ast]))=L([\mathcal{A}^\ast])\). This means that the language \(L([\mathcal{A}^\ast])\) is a fixed point of the language operator \(T_{S,G}\) in the full language space \((\mathcal{L},d)\). By Theorem 12, the operator \(T_{S,G}\) has a unique fixed point in \(\mathcal{L}\), denoted by \(L^\ast\). Hence \(L([\mathcal{A}^\ast])=L^\ast\). But \(L([\mathcal{A}^\ast])\) is recognized by a DFA, namely any representative of the class \([\mathcal{A}^\ast]\). Therefore \(L([\mathcal{A}^\ast])\) is regular. Since \(L([\mathcal{A}^\ast])=L^\ast\), it follows that \(L^\ast\) is regular.

Conversely, assume that the unique language fixed point \(L^\ast\) of \(T_{S,G}\) is regular. By the definition of regularity, there exists a DFA \(\mathcal{A}^\ast\) such that \(L(\mathcal{A}^\ast)=L^\ast\). Equivalently, in terms of equivalence classes, \(L([\mathcal{A}^\ast])=L^\ast\). Since \(L^\ast\) is a fixed point of \(T_{S,G}\), we have \(T_{S,G}(L^\ast)=L^\ast\). Substituting \(L([\mathcal{A}^\ast])=L^\ast\), we get \(T_{S,G}(L([\mathcal{A}^\ast]))=L([\mathcal{A}^\ast])\). By the definition of the induced automaton operator, the class \(\mathbb{T}_{S,G}([\mathcal{A}^\ast])\) is represented by a DFA recognizing the language \(T_{S,G}(L([\mathcal{A}^\ast]))\). But we have just shown that \(T_{S,G}(L([\mathcal{A}^\ast]))=L([\mathcal{A}^\ast])\). Therefore \(\mathbb{T}_{S,G}([\mathcal{A}^\ast])\) and \([\mathcal{A}^\ast]\) recognize the same language. Hence they are the same equivalence class, that is, \(\mathbb{T}_{S,G}([\mathcal{A}^\ast])=[\mathcal{A}^\ast]\). Thus \([\mathcal{A}^\ast]\) is a fixed point of the induced automaton operator.

It remains to prove uniqueness of the fixed point in the automaton quotient space. Suppose that \([\mathcal{A}^\ast]\) and \([\mathcal{B}^\ast]\) are two fixed points of \(\mathbb{T}_{S,G}\). Then \(\mathbb{T}_{S,G}([\mathcal{A}^\ast])=[\mathcal{A}^\ast]\) and \(\mathbb{T}_{S,G}([\mathcal{B}^\ast])=[\mathcal{B}^\ast]\). By the same argument as above, this implies that \(L([\mathcal{A}^\ast])\) and \(L([\mathcal{B}^\ast])\) are both fixed points of the language operator \(T_{S,G}\). Since the language fixed point is unique by Theorem 12, we obtain \(L([\mathcal{A}^\ast])=L^\ast=L([\mathcal{B}^\ast])\). Hence the automata \(\mathcal{A}^\ast\) and \(\mathcal{B}^\ast\) are language equivalent, and therefore \([\mathcal{A}^\ast]=[\mathcal{B}^\ast]\). Thus the fixed point in the automaton quotient space is unique. ◻

Corollary 24. Let \([\mathcal{A}^{(n+1)}]=\mathbb{T}_{S,G}([\mathcal{A}^{(n)}])\) for \(n\ge 0\) be the automaton Picard iteration, and let \(L^\ast\) be the unique language fixed point of \(T_{S,G}\). If \(2^{-mn}d(L([\mathcal{A}^{(0)}]),L^\ast)\le 2^{-N}\) for some integer \(N\ge 1\), then \(\mathbf{1}_{L([\mathcal{A}^{(n)}])}(w)=\mathbf{1}_{L^\ast}(w)\) for all \(w\in\Sigma^\ast\) with \(|w|<N\). In particular, if the initial automaton recognizes the empty language, then \(n\ge \left\lceil N/m\right\rceil\) is sufficient.

Proof. Let \(L_n:=L([\mathcal{A}^{(n)}])\) for every \(n\ge 0\). By the definition of the induced automaton operator, the sequence \((L_n)\) is exactly the Picard iteration of the language operator \(T_{S,G}\) starting from \(L_0=L([\mathcal{A}^{(0)}])\). Therefore, by Theorem 12, we have \(d(L_n,L^\ast)\le 2^{-mn}d(L_0,L^\ast)\) for every \(n\ge 0\). Rewriting this in terms of automata, we obtain \(d(L([\mathcal{A}^{(n)}]),L^\ast)\le 2^{-mn}d(L([\mathcal{A}^{(0)}]),L^\ast)\).

Assume now that \(2^{-mn}d(L([\mathcal{A}^{(0)}]),L^\ast)\le 2^{-N}\). Combining this assumption with the previous estimate gives \(d(L([\mathcal{A}^{(n)}]),L^\ast)\le 2^{-N}\). We prove that this implies agreement on all words of length strictly less than \(N\). If \(d(L([\mathcal{A}^{(n)}]),L^\ast)=0\), then \(L([\mathcal{A}^{(n)}])=L^\ast\), and the conclusion is immediate. Suppose therefore that \(d(L([\mathcal{A}^{(n)}]),L^\ast)>0\). By Definition 2, there exists an integer \(k\ge 0\) such that \(d(L([\mathcal{A}^{(n)}]),L^\ast)=2^{-k}\), where \(k\) is the length of the shortest word on which \(L([\mathcal{A}^{(n)}])\) and \(L^\ast\) differ. Since \(2^{-k}=d(L([\mathcal{A}^{(n)}]),L^\ast)\le 2^{-N}\), we have \(k\ge N\). Hence the first possible disagreement between \(L([\mathcal{A}^{(n)}])\) and \(L^\ast\) can occur only at length at least \(N\). Therefore the two languages coincide on all words \(w\in\Sigma^\ast\) with \(|w|<N\), that is, \(\mathbf{1}_{L([\mathcal{A}^{(n)}])}(w)=\mathbf{1}_{L^\ast}(w)\) for all such words.

It remains to prove the final statement. Assume that the initial automaton recognizes the empty language. Then \(L([\mathcal{A}^{(0)}])=\emptyset\), and therefore \(d(L([\mathcal{A}^{(0)}]),L^\ast)\le 1\). Hence \(2^{-mn}d(L([\mathcal{A}^{(0)}]),L^\ast)\le 2^{-mn}\). Thus the condition \(2^{-mn}d(L([\mathcal{A}^{(0)}]),L^\ast)\le 2^{-N}\) is certainly satisfied whenever \(2^{-mn}\le 2^{-N}\), which is equivalent to \(mn\ge N\). Since \(m\ge 1\) and \(n\) is an integer, the condition \(mn\ge N\) is guaranteed by \(n\ge \left\lceil N/m\right\rceil\). This proves the corollary. ◻

3.3 Regular and Nonregular Fixed-Point Examples↩︎

Example 25. We first illustrate the metric \(d_{\mathrm{aut}}\) on automaton classes. Let \(\Sigma=\{a\}\), let \(\mathcal{A}_1\) recognize \(a^\ast\), and let \(\mathcal{A}_2\) recognize \(a^+\). The languages \(a^\ast\) and \(a^+\) differ exactly on the empty word \(\varepsilon\), because \(\varepsilon\in a^\ast\) and \(\varepsilon\notin a^+\). Since \(|\varepsilon|=0\), the shortest distinguishing word has length \(0\), and therefore \(d_{\mathrm{aut}}([\mathcal{A}_1],[\mathcal{A}_2])=2^0=1\).

Now let \(\mathcal{A}_3\) recognize the language \(\{\varepsilon\}\cup\{a^n:n\ge 2\}\). Then \(L(\mathcal{A}_1)=a^\ast\) and \(L(\mathcal{A}_3)=\{\varepsilon\}\cup\{a^n:n\ge 2\}\) agree on the only word of length \(0\), namely \(\varepsilon\), but they differ on the word \(a\), which has length \(1\). Hence \(d_{\mathrm{aut}}([\mathcal{A}_1],[\mathcal{A}_3])=2^{-1}\).

This example shows the direct meaning of the automaton ultrametric: two automaton classes are close when their recognized languages agree on all short inputs. Thus the metric does not measure the number of states, the shape of the transition graph, or syntactic similarity of automata. It measures semantic agreement up to finite input depth. This is precisely the point of passing to language-equivalence classes.

Example 26. Let \(\Sigma=\{a\}\) and consider the guarded language operator \(T(L)=\{\varepsilon\}\cup aL\). Here the seed language \(\{\varepsilon\}\) is regular, and the unique guard is \((a,\varepsilon)\), so the guard length is \(|a|+|\varepsilon|=1\). Hence, by the guarded language contraction theorem recalled in the preliminaries, the language operator is contractive with contraction factor \(2^{-1}\). Since the seed and the guard preserve regularity, this operator induces an automaton operator \(\mathbb{T}\) on \(\mathfrak{A}_\Sigma\). Starting from the empty language, the first Picard iterates are \(L^{(0)}=\emptyset\), \(L^{(1)}=\{\varepsilon\}\), \(L^{(2)}=\{\varepsilon,a\}\), and \(L^{(3)}=\{\varepsilon,a,a^2\}\). By induction, \(L^{(n)}=\{\varepsilon,a,\dots,a^{n-1}\}\) for every \(n\ge 1\). The limit in the completion is \(L^\ast=a^\ast\), since \(T(a^\ast)=\{\varepsilon\}\cup aa^\ast=a^\ast\). The important automaton-level point is that this fixed point is regular. Therefore Theorem 23 applies and shows that the induced automaton operator has a fixed point in the automaton quotient space. This fixed point is represented by the one-state DFA whose unique state is both initial and accepting and whose \(a\)-transition is a loop. Thus this example illustrates the regular case of the theory. The completion does not add a genuinely new limit outside finite automata: the language fixed point is already represented by a finite automaton. In this case, the automaton-level contraction leads to an actual fixed point in \(\mathfrak{A}_\Sigma\).

Example 27. Let \(\Sigma=\{a,b\}\) and consider the guarded language operator \(T(L)=\{\varepsilon\}\cup aLb\). The seed language \(\{\varepsilon\}\) is regular, and the unique guard is \((a,b)\), whose total length is \(|a|+|b|=2\). Hence the corresponding language operator is contractive with contraction factor \(2^{-2}\), and it induces a contractive operator on automaton classes. Starting from \(L^{(0)}=\emptyset\), we obtain \(L^{(1)}=\{\varepsilon\}\), \(L^{(2)}=\{\varepsilon,ab\}\), and \(L^{(3)}=\{\varepsilon,ab,a^2b^2\}\). In general, \(L^{(n)}=\{a^k b^k:0\le k<n\}\). Each \(L^{(n)}\) is finite, hence regular, so every Picard iterate is represented by a DFA. The limit in the full language space is \(L^\ast=\{a^k b^k:k\ge 0\}\). Indeed, \(T(L^\ast)=\{\varepsilon\}\cup aL^\ast b=\{\varepsilon\}\cup\{a^{k+1}b^{k+1}:k\ge 0\}=L^\ast\). By uniqueness of the guarded language fixed point, this is the unique language fixed point of \(T\). However, \(L^\ast=\{a^k b^k:k\ge 0\}\) is not regular. Therefore, by Theorem 23, the induced automaton operator has no fixed point in \(\mathfrak{A}_\Sigma\). Nevertheless, Theorem 22 shows that the automaton Picard sequence is Cauchy and converges after passing to the completion. This example is central for the present paper. At the language level, the fixed point exists by the guarded contraction theorem. At the automaton level, the same iteration remains meaningful, but the limit is not represented by any finite automaton. Thus the new contribution is the precise identification of the phenomenon: finite automata form a dense but incomplete metric subspace, and guarded automaton iterations may converge only to nonregular languages in the completion.

Example 28. The previous example also gives a concrete witness of incompleteness when \(\Sigma=\{a,b\}\). For each \(n\ge 1\), let \([\mathcal{A}_n]\) be an automaton class recognizing \(L_n=\{a^k b^k:0\le k<n\}\). If \(\ell>n\), then \(L_n\) and \(L_\ell\) agree on all words of length strictly less than \(2n\), and their first disagreement occurs at the word \(a^n b^n\), whose length is \(2n\). Therefore \(d_{\mathrm{aut}}([\mathcal{A}_n],[\mathcal{A}_\ell])=2^{-2n}\) for all \(\ell>n\).

It follows that \(([\mathcal{A}_n])_{n\ge 1}\) is a Cauchy sequence in \((\mathfrak{A}_\Sigma,d_{\mathrm{aut}})\). Indeed, given \(\varepsilon>0\), choose \(N\) such that \(2^{-2N}<\varepsilon\). Then, for all \(\ell>n\ge N\), we have \(d_{\mathrm{aut}}([\mathcal{A}_n],[\mathcal{A}_\ell])=2^{-2n}\le 2^{-2N}<\varepsilon\), and the remaining cases follow by symmetry or equality of indices. If this Cauchy sequence had a limit in \(\mathfrak{A}_\Sigma\), that limit would have to recognize the completion-limit language \(\{a^k b^k:k\ge 0\}\). But this language is not regular, so no DFA recognizes it. Therefore no limit exists inside the automaton quotient space. This example illustrates Proposition 17 in a concrete guarded setting. The point is not only that regular languages are not closed under this metric limit, but also that the natural Picard sequence of finite automata may be forced to converge to a nonregular language. This is exactly why the completion is essential in the automaton version of the theory.

Example 29. We conclude with the quantitative interpretation of convergence. Consider again the operator \(T(L)=\{\varepsilon\}\cup aLb\) from Example 27. Its unique language fixed point is \(L^\ast=\{a^k b^k:k\ge 0\}\), while the \(n\)-th Picard iterate from the empty language is \(L^{(n)}=\{a^k b^k:0\le k<n\}\). The shortest word on which \(L^{(n)}\) and \(L^\ast\) differ is \(a^n b^n\), whose length is \(2n\). Therefore \(d(L^{(n)},L^\ast)=2^{-2n}\). By Corollary 24, if \(2^{-2n}\le 2^{-N}\), equivalently if \(2n\ge N\), then any automaton recognizing \(L^{(n)}\) decides membership correctly for all words of length strictly less than \(N\) with respect to the nonregular limit language \(L^\ast\). Thus after \(n\) iterations, the finite automaton approximation is guaranteed to be correct on all inputs of length less than \(2n\). In particular, for any prescribed input bound \(N\), it is enough to take \(n\ge \left\lceil N/2\right\rceil\). This example highlights the practical meaning of the automaton metric. Even when no finite automaton can represent the fixed point exactly, the Picard iteration produces finite automata with certified finite-depth correctness. This is the automaton-level contribution of the theory: nonregular fixed points can still be approximated by finite automata with explicit quantitative guarantees.

4 Some Generalizations, Extensions and Certified Finite-State Approximation↩︎

In this section we develop three new theoretical results that extend the core framework of Section 3 in directions required for the application to input validation described in Section 5.

4.1 Power-Type Guarded Language Operators↩︎

Definition 30. Let \(S\subseteq\Sigma^\ast\), let \(q\ge 1\) be an integer, and let \(G=\{(u_r,v_r):r=1,\dots,p\}\subseteq\Sigma^\ast\times\Sigma^\ast\) be a finite nonempty family of guards. For every language \(L\in\mathcal{L}\), define \(\mathcal{U}_G(L)=\bigcup_{r=1}^{p}u_rLv_r\). The corresponding \(q\)-power guarded language operator \(T_{S,G,q}:\mathcal{L}\to\mathcal{L}\) is defined by \[T_{S,G,q}(L)=S\cup\bigl(\mathcal{U}_G(L)\bigr)^q=S\cup\left(\bigcup_{r=1}^{p}u_rLv_r\right)^q,\] where, for a language \(A\subseteq\Sigma^\ast\), \(A^q=\underbrace{A\cdot A\cdots A}_{q\text{ factors}}\) denotes the \(q\)-fold language concatenation.

Theorem 31. Let \(T_{S,G,q}\) be the operator from Definition 30. Assume that the guard family \(G\) has guard length at least \(m\ge 1\), that is, \(\min_{1\le r\le p}\bigl(|u_r|+|v_r|\bigr)\ge m\). Then \(T_{S,G,q}\) is a contraction on the complete ultrametric space \((\mathcal{L},d)\) with contraction coefficient \(2^{-qm}\). More precisely, \[d\bigl(T_{S,G,q}(L),T_{S,G,q}(M)\bigr)\le 2^{-qm}d(L,M) \qquad\text{for all }L,M\in\mathcal{L}.\] Consequently, \(T_{S,G,q}\) has a unique fixed point \(L^\ast\in\mathcal{L}\). For every initial language \(L^{(0)}\in\mathcal{L}\), the Picard iteration \(L^{(n+1)}=T_{S,G,q}(L^{(n)})\), \(n\ge 0\), converges to \(L^\ast\). Moreover, \[d(L^{(n)},L^\ast)\le 2^{-qmn}d(L^{(0)},L^\ast) \qquad\text{for all }n\ge 0.\]

Proof. Let \(L,M\in\mathcal{L}\) be arbitrary. If \(L=M\), then \(T_{S,G,q}(L)=T_{S,G,q}(M)\), and therefore \(d\bigl(T_{S,G,q}(L),T_{S,G,q}(M)\bigr)=0=2^{-qm}d(L,M)\). Thus the required estimate is immediate in this case.

Assume now that \(L\neq M\), and let \(n_0=\min\{\,|w|:\mathbf{1}_L(w)\neq\mathbf{1}_M(w)\,\}\). By the definition of the length-based ultrametric, \(d(L,M)=2^{-n_0}\). The languages \(L\) and \(M\) therefore agree on every word of length strictly less than \(n_0\).

Set \(P_L=\bigl(\mathcal{U}_G(L)\bigr)^q\) and \(P_M=\bigl(\mathcal{U}_G(M)\bigr)^q\). We shall prove that \(P_L\) and \(P_M\) agree on all words of length strictly less than \(n_0+qm\).

We first consider the case \(n_0=0\). Every word \(x\in P_L\) admits a representation \[x=u_{r_1}w_1v_{r_1}u_{r_2}w_2v_{r_2}\cdots u_{r_q}w_qv_{r_q},\] where \(r_1,\dots,r_q\in\{1,\dots,p\}\) and \(w_1,\dots,w_q\in L\). Hence \[|x|=\sum_{j=1}^{q}\bigl(|u_{r_j}|+|v_{r_j}|\bigr)+\sum_{j=1}^{q}|w_j|\ge qm.\] The same lower bound holds for every word in \(P_M\). Since \(n_0=0\), we have \(n_0+qm=qm\). Therefore neither \(P_L\) nor \(P_M\) contains a word of length strictly less than \(n_0+qm\). Consequently, the two languages agree vacuously on all words of length strictly less than \(n_0+qm\).

Assume now that \(n_0\ge 1\). Let \(x\in P_L\) and suppose that \(|x|<n_0+qm\). By the definition of the \(q\)-fold concatenation, there exist indices \(r_1,\dots,r_q\in\{1,\dots,p\}\) and words \(w_1,\dots,w_q\in L\) such that \(x=u_{r_1}w_1v_{r_1}u_{r_2}w_2v_{r_2}\cdots u_{r_q}w_qv_{r_q}.\) Taking lengths gives \(|x|=\sum_{j=1}^{q}\bigl(|u_{r_j}|+|v_{r_j}|\bigr)+\sum_{j=1}^{q}|w_j|.\) Since every guard has total length at least \(m\), \(\sum_{j=1}^{q}\bigl(|u_{r_j}|+|v_{r_j}|\bigr)\ge qm\). It follows that \(qm+\sum_{j=1}^{q}|w_j|\le |x|<n_0+qm,\) and hence \(\sum_{j=1}^{q}|w_j|<n_0\). Since all word lengths are nonnegative integers, this implies \(|w_j|<n_0\) for every \(j=1,\dots,q\). The languages \(L\) and \(M\) agree on all words of length strictly less than \(n_0\). Therefore \(w_j\in L\Longleftrightarrow w_j\in M\) for every \(j=1,\dots,q\). In particular, each \(w_j\) appearing in the chosen representation of \(x\) also belongs to \(M\). The same representation then shows that \(x\in P_M\). Thus every word of \(P_L\) having length strictly less than \(n_0+qm\) also belongs to \(P_M\).

By interchanging the roles of \(L\) and \(M\), we obtain the converse implication. Hence \[\mathbf{1}_{P_L}(x)=\mathbf{1}_{P_M}(x) \qquad\text{for every }x\in\Sigma^\ast\text{ with }|x|<n_0+qm.\] Therefore \(P_L\) and \(P_M\) agree on all words of length strictly less than \(n_0+qm\).

We now add the common seed language \(S\). Let \(x\in\Sigma^\ast\) satisfy \(|x|<n_0+qm\). If \(x\in S\), then \(x\in S\cup P_L\) and \(x\in S\cup P_M\). If \(x\notin S\), then \[x\in S\cup P_L\Longleftrightarrow x\in P_L\Longleftrightarrow x\in P_M\Longleftrightarrow x\in S\cup P_M.\] Thus \(T_{S,G,q}(L)=S\cup P_L\) and \(T_{S,G,q}(M)=S\cup P_M\) agree on all words of length strictly less than \(n_0+qm\).

Consequently, their first possible disagreement can occur only at a word of length at least \(n_0+qm\). By the definition of \(d\), \(d\bigl(T_{S,G,q}(L),T_{S,G,q}(M)\bigr)\le 2^{-(n_0+qm)}.\) Using \(d(L,M)=2^{-n_0}\), we obtain \(d\bigl(T_{S,G,q}(L),T_{S,G,q}(M)\bigr)\le 2^{-qm}2^{-n_0}=2^{-qm}d(L,M).\) Since \(q\ge 1\) and \(m\ge 1\), we have \(0<2^{-qm}<1\). Therefore \(T_{S,G,q}\) is a contraction on \((\mathcal{L},d)\).

The space \((\mathcal{L},d)\) is complete. Hence Banach’s fixed-point theorem implies that \(T_{S,G,q}\) possesses a unique fixed point \(L^\ast\in\mathcal{L}\), and that the Picard iteration converges to \(L^\ast\) from every initial language \(L^{(0)}\in\mathcal{L}\).

Finally, applying the contraction estimate repeatedly gives \[d(L^{(n)},L^\ast)=d\bigl(T_{S,G,q}^{\,n}(L^{(0)}),T_{S,G,q}^{\,n}(L^\ast)\bigr)\le \left(2^{-qm}\right)^n d(L^{(0)},L^\ast).\] Since \(T_{S,G,q}(L^\ast)=L^\ast\), this becomes \(d(L^{(n)},L^\ast)\le 2^{-qmn}d(L^{(0)},L^\ast),\) which proves the stated quantitative estimate. ◻

Corollary 32. Under the assumptions of Theorem 31, the following statements hold:

If \(S=\emptyset\), then the unique fixed point of \(T_{\emptyset,G,q}\) is \(L^\ast=\emptyset\).
If \(S=\Sigma^\ast\), then the unique fixed point of \(T_{\Sigma^\ast,G,q}\) is \(L^\ast=\Sigma^\ast\).

In both cases, the Picard iteration converges to the corresponding fixed point from every initial language \(L^{(0)}\in\mathcal{L}\).

Proof. Suppose first that \(S=\emptyset\). Since \(u_r\emptyset v_r=\emptyset\) for every \(r=1,\dots,p\), we have \(\mathcal{U}_G(\emptyset)=\bigcup_{r=1}^{p}u_r\emptyset v_r=\emptyset\). Because \(q\ge 1\), the \(q\)-fold concatenation of the empty language is again empty, so \(\bigl(\mathcal{U}_G(\emptyset)\bigr)^q=\emptyset^q=\emptyset\). Therefore \(T_{\emptyset,G,q}(\emptyset)=\emptyset\cup\emptyset=\emptyset\). Thus \(\emptyset\) is a fixed point. By the uniqueness established in Theorem 31, it is the unique fixed point of \(T_{\emptyset,G,q}\).

Suppose now that \(S=\Sigma^\ast\). For every language \(L\in\mathcal{L}\), \(T_{\Sigma^\ast,G,q}(L)=\Sigma^\ast\cup\bigl(\mathcal{U}_G(L)\bigr)^q=\Sigma^\ast.\) In particular, \(T_{\Sigma^\ast,G,q}(\Sigma^\ast)=\Sigma^\ast\). Hence \(\Sigma^\ast\) is a fixed point. Uniqueness follows again from Theorem 31.

The convergence of the Picard iteration from every initial language follows directly from the same theorem. ◻

Remark 33. For \(q=1\), the operator \(T_{S,G,q}\) reduces to the standard guarded language operator \(T_{S,G,1}(L)=S\cup\bigcup_{r=1}^{p}u_rLv_r\), and Theorem 31 reduces to the usual guarded contraction result with contraction coefficient \(2^{-m}\). Hence, this result generalize the main fixed-point theorem for guarded language operators from [7].

4.2 Systems of Guarded Operators↩︎

Practical input models typically consist of several parameter types or production rules, each validated independently. We organise such a collection as a finite product of guarded operators, one operator per component, and analyse them jointly through a product ultrametric. In the two-component case, when the negative guard families are empty and each component depends only on its own language variable, the system considered below is a decoupled positive special case of the positive–negative guarded language systems studied in [8]. The present \(k\)-component formulation extends this independent-coordinate construction to an arbitrary finite number of components. As we show below, the joint operator decouples into its components, so the existence, uniqueness, and convergence guarantees of the single-operator case carry over to the product setting coordinatewise.

Definition 34. Let \(k\ge 1\). For each \(i=1,\dots,k\), let \(S_i\subseteq\Sigma^\ast\) be a regular language, and let \(G_i=\{(u^i_r,v^i_r):r=1,\dots,p_i\}\subseteq\Sigma^\ast\times\Sigma^\ast\) be a finite nonempty family of guards. The \(i\)-th component operator acts on its own component language and is given by \[T_i(L_1,\dots,L_k) = S_i\cup\bigcup_{r=1}^{p_i}u^i_r\,L_{i}\,v^i_r.\] The joint operator is \(\mathbf{T}=(T_1,\dots,T_k)\), acting on the product space \(\mathcal{L}^k\). The minimum guard length of the system is \(m=\min_{i,r}(|u^i_r|+|v^i_r|)\). The product ultrametric on \(\mathcal{L}^k\) is \[d_\infty\!\left((L_1,\dots,L_k),(M_1,\dots,M_k)\right) =\max_{1\le i\le k}d(L_i,M_i).\]

Remark 35. Each component operator \(T_i\) depends only on its own argument \(L_i\). Hence the joint operator \(\mathbf{T}\) is the product of \(k\) independent single guarded operators of the form recalled in Theorem 12, and its fixed point is obtained componentwise. Theorem 36 below is thus the coordinatewise form of the single-operator result; the product ultrametric \(d_\infty\) serves only to package the \(k\) independent contractions into a single contraction on \(\mathcal{L}^k\).

Theorem 36. Let \(\mathbf{T}\) be a system of guarded operators as in Definition 34, with minimum guard length \(m\ge 1\). Then:

\((\mathcal{L}^k,d_\infty)\) is a complete ultrametric space.
\(\mathbf{T}\) is a contraction on \((\mathcal{L}^k,d_\infty)\) with contraction factor \(2^{-m}\).
\(\mathbf{T}\) has a unique fixed point \((L^\ast_1,\dots,L^\ast_k)\in\mathcal{L}^k\), and the Picard iteration \(\mathbf{L}^{(n+1)}=\mathbf{T}(\mathbf{L}^{(n)})\) converges to this fixed point from any initial vector, with \[d_\infty(\mathbf{L}^{(n)},\mathbf{L}^\ast) \le 2^{-mn}\,d_\infty(\mathbf{L}^{(0)},\mathbf{L}^\ast) \qquad\text{for all }n\ge 0.\]

Proof. (i) Completeness. Non-negativity, symmetry, and the identity of indiscernibles for \(d_\infty\) follow immediately from the corresponding properties of \(d\) on each coordinate. For the strong triangle inequality, let \(\mathbf{L},\mathbf{M},\mathbf{N}\in\mathcal{L}^k\). Then \[\begin{align} d_\infty(\mathbf{L},\mathbf{N}) &= \max_i d(L_i,N_i) \le \max_i\max\{d(L_i,M_i),d(M_i,N_i)\}\\ &= \max\!\left\{\max_i d(L_i,M_i),\,\max_i d(M_i,N_i)\right\} = \max\{d_\infty(\mathbf{L},\mathbf{M}),d_\infty(\mathbf{M},\mathbf{N})\}, \end{align}\] where the first inequality uses the ultrametric property of \(d\) (Theorem 4). A Cauchy sequence in \((\mathcal{L}^k,d_\infty)\) is Cauchy in each coordinate; completeness of \((\mathcal{L},d)\) (Theorem 5) gives coordinatewise limits whose join is the limit in \(d_\infty\). Hence \((\mathcal{L}^k,d_\infty)\) is complete.

(ii) Contraction. Fix \(\mathbf{L},\mathbf{M}\in\mathcal{L}^k\) and a component index \(i\). A word \(w\) distinguishes \(T_i(\mathbf{L})\) from \(T_i(\mathbf{M})\) only if it distinguishes \(u^i_r L_{i} v^i_r\) from \(u^i_r M_{i} v^i_r\) for some \(r\), which requires \(w=u^i_r w' v^i_r\) with \(w'\) distinguishing \(L_{i}\) from \(M_{i}\). Hence \(|w|\ge |u^i_r|+|v^i_r|\ge m\), giving \[d(T_i(\mathbf{L}),T_i(\mathbf{M})) \le 2^{-m}\, d(L_{i},M_{i}) \le 2^{-m}\,d_\infty(\mathbf{L},\mathbf{M}).\] Taking the maximum over \(i\) yields \(d_\infty(\mathbf{T}(\mathbf{L}),\mathbf{T}(\mathbf{M}))\le 2^{-m}d_\infty(\mathbf{L},\mathbf{M})\).

(iii) Unique fixed point and convergence. Since \((\mathcal{L}^k,d_\infty)\) is complete and \(\mathbf{T}\) is a contraction, Theorem 7 applies directly, giving a unique fixed point and the stated convergence rate. ◻

4.3 Two-Sided Convergence↩︎

For pre-filter construction it is useful to track convergence from both the empty language and the full language simultaneously.

Definition 37. Let \(T_{S,G}\) be a single guarded operator with regular seed \(S\) and guard family \(G\) of guard length at least \(m\ge 1\). Define the lower and upper Picard iterates by \[L^{(n)}_{\min}=T_{S,G}^n(\emptyset), \qquad L^{(n)}_{\max}=T_{S,G}^n(\Sigma^\ast), \qquad n\ge 0.\]

Theorem 38. Under the hypotheses of Definition 37, for all \(n\ge 0\):

\(L^{(n)}_{\min}\subseteq L^\ast\subseteq L^{(n)}_{\max}\).
\(d(L^{(n)}_{\min},L^\ast)\le 2^{-mn}\) and \(d(L^{(n)}_{\max},L^\ast)\le 2^{-mn}\).
Both \(L^{(n)}_{\min}\) and \(L^{(n)}_{\max}\) are regular.

Proof. Monotonicity. If \(L\subseteq M\) then \(u_r L v_r\subseteq u_r M v_r\) for every guard \((u_r,v_r)\), so \(T_{S,G}(L)\subseteq T_{S,G}(M)\). Thus \(T_{S,G}\) is monotone with respect to set inclusion.

(i) We prove \(L^{(n)}_{\min}\subseteq L^\ast\) by induction on \(n\). For \(n=0\): \(\emptyset\subseteq L^\ast\). Assuming \(L^{(n)}_{\min}\subseteq L^\ast\), monotonicity gives \(L^{(n+1)}_{\min}=T_{S,G}(L^{(n)}_{\min})\subseteq T_{S,G}(L^\ast)=L^\ast\). The inclusion \(L^\ast\subseteq L^{(n)}_{\max}\) is symmetric: for \(n=0\), \(L^\ast\subseteq\Sigma^\ast\); the inductive step uses \(L^\ast=T_{S,G}(L^\ast)\subseteq T_{S,G}(L^{(n)}_{\max})=L^{(n+1)}_{\max}\).

(ii) By Theorem 12, for any initial language \(L^{(0)}\), \(d(T_{S,G}^n(L^{(0)}),L^\ast)\le 2^{-mn}d(L^{(0)},L^\ast)\). Since \(d(\emptyset,L^\ast)\le 1\) and \(d(\Sigma^\ast,L^\ast)\le 1\), both bounds follow immediately.

(iii) We prove regularity of \(L^{(n)}_{\min}\) by induction. \(L^{(0)}_{\min}=\emptyset\) is regular. If \(L^{(n)}_{\min}\) is regular, then \(T_{S,G}(L^{(n)}_{\min})=S\cup\bigcup_r u_r L^{(n)}_{\min} v_r\) is regular, since regular languages are closed under finite union and concatenation with fixed words, and \(S\) is regular by assumption. The argument for \(L^{(n)}_{\max}\) is identical, starting from \(\Sigma^\ast\). ◻

Remark 39. The estimate in Theorem 38(ii) should be interpreted in terms of finite-depth agreement. The lower iterates \((L^{(n)}_{\min})\) form an increasing sequence of sound under-approximations of \(L^\ast\); no accepted word is ever removed, and after \(n\) iterations all words of \(L^\ast\) of length strictly less than \(mn\) have already appeared. The upper iterates \((L^{(n)}_{\max})\) form a decreasing sequence of over-approximations of \(L^\ast\): the removed words are outside the current certified over-approximation, and after \(n\) iterations all spurious words of length strictly less than \(mn\) have been eliminated. Thus the first possible disagreement with \(L^\ast\) is pushed to length at least \(mn\).

4.4 Soundness of the Iteration-from-Below↩︎

Theorem 40. For all \(n\ge 0\), \(L^{(n)}_{\min}\subseteq L^\ast\). Consequently, if the DFA \([\mathcal{A}^{(n)}]\) recognizes \(L^{(n)}_{\min}\), then every word accepted by \([\mathcal{A}^{(n)}]\) belongs to \(L^\ast\). Moreover, for every \(v\in L^\ast\) with \(|v|<mn\), we have \(v\in L^{(n)}_{\min}\).

Proof. The inclusion \(L^{(n)}_{\min}\subseteq L^\ast\) is part (i) of Theorem 38, proved above. The DFA statement is immediate. For the completeness claim, the case \(n=0\) is vacuous, since there is no word \(v\) with \(|v|<0\). Assume now that \(n\ge 1\). Apply Corollary 24 with initial language \(L^{(0)}_{\min}=\emptyset\) and with \(N=mn\). Since \(d(\emptyset,L^\ast)\le 1\), the certified agreement condition \(2^{-mn}\,d(\emptyset,L^\ast)\le 2^{-N}\) is satisfied. Hence \(\mathbf{1}_{L^{(n)}_{\min}}(w)=\mathbf{1}_{L^\ast}(w)\) for all \(w\) with \(|w|<mn\). Thus if \(v\in L^\ast\) and \(|v|<mn\), then \(\mathbf{1}_{L^{(n)}_{\min}}(v)=\mathbf{1}_{L^\ast}(v)=1\), giving \(v\in L^{(n)}_{\min}\). ◻

4.5 State Complexity of Linearly Nested Bracket Operators↩︎

We now determine the exact number of states of the minimal DFA for \(L^{(n)}_{\min}\) when the guarded operator has Dyck-like structure. This is the key result governing the feasibility of the pre-filter construction.

Definition 41. Let \(k\ge 1\) and let \(\Sigma\) contain \(2k\) distinct bracket symbols \(a_1,b_1,\dots,a_k,b_k\). Set \(\Sigma_{\mathrm{safe}}=\Sigma\setminus\{a_1,b_1,\dots,a_k,b_k\}\). The \(k\)-bracket guarded operator is \(T(L)=\Sigma_{\mathrm{safe}}^\ast \cup\bigcup_{i=1}^k a_i\,L\,b_i.\) The guard length is \(m=2\). We write \(D^{(n)}_k=T^n(\emptyset)\) for the \(n\)-th lower iterate.

Lemma 42. \(D^{(n)}_k\) is the set of all single-chain* (linearly nested) words \[a_{i_1}a_{i_2}\cdots a_{i_t}\,w\,b_{i_t}\cdots b_{i_2}b_{i_1}, \qquad 0\le t<n,\quad i_1,\dots,i_t\in\{1,\dots,k\},\quad w\in\Sigma_{\mathrm{safe}}^\ast,\] that is, words consisting of a single nested chain of \(t\) matching bracket pairs, with \(t<n\), enclosing a core \(w\) of safe symbols. In particular, \(D^{(n)}_k\) is not the set of all well-nested words of nesting depth \(<n\): words made of two or more concatenated sibling bracketed blocks, such as \(a_1b_1a_1b_1\), are well-nested of depth \(1\) but do not belong to any \(D^{(n)}_k\).*

Proof. By induction on \(n\). For \(n=0\): \(D^{(0)}_k=\emptyset\), which is the empty set of chains (\(t<0\) is impossible). For \(n=1\): \(T(\emptyset)=\Sigma_{\mathrm{safe}}^\ast\), which is exactly the set of chains with \(t=0\) (the core \(w\) alone). For the inductive step, assume the claim for \(n\). Then \[D^{(n+1)}_k=\Sigma_{\mathrm{safe}}^\ast\cup\bigcup_i a_i\,D^{(n)}_k\,b_i.\] A word belongs to \(D^{(n+1)}_k\) iff either it lies in \(\Sigma_{\mathrm{safe}}^\ast\) (a chain with \(t=0\)), or it has the form \(a_i x b_i\) with \(x\in D^{(n)}_k\). By the induction hypothesis \(x\) is a single chain of \(t'<n\) pairs with a safe core, hence \(a_i x b_i\) is a single chain of \(t'+1\le n\) pairs with the same safe core. Conversely, by applying structural induction on the strings, every chain of \(1\le t<n+1\) pairs strictly has this form. This proves the claim for \(n+1\). The key structural point is that each guarded production \(L\mapsto a_i\,L\,b_i\) wraps a single occurrence of the recursion variable in one bracket pair; the operator is therefore linear, and it cannot generate words in which two completed bracketed blocks appear side by side. This is consistent with Example 27, where the same operator (for \(k=1\), \(\Sigma_{\mathrm{safe}}=\emptyset\)) has fixed point \(\{a^kb^k:k\ge 0\}\) rather than the full Dyck language. ◻

Theorem 43. Let \(D^{(n)}_k\) be as in Definition 41, with \(n\ge 1\), and assume the safe-free case \(\Sigma_{\mathrm{safe}}=\emptyset\).

If \(k=1\), the minimal DFA for \(D^{(n)}_1\) has exactly \(2n\) states.
If \(k\ge 2\), the minimal DFA for \(D^{(n)}_k\) has exactly \[\frac{k^{n}-1}{k-1}+\frac{k^{n-1}-1}{k-1}+1\] states.

The formula in (i) can be viewed rigorously as the limit as \(k \to 1\) of the formula in (ii) (since \(\lim_{k\to 1} \frac{k^p-1}{k-1} = p\), the fractions evaluate to \(n\) and \(n-1\), giving \(2n\)).

Proof. By Lemma 42 (with \(\Sigma_{\mathrm{safe}}=\emptyset\)), \(D^{(n)}_k\) is the set of single chains \(a_{i_1}\cdots a_{i_t}\,b_{i_t}\cdots b_{i_1}\) with \(0\le t<n\). We count the Myhill–Nerode classes directly; this is the only structure the recogniser must track, and it yields a minimal DFA. Valid prefixes. A nonempty prefix of a word in \(D^{(n)}_k\) is either in an opening phase or a closing phase. An opening-phase prefix has the form \(a_{i_1}\cdots a_{i_s}\) with \(0\le s\le n-1\): only opening brackets have been read so far. A closing-phase prefix has the form \(a_{i_1}\cdots a_{i_t}\,b_{i_t}\cdots b_{i_{s+1}}\), i.e.a chain that has begun closing and still has the pending closer stack \((a_{i_s},\dots,a_{i_1})\) to discharge, with \(1\le t\le n-1\). Because the operator is linear (Lemma 42), once a prefix has started closing it can never open again, so opening- and closing-phase prefixes are never equivalent. Opening-phase classes. Two opening prefixes \(a_{i_1}\cdots a_{i_s}\) and \(a_{j_1}\cdots a_{j_r}\) are equivalent iff they are identical: the only accepting continuation is the matching reverse closer \(b_{i_s}\cdots b_{i_1}\), so any difference in the opening sequence (in length or in some symbol) is exposed by a suitable closing suffix, exactly as in the stack-content argument. There is one such class for each word in \(\{a_1,\dots,a_k\}^{\le n-1}\), giving \(\sum_{s=0}^{n-1}k^s=\frac{k^{n}-1}{k-1}\) classes (the case \(s=0\) is the initial prefix \(\varepsilon\), which is accepting since \(\varepsilon\in D^{(n)}_k\)). Closing-phase classes. A closing-phase prefix is determined, up to equivalence, by its pending closer stack \((a_{i_s},\dots,a_{i_1})\) of length \(s\): the only accepting continuation is \(b_{i_s}\cdots b_{i_1}\), and a mismatch in the pending stack is again exposed by the appropriate closing suffix. The pending stack has length \(s\) with \(0\le s\le n-2\) (it arises from a chain of length \(t\le n-1\) after at least one close, so \(s\le t-1\le n-2\)). The case \(s=0\) is the single “fully closed” accepting class, which is distinct from the initial prefix because no further symbol may follow a completed chain. This gives \(\sum_{s=0}^{n-2}k^s=\frac{k^{n-1}-1}{k-1}\) classes.

Dead class. All remaining prefixes (an unmatched closer, a mismatched closer, or an opening that would exceed depth \(n-1\)) are rejecting with no accepting continuation, forming a single dead class. Total. Summing the three groups, the number of Myhill–Nerode classes is \(\frac{k^{n}-1}{k-1}+\frac{k^{n-1}-1}{k-1}+1 .\) Every class is reachable (the opening prefix \(a_{i_1}\cdots a_{i_s}\) and its partial closings realise each class), so the DFA with one state per class is minimal. For \(k=1\) the two fractions evaluate in the limit to \(n\) and \(n-1\), giving \(2n\), which proves (i); the general case proves (ii). ◻

Remark 44. Theorem 43 is stated for the safe-free case \(\Sigma_{\mathrm{safe}}=\emptyset\), which isolates the bracket-nesting contribution to the state count. When \(\Sigma_{\mathrm{safe}}\neq\emptyset\) the safe symbols may be inserted into the core \(w\) at the innermost level of a chain. Each open-chain prefix then additionally needs a state that loops on \(\Sigma_{\mathrm{safe}}\) at its current depth, so a nonempty safe alphabet adds a bounded number of further “core” states per nesting level; the exact count depends on how safe-symbol loops merge at the maximal depth \(n-1\). The exponential order in \(n\) for \(k\ge 2\) is unaffected. The state counts reported in Table 1 are the safe-free values; the SQL operators of Section 5 carry safe symbols, so their deployed DFAs are correspondingly larger by the additive core-state term.

4.6 Depth-Capped Approximation↩︎

Theorem 43 shows that for \(k\ge 2\) the DFA grows exponentially in the iteration depth \(n\). We resolve this by capping the nesting depth at a constant \(D\) independent of \(n\). Capping depth and repetition constraints is a known strategy in regex matching and automata construction to avoid state-space explosion and mitigate ReDoS vulnerabilities, as seen in counting-set automata [22].

Definition 45. For integers \(n\ge 1\) and \(D\ge 1\), define the depth-capped approximations \[L^{(n,D)}_{\min} = L^{(n)}_{\min}\cap\{w\in\Sigma^\ast:\text{nesting depth of }w\le D\},\] \[L^{(n,D)}_{\max} = L^{(n)}_{\max}\cap\{w\in\Sigma^\ast:\text{nesting depth of }w\le D\}.\]

Theorem 46. Let \(T\) be the \(k\)-bracket guarded operator of Definition 41, and let \(L^{(n,D)}_{\min}\) be its depth-capped lower approximation as in Definition 45.

**Soundness: \(L^{(n,D)}_{\min}\subseteq L^\ast\) for all \(n,D\).
**DFA size: for the safe-free single-chain language generated by Definition 41, i.e. when \(\Sigma_{\mathrm{safe}}=\emptyset\), the minimal DFA for \(L^{(n,D)}_{\min}\) has exactly \[\frac{k^{D+1}-1}{k-1}+\frac{k^{D}-1}{k-1}+1\] states, independent of \(n\) for \(n\ge D+1\) (equal to \(2(D+1)\) when \(k=1\)). A nonempty safe alphabet adds the bounded core-state term of Remark 44.
**Exactness: for \(n\ge D+1\), \(L^{(n,D)}_{\min}=L^\ast\cap\{w:\text{nesting depth of }w\le D\}\).
**Characterisation of incompleteness: for \(n\ge D+1\), \(L^\ast\setminus L^{(n,D)}_{\min} =\{w\in L^\ast:\text{nesting depth of }w>D\}\).

Proof. (i) Follows immediately from Theorem 40, since \(L^{(n,D)}_{\min}\subseteq L^{(n)}_{\min}\subseteq L^\ast\).

(ii) For \(n\ge D+1\), the constraint “depth \(<n\)” in \(L^{(n)}_{\min}\) is dominated by “depth \(\le D\)”, so \(L^{(n,D)}_{\min}\) is exactly the set of single chains of length \(t\le D\) (Lemma 42). This is the language \(D^{(D+1)}_k\), so by Theorem 43 applied with \(n\) replaced by \(D+1\), the safe-free minimal DFA has \((k^{D+1}-1)/(k-1)+(k^{D}-1)/(k-1)+1\) states, independent of \(n\).

(iii) Before proving exactness, observe that \(L^\ast=\bigcup_{q\ge 0}D_k^{(q)}\). Indeed, by Lemma 42, the increasing union \(\bigcup_{q\ge 0}D_k^{(q)}\) is precisely the language of all finite single chains generated by the operator of Definition 41. This union is fixed by \(T\): applying \(T\) either produces a safe core or wraps an already generated finite chain in one additional matching bracket pair. Hence, by uniqueness of the guarded fixed point, this union is equal to \(L^\ast\).

The inclusion \(L^{(n,D)}_{\min}\subseteq L^\ast\cap\{\text{depth}\le D\}\) holds by (i). For the reverse inclusion, let \(w\in L^\ast\) with \(\mathrm{depth}(w)\le D\). By the preceding observation and by Lemma 42, \(w\) is a single chain of depth at most \(D\). Since \(n\ge D+1\), this chain belongs to \(D^{(n)}_k=L^{(n)}_{\min}\). Together with \(\mathrm{depth}(w)\le D\), this gives \(w\in L^{(n,D)}_{\min}\). Therefore \(L^{(n,D)}_{\min}=L^\ast\cap\{w:\text{depth}(w)\le D\}\).

(iv) Follows from (iii) by set difference: \(L^\ast\setminus L^{(n,D)}_{\min} =L^\ast\setminus(L^\ast\cap\{\text{depth}\le D\}) =L^\ast\cap\{\text{depth}>D\}\). ◻

5 Application to Structural Input Validation↩︎

The theoretical framework developed in the preceding sections admits a direct application to the problem of SQL injection prevention. Unlike traditional parse tree validation [12] or monitoring architectures [13] that operate at runtime, we describe a compile-time validation architecture—the Fixed-Point SQL Guard—in which every design decision is grounded in one of the proved theorems.

5.1 Modelling SQL Parameter Types as Guarded Operators↩︎

Each SQL parameter type is modelled as a component of a system of guarded operators in the sense of Definition 34. The four base types and their operators are as follows.

Integer. \(T_1(L)=\{0,\dots,9\}\cup\bigcup_{a\in\{0,\dots,9\}}aL\). Seed \(S_1=\{0,\dots,9\}\), one guard \((a,\varepsilon)\) per digit, \(m_1=1\). Fixed point \(L^\ast_1=\{0,\dots,9\}^+\). Regularity: By Theorem 23, the fixed point is represented by a finite DFA. The Picard iteration converges to this validator in the distinguishing-word ultrametric, but it does not in general reach the exact language after finitely many steps. Starting from the empty language, the \(n\)-th Picard iterate contains the words of the target language up to a finite depth determined by \(n\), and hence approximates the regular fixed point by finite-depth prefixes.
Safe string. Let \(R_{\mathrm{safe}}\subseteq\Sigma^\ast\) be the regular language of strings containing none of the forbidden tokens ’, ;, --, /*, */. Equivalently, \(R_{\mathrm{safe}}\) is recognised by the finite automaton that scans the input and rejects as soon as one of these forbidden tokens is encountered. We use \(R_{\mathrm{safe}}\) as the safe-string component, setting \(T_2(L) = R_{\mathrm{safe}}\). This keeps the model at the level of regular languages and avoids treating multi-character tokens as alphabet symbols. In this component, no recursive nesting is needed: the regular seed \(R_{\mathrm{safe}}\) already gives the intended finite-state validator. Thus this component is included in the product system as a regular finite-state component, while the nonregular behaviour of the application comes from the parenthesised-expression component.
Parenthesised expression. Let \(C\subseteq\Sigma\) be the safe core alphabet, excluding the bracket symbols used by the operator. For one bracket pair, define \(T_3(L)=C^\ast\cup \texttt{(}L\texttt{)}\). The seed is \(S_3=C^\ast\), and the unique guard is \((\texttt{(},\texttt{)})\), so \(m_3=2\). The fixed point is the single-chain language \(L^\ast_3=\{\,\texttt{(}^t w\,\texttt{)}^t : t\ge 0,\;w\in C^\ast\,\}\). This is a linearly nested language generated by the chosen guarded operator; it is not the full Dyck language of all well-nested parenthesised strings. Non-regularity: By the pumping lemma, \(L^\ast_3\) is not regular: the words \(\texttt{(}^n\texttt{)}^n\) are in \(L^\ast_3\) but cannot be pumped within \(L^\ast_3\) for any pumping length. By Theorem 23 no finite automaton can represent \(L^\ast_3\) exactly; the depth-capped pre-filter (Theorem 46) is used instead.
Identifier. Let \(B=\{a,\dots,z,A,\dots,Z,\_\}\) be the set of admissible first characters, and let \(A=\{a,\dots,z,A,\dots,Z,0,\dots,9,\_\}\) be the set of admissible subsequent characters. We define \(T_4(L)=B\cup\bigcup_{a\in A}La\). The seed is \(S_4=B\), and the guards are \((\varepsilon, a)\), one for each \(a\in A\), so \(m_4=1\). The fixed point is \(L^\ast_4=BA^\ast\), the language of non-empty identifiers whose first character is a letter or underscore and whose remaining characters are letters, digits, or underscore. Regularity: By Theorem 23, the fixed point is represented by a finite DFA. The Picard iteration converges to this validator in the distinguishing-word ultrametric, but it does not in general reach the exact language after finitely many steps. Starting from the empty language, the \(n\)-th Picard iterate contains the words of the target language up to a finite depth determined by \(n\), and hence approximates the regular fixed point by finite-depth prefixes.

By Theorem 36, the joint system \((T_1,T_2,T_3,T_4)\) has a unique fixed point vector \((L^\ast_1,\dots,L^\ast_4)\) in \((\mathcal{L}^4,d_\infty)\), with global contraction rate \(m=\min(m_1,\infty,m_3,m_4)=1\).

5.2 DFA Construction via Picard Iteration↩︎

Algorithm 1 constructs the minimal DFA for \(L^{(n)}_{\min,i}\) at depth \(n\) and for the depth-capped approximation \(L^{(n,D)}_{\min,i}\). Its correctness is guaranteed by Theorems 38 and 46.

Similarly, the upper iterate \(L^{(n)}_{\max,i}\) is obtained by replacing \(\emptyset\) with \(\Sigma^\ast\) on line 1.

Remark 47 (Intermediate DFA size). Algorithm 1 calls Minimise after every iteration step. Without minimisation, the concatenation \(\text{Concat}(u,L,v)\) applied to a DFA of \(s\) states yields an NFA of \(s+|u|+|v|\) states, and the subsequent determinisation can in the worst case produce \(2^s\) states before minimisation reduces it again. In practice, for the SQL parameter operators of Section 5, the iterates grow slowly: by Theorem 43 the final minimal DFA at depth \(n\) has at most \((k^n-1)/(k-1)+(k^{n-1}-1)/(k-1)+1=O(k^n/(k-1))\) states, so the minimised intermediate DFAs at step \(j<n\) are no larger than the final size—no step exceeds it. Minimisation after each step therefore keeps the working DFA bounded by the final size throughout, and the total work across all \(n\) steps is \(O\!\left(n\cdot(k^n/(k-1))\cdot|\Sigma|\right)\) transitions. For the depth-capped variant (\(n\ge D+1\)), this stabilises at \(O\!\left(n\cdot(k^{D+1}/(k-1))\cdot|\Sigma|\right)\), which is linear in \(n\) and exponential only in the fixed constant \(D\).

At runtime, each incoming parameter value \(v\) is subjected to the decision procedure of Algorithm 2, which implements the three-zone structure derived from Theorem 38. Notice that \(L^{(n,D)}_{\max,i}\) strictly excludes words of depth \(>D\) (per Definition 45). Therefore, Algorithm 2 acts as a strict depth-limiting firewall policy, deliberately rejecting any payload exceeding depth \(D\) without needing a runtime stack. Throughout this algorithm, the DFAs used are the depth-capped variants \(\mathcal{A}^{(n,D)}_{\min,i}\) and \(\mathcal{A}^{(n,D)}_{\max,i}\) produced by Algorithm 1 with the optional cap \(D\). Using uncapped DFAs would incur the exponential state growth established in Theorem 43(ii); the depth cap keeps every DFA within the constant-in-\(n\) bounds of Table 1.

Figure 2: Three-zone parameter validation (depth-capped DFAs)

Both acceptance and rejection decisions are formally certified: every Valid return implies \(v\in L^\ast_i\) by Theorem 40; every Invalid return at depth \(n\) triggered by a legitimate structural violation or maximum depth policy implies \(v\notin L^{(n,D)}_{\max,i}\) by Theorem 38(i) and Definition 45. The fallback Invalid on line 9 is a security-conservative policy choice, not a theorem; it handles inputs whose depth-capped membership cannot be resolved within \(N_{\max}\) iterations; see the discussion of practical limitations in Section 6.

5.3 State Complexity and Feasibility↩︎

Table 1 collects the DFA state counts for the depth-capped validator, computed from Theorem 46(ii) with \(k\) bracket pairs and cap \(D\).

Table 1: Minimal DFA state counts for the depth-capped pre-filter.
Parameter type	\(k\)	\(D=2\)	\(D=3\)	\(D=4\)	\(D=6\)
Integer / identifier	0	finite DFA	finite DFA	finite DFA	finite DFA
Single-parenthesis expression	1	6	8	10	14
Two-bracket expression	2	11	23	47	191
Three-bracket expression	3	18	54	162	1458

For a practical deployment with at most three bracket types and \(D=4\), all pre-filter DFAs have at most \(162\) bracket-tracking states (plus the bounded safe-symbol core states of Remark 44)—small enough to be loaded into cache and executed in microseconds per input character. However, it is worth noting that for larger alphabets (e.g., \(k \ge 4\)) or deeper caps (\(D \ge 6\)), the state count grows into the thousands, establishing a practical upper bound on the parameters \(k\) and \(D\) for \(O(1)\)-memory deployments.

5.4 Handling Horizontal Repetition (Width vs. Depth)↩︎

The core guarded operator \(T_{3}(L)\) intrinsically defines vertical nesting (depth) by wrapping constructs sequentially inside bracket pairs (e.g., ((1))). According to Lemma 42, a single guarded operator cannot organically represent strings composed of concatenated sibling blocks, such as (1) + (2), because the operator acts linearly. However, recognizing concatenated blocks does not require non-regular memory. Since horizontal repetition involves releasing the memory associated with a fully parsed block, it can be formally addressed by applying the Kleene closure (repetition operator) on top of the depth-capped DFA \(\mathcal{A}_{\min}^{(n,D)}\). By linking the accepting states of the base DFA back to its initial state via the appropriate delimiter symbols (e.g., + or AND), we permit unbounded horizontal width without compromising the strict \(O(N)\) execution time.

5.5 Securing Industrial `SELECT` Queries↩︎

In typical industrial applications, the read-to-write ratio heavily favours SELECT queries. While destructive actions (DROP, DELETE) represent severe availability threats, the primary concern for SELECT statements is data exfiltration (Data Breaches) via techniques like UNION-based or Blind SQL Injection. A prominent technique in Blind SQL Injection involves exploiting nested logical conditions and sleep functions (e.g., IF(ASCII(SUBSTRING((SELECT password),1,1))=65, SLEEP(5), 0)). The structural complexity of these payloads routinely requires nesting depths exceeding the capabilities of a typical application parameter. By imposing a hard depth cap \(D\) on the validation DFA, the fixed-point pre-filter achieves "security by conservative fallback." Malicious queries employing deep nesting are preemptively rejected on structural grounds before any semantic database evaluation occurs, effectively neutralising complex Blind SQLi payloads.

5.6 Next-Generation AI WAF Pipeline and NFA Determinisation↩︎

The theoretical limitations of bounding regular expressions can be overcome practically via an automated compilation pipeline. Rather than manually defining the seed language \(S\), an implementation may employ a machine learning or grammar induction component (such as the classical \(L^\ast\) algorithm [23]) or a Large Language Model (LLM) component to abstract application query logs into generalized structural templates. This AI-driven process extracts a baseline Non-deterministic Finite Automaton (NFA) representing legitimate business logic (the "Seed" NFA). The guarded operators are then algorithmically applied to this seed up to depth \(D\). Finally, the resulting expanded NFA is determinised into a single, unified DFA via the classical subset construction algorithm. To mitigate the theoretical worst-case exponential state explosion during the NFA-to-DFA compilation, the architecture implements micro-segmentation. Instead of compiling a single monolithic DFA for the entire database, the pipeline generates distinct, minimal DFAs tailored to individual API endpoints. These endpoint-specific DFAs reside in the fastest layer of processor cache, performing robust structural validation without requiring backtracking or dynamic memory allocation.

6 Discussion, Limitations, and Future Work↩︎

6.1 Theoretical Limitations↩︎

6.1.0.1 Single-operator scope of Theorems 38–46.

Theorems 38, 40, 43, and 46 are stated and proved for a single guarded operator. Extension to the system setting of Theorem 36 is technically routine—the product ultrametric allows coordinatewise application of the same arguments—but is not carried out here. In particular, the DFA size bounds of Theorem 43 apply to individual components of the system; the size of a DFA for the joint fixed point, if it is regular, may be larger due to product constructions in the minimisation step.

6.1.0.2 Tightness of Theorem 43(ii).

For \(k\ge 2\), the exact count \((k^{n}-1)/(k-1)+(k^{n-1}-1)/(k-1)+1\) is established by classifying valid prefixes into opening-phase classes (one per opening sequence of length \(<n\)) and closing-phase classes (one per pending closer stack of length \(\le n-2\), plus the single completed-chain class). This relies on the operator being linear: a single chain is the only structure a valid prefix can encode, so once closing begins no further opening is possible. The count is exact in the safe-free case \(\Sigma_{\mathrm{safe}}=\emptyset\); a nonempty safe alphabet adds the bounded core-state term of Remark 44, and a seed \(S\) richer than \(\Sigma_{\mathrm{safe}}^\ast\) may introduce additional Myhill–Nerode classes, but the exponential order in \(n\) is unchanged in all cases.

6.1.0.3 Absence of tight bounds for the system case.

Theorem 36 proves existence, uniqueness, and convergence rate for the joint fixed point, but gives no information about the size of DFAs recognising the individual component fixed points when they are regular. Obtaining such bounds is an open problem.

6.1.0.4 Modelling fidelity.

The soundness guarantee of Theorem 40 is relative to the language \(L^\ast\) defined by the chosen guarded operator. If the operator over-approximates the set of valid inputs—for example, by omitting a semantic constraint such as length bounds or character-class restrictions that are not expressible as guards—then \(L^\ast\) will contain strings that are syntactically valid but semantically undesirable. The mathematical guarantees do not compensate for an inaccurate grammar model.

6.2 Limitations of the Depth-Capped Approximation↩︎

6.2.0.1 Incompleteness for deep nesting.

By Theorem 46(iv), the depth-capped pre-filter rejects all valid inputs whose nesting depth exceeds \(D\). In the context of input validation this means that genuinely valid parameter values with nesting depth \(>D\) will be flagged as invalid. For SQL injection prevention this is generally acceptable—real parameter values rarely require nesting depth beyond \(3\) or \(4\)—but it constitutes a false-rejection class whose size depends on the distribution of input values in the application. No formal characterisation of this distribution is given here.

6.2.0.2 Conservative fallback.

When Algorithm 2 exhausts all depths without reaching a decision—a situation that can arise for inputs of large length whose membership in \(L^\ast\) cannot be resolved at depth \(N_{\max}\)—the algorithm returns Invalid as a security-conservative default. This fallback is not certified by any of the proved theorems; it is a policy choice. An alternative is to forward such inputs to a full structural parser, but this is outside the formal framework developed here.

6.3 Limitations of the Application to SQL Injection Prevention↩︎

6.3.0.1 Encoding-layer attacks.

The fixed-point framework operates on the structural level of the input after character decoding. Encoding-based evasions—Unicode normalisation variants, percent-encoding, multi-byte character smuggling—act at a layer below structural validation and are not addressed by the present theory. Handling them requires a preprocessing step that normalises the encoding before the pre-filter runs.

6.3.0.2 Second-order injection.

The soundness guarantee applies at the point of validation. In a second-order injection attack, a value that is structurally valid at the time of storage is later used in a context where it becomes malicious. The framework does not model the relationship between storage context and use context; extending it to cover second-order injection would require a two-phase formulation in which both the write and the read validate against the appropriate fixed point.

6.3.0.3 Semantic SQL constraints.

The guarded operator formalism captures syntactic well-formedness of parameter values but does not model semantic constraints such as type compatibility, referential integrity, or query semantics. A complete validation architecture must layer semantic checks above the fixed-point pre-filter.

6.3.0.4 Dynamic query structures.

In applications that construct query strings programmatically, the structure of the query may vary at runtime in ways that are difficult to anticipate by a fixed guarded operator. The framework is best suited to applications with a well-defined, static parameter schema.

6.4 Open Problems↩︎

The following problems are identified as directions for future work.

Extend Theorems 38–46 to the system setting of Theorem 36, with explicit DFA size bounds for the joint Picard iterates.
Determine whether the exponential lower bound of Theorem 43(ii) is achievable by a polynomial-state DFA if approximate Myhill–Nerode equivalence (restricted to suffixes of bounded length) is used in place of exact minimisation.
Characterise the class of guarded operators for which the fixed point \(L^\ast\) is regular, extending the regularity criterion of Theorem 23 to the system setting.
Develop a formal model of second-order injection within the ultrametric framework, providing soundness guarantees at both the write and read phases.
Investigate the application of the two-sided convergence framework to other domains identified in the discussion—including RNA secondary structure prediction, bounded model checking, and streaming XML validation—where the three-zone decision structure and the certified depth guarantee may provide formal correctness properties not available in current approaches.

Author Contributions↩︎

The authors contributed equally to this study and are listed in alphabetical order. Conceptualization, A.I., H.K., G.P. and B.Z.; methodology, A.I., H.K., G.P. and B.Z.; formal analysis, A.I., H.K., G.P. and B.Z.; investigation, A.I., H.K., G.P. and B.Z.; writing—original draft preparation, A.I., H.K., G.P. and B.Z.; writing—review and editing, A.I., H.K., G.P. and B.Z. All authors have read and agreed to the published version of the manuscript.

Funding↩︎

The fourth author is partially supported by the Bulgarian National Science Fund (BNSF), Grant number KP-06-N92/1.

Data Availability Statement↩︎

No new data were created or analyzed in this study.

Acknowledgments↩︎

Conflicts of Interest↩︎

The authors declare no conflicts of interest.

References↩︎

[1]

Vianu, V. The Bodnarchuk Metric Space of Languages and the Topology of the Learning Space. In Mathematical Foundations of Computer Science 1977; Gruska, J., Ed.; Lecture Notes in Computer Science, Vol. 53; Springer: Berlin/Heidelberg, Germany, 1977; pp. 537–542. https://doi.org/10.1007/3-540-08353-7_177.

[2]

Fulop, S.A.; Kephart, D. Topology of Language Classes. In Proceedings of the 14th Meeting on the Mathematics of Language; Morrill, G.; Muskens, R.; Osswald, R.; Richter, F., Eds.; Association for Computational Linguistics: Chicago, IL, USA, 2015; pp. 26–38. https://aclanthology.org/W15-2303/.

[3]

de Bakker, J.W.; Zucker, J.I. Processes and the Denotational Semantics of Concurrency. Inf. Control1982, 54, 70–120. https://doi.org/10.1016/S0019-9958(82)91250-5.

[4]

America, P.; Rutten, J.J.M.M. Solving Reflexive Domain Equations in a Category of Complete Metric Spaces. J. Comput. Syst. Sci.1989, 39, 343–375. https://doi.org/10.1016/0022-0000(89)90027-5.

[5]

Bonchi, F.; König, B.; Petrişan, D. Up-To Techniques for Behavioural Metrics via Fibrations. In Proceedings of the 29th International Conference on Concurrency Theory (CONCUR 2018); Schewe, S.; Zhang, L., Eds.; Leibniz International Proceedings in Informatics, Volume 118; Schloss Dagstuhl–Leibniz-Zentrum für Informatik: Dagstuhl, Germany, 2018; pp. 17:1–17:17. https://doi.org/10.4230/LIPIcs.CONCUR.2018.17.

[6]

Różowski, W. A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024); Bringmann, K.; Grohe, M.; Puppis, G.; Svensson, O., Eds.; Leibniz International Proceedings in Informatics, Volume 297; Schloss Dagstuhl–Leibniz-Zentrum für Informatik: Dagstuhl, Germany, 2024; pp. 149:1–149:20. https://doi.org/10.4230/LIPIcs.ICALP.2024.149.

[7]

Hristov, H.; Ilchev, A.; Kulina, H.; Zlatanov, B. Guarded Language Operators as Contractions in a Length-Based Ultrametric Space. Mathematics2026, 14, 1644. https://doi.org/10.3390/math14101644.

[8]

Ajeti, L.; Hristov, H.; Ilchev, A.; Zlatanov, B. Weak Monotone Fixed Points for Positive–Negative Guarded Language Systems in a Length-Based Ultrametric Space. Axioms2026, 15, 440. https://doi.org/10.3390/axioms15060440.

[9]

Crespo-Martı́nez, I.S.; Campazas-Vega, A.; Guerrero-Higueras, Á.M.; Riego-DelCastillo, V.; Álvarez-Aparicio, C.; Fernández-Llamas, C. SQL Injection Attack Detection in Network Flow Data. Comput. Secur.2023, 127, 103093. https://doi.org/10.1016/j.cose.2023.103093.

[10]

Crosby, S.A.; Wallach, D.S. Denial of Service via Algorithmic Complexity Attacks. In Proceedings of the 12th USENIX Security Symposium; Washington, DC, USA, 2003; pp. 29–44. https://www.usenix.org/conference/12th-usenix-security-symposium/denial-service-algorithmic-complexity-attacks.

[11]

Staicu, C.-A.; Pradel, M. Freezing the Web: A Study of ReDoS Vulnerabilities in JavaScript-Based Web Servers. In Proceedings of the 27th USENIX Security Symposium; Baltimore, MD, USA, 2018; pp. 361–376. https://www.usenix.org/conference/usenixsecurity18/presentation/staicu.

[12]

Buehrer, G.T.; Weide, B.W.; Sivilotti, P.A.G. Using Parse Tree Validation to Prevent SQL Injection Attacks. In Proceedings of the 5th International Workshop on Software Engineering and Middleware (SEM 2005); Lisbon, Portugal, 2005; pp. 106–113. https://doi.org/10.1145/1108473.1108496.

[13]

Halfond, W.G.J.; Orso, A. AMNESIA: Analysis and Monitoring for NEutralizing SQL-Injection Attacks. In Proceedings of the 20th IEEE/ACM International Conference on Automated Software Engineering (ASE ’05); Long Beach, CA, USA, 2005; pp. 174–183. https://doi.org/10.1145/1101908.1101935.

[14]

Mohri, M.; Nederhof, M.-J. Regular Approximation of Context-Free Grammars through Transformation. In Robustness in Language and Speech Technology; Junqua, J.-C.; Van Noord, G., Eds.; Kluwer Academic Publishers: Dordrecht, The Netherlands, 2001; pp. 153–163. https://doi.org/10.1007/978-94-015-9719-7_6.

[15]

Salomaa, A. Formal Languages; Academic Press: New York, NY, USA, 1973.

[16]

Eilenberg, S. Automata, Languages, and Machines, Vol. A; Academic Press: New York, NY, USA, 1974.

[17]

Schikhof, W.H. Ultrametric Calculus: An Introduction to p-Adic Analysis; Cambridge University Press: Cambridge, UK, 1984. https://doi.org/10.1017/CBO9780511623844.

[18]

Bodnarchuk, V.G. The Metrical Space of Events. I. Cybernetics1965, 1, 20–24. https://doi.org/10.1007/BF01071439.

[19]

Banach, S. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundam. Math.1922, 3, 133–181.

[20]

Bhaskar, T.G.; Lakshmikantham, V. Fixed Point Theorems in Partially Ordered Metric Spaces and Applications. Nonlinear Anal. Theory Methods Appl.2006, 65, 1379–1393. https://doi.org/10.1016/j.na.2005.10.017.

[21]

Hopcroft, J.E.; Motwani, R.; Ullman, J.D. Introduction to Automata Theory, Languages, and Computation, 3rd ed.; Pearson/Addison-Wesley: Boston, MA, USA, 2007.

[22]

Turoňová, L.; Holík, L.; Lengál, O.; Saarikivi, O.; Veanes, M.; Vojnar, T. Regex Matching with Counting-Set Automata. Proc. ACM Program. Lang.2020, 4, 1–30. https://doi.org/10.1145/3428286.

[23]

Angluin, D. Learning Regular Sets from Queries and Counterexamples. Inf. Comput.1987, 75, 87–106. https://doi.org/10.1016/0890-5401(87)90052-6.

Corresponding author: atanasilchev@uni-plovdiv.bg ↩︎

Ultrametric Convergence of Guarded Automata and Applications to Structural Input Validation