Pith. sign in

REVIEW 2 major objections 4 minor 25 references

The paper shows that guarded automaton operators contract a distinguishing-word ultrametric, so iterating a DFA converges to a unique language fixed point, which is regular exactly when the iteration stops at a finite automaton.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 13:32 UTC pith:MFYHZ7KA

load-bearing objection Sound automaton-space theory with a genuine dependency on an unproved prior theorem; the application claims outrun the proofs but the core is referee-worthy. the 2 major comments →

arxiv 2607.19065 v1 pith:MFYHZ7KA submitted 2026-07-21 cs.FL

Ultrametric Convergence of Guarded Automata and Applications to Structural Input Validation

Atanas Ilchev , Hristo Kiskinov , George Pashev , Boyan Zlatanov This is my paper
classification cs.FL MSC 68Q4547H1054E5068Q6068R15
keywords ultrametricguarded language operatorsdeterministic finite automatalanguage equivalencecontractionPicard iterationfixed pointstructural input validation
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that the space of deterministic finite automata, up to language equivalence, carries a natural ultrametric: two automata are close when they agree on all short inputs, the distance being 2^{-n} for the shortest distinguishing word of length n. This space is isometric to the regular languages, is dense but not complete, and its metric completion is the space of all formal languages. Operators of the guarded form L → S ∪ ⋃ u_r L v_r — where every recursive call is wrapped in fixed left and right contexts of total length at least m — contract the automaton ultrametric by the factor 2^{-m}. Their Picard iterates therefore always converge to a unique language fixed point in the completion; the fixed point is an actual automaton exactly when it is regular. The paper leverages this to build depth-capped DFAs with certified finite-depth correctness, giving ReDoS-immune pre-filters for nested inputs such as parenthesised SQL parameters.

Core claim

The central claim: the quotient of DFAs by language equivalence, with distance 2^{-n} where n is the length of the shortest distinguishing word, is isometric to the regular languages, is dense and not complete, and its metric completion is the space of all formal languages. Any guarded operator T(L)=S∪⋃ u_r L v_r with guard length at least m induces a 2^{-m}-contraction on this space, so its Picard iterates of automata are Cauchy and converge in the completion to the unique language fixed point L*. That fixed point is realized by a DFA iff L* is regular; if it is nonregular, each iterate is still a DFA and, once 2^{-mn}d(L(0),L*) ≤ 2^{-N}, it agrees with L* on all words of length < N. Even a

What carries the argument

The distinguishing-word ultrametric d_aut on DFA equivalence classes—identical to the length-based ultrametric d on languages via the isometry ι([A])=L(A)—and the guarded operator T(L)=S∪⋃ u_r L v_r. The guard length m makes T a 2^{-m}-contraction, which is the mechanism turning Picard iteration into a Cauchy family whose n-th automaton is certified correct up to length mn.

Load-bearing premise

The contraction factor 2^{-m} — the engine behind every convergence rate and certification bound in the paper — is inherited from an earlier theorem about guarded language operators recalled in Section 2; if that theorem has any unstated restriction, the present claims weaken accordingly.

What would settle it

Search all pairs of DFAs with up to, say, 4 states over {a,b}; for the guarded operator T(L)={ε}∪aLb, verify d_aut(T([A]), T([B])) ≤ 2^{-2} d_aut([A],[B]). A counterexample would falsify Theorem 3.8 and the certification corollary; verifying it confirms the central estimate on a small finite test set.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Nonregular fixed points (e.g., {a^k b^k}) are still approximated by DFA iterates, with the n-th iterate certified to exactly match the fixed point on all words of length < N once 2^{-mn} d(L(0),L*) ≤ 2^{-N}.
  • Starting from the empty language, n ≥ ⌈N/m⌉ iterations suffice to certify correctness on every input of length < N, so the required iteration count is linear in the desired validation depth.
  • For the k-bracket guarded operator, the minimal DFA of the n-th lower iterate has (k^n−1)/(k−1)+(k^{n−1}−1)/(k−1)+1 states; capping nesting depth at D makes the size independent of n and yields constant-in-n pre-filter DFAs.
  • Two-sided iteration from ∅ and Σ* yields monotone lower/upper approximations of L*: the lower sequence is sound (never accepts a word outside L*), and after n iterations every word of L* of length < mn has already appeared in it.
  • A coordinatewise product construction extends the contraction, uniqueness, and rate to systems of guarded operators, matching the paper's SQL parameter model of several independent parameter types.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Testable extension: the same guarded-contraction argument could be applied to tree-shaped inputs (e.g., XML or JSON), where the 'guards' are the opening and closing tags; the distinguishing-word ultrametric would then measure agreement on all trees of bounded height. The paper lists streaming XML validation as a possible domain but leaves the formal extension to tree languages open.
  • The paper's own limitation section notes that SQL semantic constraints are not expressible as guards. A natural next experiment is to combine the depth-certified DFA pre-filter with a separate semantic validator and measure how often the pre-filter's conservative rejection of deep-nesting legitimate inputs occurs; the paper does not characterize that input distribution.
  • The exponential state growth for k bracket types is inherent to exact minimization (Theorem 4.14), but the paper poses an open question about approximate Myhill–Nerode equivalence; one could try bounded-suffix indistinguishability to build smaller state pre-filters while keeping the certified-depth property.
  • The completion result implies that every sequence of automata with pairwise disagreement length tending to infinity has a language limit; this could offer a way to compare outputs of grammar induction algorithms by semantic distance rather than exact language equality, though the paper does not pursue this.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 4 minor

Summary. The paper develops a fixed-point theory for guarded language operators on the space of DFA language-equivalence classes equipped with a distinguishing-word ultrametric. It shows that this space is isometric to the regular languages, is dense but incomplete in the full language space, and that guarded operators induce 2^{-m}-contractions on the automaton quotient. The Picard iteration is shown to be Cauchy, converging in the completion to the unique language fixed point, which is representable by a DFA exactly when it is regular. The paper then derives certified finite-depth approximations, state-complexity bounds for linearly nested bracket languages, and a depth-capped DFA construction applied to SQL parameter validation as a ReDoS-immune structural pre-filter.

Significance. If the results hold, the paper provides a clean metric formulation of approximating (possibly nonregular) fixed points of guarded operators by finite automata, with explicit quantitative guarantees on the depth up to which the approximation is exact. The proofs of the automaton-space propositions (Prop. 3.3–3.5, Thm. 3.8–3.10) and of the power-operator contraction (Thm. 4.2) are coherent and detailed; the Myhill–Nerode counting in Thm. 4.14 is plausible and checks out on small cases. The application is honest about its modelling limits and clearly separates formal guarantees from engineering decisions. The main caveat is that the quantitative engine—the contraction factor, Picard rate, and certification bounds—is imported from Theorem 2.12, which is quoted from the authors' earlier work [7] but not proved in this manuscript.

major comments (2)
  1. [§2, Theorem 2.12; used in §3.2 and §4] The central quantitative claims of the paper (Theorems 3.8–3.11, 4.9, 4.11, 4.17) all derive their contraction factor 2^{-m}, the Picard convergence rate, and the finite-depth certification bounds from Theorem 2.12, which is stated but not proved here. Since this is the load-bearing premise for the paper's main results, the authors should either include a self-contained proof (or at least a detailed proof sketch) of Theorem 2.12 in an appendix, or give an exact pointer to the theorem in [7] and explicitly confirm that the hypotheses stated here—arbitrary seed S, arbitrary finite guard family, and guard length at least m≥1—are precisely the hypotheses of [7]. I am not claiming that the theorem is false; the issue is verifiability and self-containedness of the paper's quantitative core.
  2. [§4.2, Theorem 4.7 proof] The contraction proof for each component T_i is incomplete as written. The text says that a distinguishing word w for T_i(L) and T_i(M) must have the form w = u_i^r w' v_i^r with w' distinguishing L_i from M_i, and concludes |w| ≥ |u_i^r|+|v_i^r| ≥ m, giving d(T_i(L),T_i(M)) ≤ 2^{-m} d(L_i,M_i). This inference is only valid when d(L_i,M_i)=1 (i.e., the shortest distinguishing word has length 0). If d(L_i,M_i)=2^{-n0} with n0>0, then |w'|≥n0, so the correct bound is |w|≥|u_i^r|+|v_i^r|+|w'|≥m+n0, which yields the stated contraction factor. The argument should be corrected to include the +|w'| term; otherwise the displayed inequality does not follow from the preceding sentence.
minor comments (4)
  1. [§3.3, Example 3.12] The text writes 'd_aut([A1],[A2]) = 2^0 = 1'; this should be 2^{-0} to match Definition 3.1. The value is correct, but the notation is inconsistent.
  2. [§4.2, Definition 4.5] The notation T_i(L_1,...,L_k) is misleading because each component depends only on its own argument L_i. Writing T_i(L_i) would clarify the coordinatewise nature of the system, which the subsequent Remark 4.6 already emphasises.
  3. [§5.1, base types] The expression 'global contraction rate m = min(m1,∞,m3,m4) = 1' is stylistically awkward; the ∞ for T2 (which has no guards) is understandable but should be explained or simply written as min(m1,m3,m4). Also, the notation 'T3(L)=C*∪(L)' for the parenthesised-expression operator is ambiguous; it should be written as C* ∪ '(' L ')'.
  4. [§4.5, Definition 4.16] The notion of 'nesting depth of w' is used formally in Theorem 4.17 and Definition 4.16 but is never defined. Since the paper's certified state-count results depend on this notion, a short formal definition would improve precision.

Circularity Check

0 steps flagged

No significant circularity found: automaton contraction transfers a parameter-free prior theorem, and the completion, state-complexity, and approximation results are proved from standard facts; application limitations are explicit.

full rationale

The paper's central derivation is not circular. Definition 3.1 defines daut([A],[B]) as d(L([A]),L([B])); the isometry in Proposition 3.3 is therefore a definitional identification of automaton classes with regular languages, while the substantive claims are the incompleteness of (AΣ,daut), its completion by (L,d), the induced contraction, and the depth-certified approximations. The contraction Theorem 3.8 is obtained by applying Theorem 2.12 to the regular languages L([A]), L([B]) and then using the isometry; this is a genuine transfer, not a fit. Theorem 2.12 is a self-cited result from [7] (authors overlap), and it is load-bearing for the quantitative rates in Theorems 3.9–3.11, 4.9, 4.11 and 4.17. But the cited theorem is parameter-free, with hypotheses (arbitrary seed S, finite guard family of minimum length ≥ 1) that do not include the present conclusions; the paper even supplies the ε-case justification in Remark 2.13. Under the rule that self-citation is not itself circular when the cited statement is an independent, non-fitted theorem, this is a proof dependency rather than a circular reduction. The completion argument (Propositions 3.4–3.5) uses the pumping lemma and standard density/completeness facts; the state-complexity theorem (Theorem 4.14) is a direct Myhill–Nerode count; the q-power contraction (Theorem 4.2) and the product-system theorem (Theorem 4.7) are proved self-containedly. The application-side limitation is explicit: Section 6.1 says 'The soundness guarantee of Theorem 4.11 is relative to the language L∗ defined by the chosen guarded operator,' and Section 6.2 acknowledges the depth-cap false-rejection class. No fitted parameter is renamed as a prediction. Accordingly, no circular step is exhibited.

Axiom & Free-Parameter Ledger

1 free parameters · 6 axioms · 0 invented entities

Central results rest on standard automata/ultrametric facts plus the prior guarded-contraction theorem from the same group, which this paper does not reprove. Application claims additionally assume the guarded operator models SQL parameters and that a small depth cap D is acceptable; the authors themselves flag semantic-model and false-rejection caveats in Section 6. No fitted parameters are used in the theoretical derivation; D is a practical design parameter. No new physical or mathematical entities are introduced.

free parameters (1)
  • nesting depth cap D = 3-4 in the deployment discussion; Table 1 explores D = 2,3,4,6
    Application-specific cutoff that trades DFA size against false rejections; chosen pragmatically rather than fitted to data. The theorems hold for any D, so it does not prop up the mathematics.
axioms (6)
  • domain assumption Theorem 2.12 from [7]: guarded language operator T_{S,G}(L)=S union union u_r L v_r with guard length >= 1 is a 2^(-m)-contraction with unique fixed point and Picard convergence rate.
    Used as the language-level foundation for Theorems 3.8-3.11 and Section 4; authors of [7] overlap with current authors, and the proof is not reproduced.
  • standard math Completeness and compactness of (L,d) as a Cantor space, and the ultrametric properties of the length-based distance.
    Used to identify the completion and to apply Banach's fixed-point theorem; cited to [1,2,18].
  • standard math Pumping lemma, closure properties of regular languages, and Myhill-Nerode theorem.
    Used in Proposition 3.4 and Theorem 4.14 for nonregularity proofs and minimal state counts.
  • domain assumption The guarded-operator model of SQL parameters captures the intended notion of valid input.
    Section 6.1 admits that semantic constraints such as length bounds and character-class restrictions are not modelled; the soundness guarantee is relative to L*, not to actual SQL validity.
  • ad hoc to paper The depth cap D is small enough that legitimate inputs are not falsely rejected in practice.
    The introduction calls D=3 or 4 a pragmatic choice; Section 6.2 notes the size of the false-rejection class depends on the input distribution, which is not characterized.
  • ad hoc to paper The seed NFA produced by the L*/LLM component in the proposed AI pipeline is correct.
    Section 5.6 assumes a machine-learning or grammar-induction step yields the seed for guarded operators, but provides no correctness condition or formal derivation.

pith-pipeline@v1.3.0-alltime-deepseek · 24872 in / 17354 out tokens · 181992 ms · 2026-08-01T13:32:58.936775+00:00 · methodology

0 comments
read the original 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.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 9 canonical work pages

  1. [1]

    The Bodnarchuk Metric Space of Languages and the Topology of the Learning Space

    Vianu, V. The Bodnarchuk Metric Space of Languages and the Topology of the Learning Space. InMathematical Foundations of Computer Science 1977; Gruska, J., Ed.; Lecture Notes in Computer Science, Vol. 53; Springer: Berlin/Heidelberg, Germany, 1977; pp. 537–

    1977

  2. [2]

    Topology of Language Classes

    Fulop, S.A.; Kephart, D. Topology of Language Classes. InProceedings 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/

    2015

  3. [3]

    Processes and the Denotational Semantics of Concurrency

    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

    work page doi:10.1016/s0019-9958(82)91250-5

  4. [4]

    Solving Reflexive Domain Equations in a Category of Com- plete Metric Spaces.J

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

    doi:10.1016/0022- 1989

  5. [5]

    Bonchi, F.; König, B.; Petrişan, D.Up-ToTechniquesforBehaviouralMetricsviaFibrations. InProceedings 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. ht...

    doi:10.4230/lipics.concur.2018.17 2018

  6. [6]

    A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions

    Różowski, W. A Complete Quantitative Axiomatisation of Behavioural Distance of Regular Expressions. InProceedings of the 51st International Colloquium on Automata, Lan- guages, and Programming (ICALP 2024); Bringmann, K.; Grohe, M.; Puppis, G.; Svens- son, O., Eds.; Leibniz International Proceedings in Informatics, Volume 297; Schloss Dagstuhl–Leibniz-Zen...

    work page doi:10.4230/lipics.icalp.2024.149 2024

  7. [7]

    Guarded Language Operators as Contractions in a Length-Based Ultrametric Space.Mathematics2026,14, 1644

    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

    work page doi:10.3390/math14101644

  8. [8]

    Weak Monotone Fixed Points for Positive– Negative Guarded Language Systems in a Length-Based Ultrametric Space.Axioms2026, 15, 440

    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

    work page doi:10.3390/axioms15060440

  9. [9]

    SQL Injection Attack Detection in Network Flow Data.Comput

    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

    arXiv 2023

  10. [10]

    Denial of Service via Algorithmic Complexity Attacks

    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. 25

    2003

  11. [11]

    Freezing the Web: A Study of ReDoS Vul- nerabilities in JavaScript-Based Web Servers

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

    2018

  12. [12]

    Using Parse Tree Validation to Pre- vent SQL Injection Attacks

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

    arXiv 2005

  13. [13]

    AMNESIA: Analysis and Monitoring for NEutralizing SQL- Injection Attacks

    Halfond, W.G.J.; Orso, A. AMNESIA: Analysis and Monitoring for NEutralizing SQL- Injection Attacks. InProceedings 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

    Pith/arXiv arXiv 2005

  14. [14]

    Regular Approximation of Context-Free Grammars through Transformation

    Mohri, M.; Nederhof, M.-J. Regular Approximation of Context-Free Grammars through Transformation. InRobustness in Language and Speech Technology; Junqua, J.-C.; Van Noord, G., Eds.; Kluwer Academic Publishers: Dordrecht, The Netherlands, 2001; pp. 153–

    2001

  15. [15]

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

    1973

  16. [16]

    A; Academic Press: New York, NY, USA, 1974

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

    1974

  17. [17]

    https://doi.org/10.1017/CBO9780511623844

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

    work page doi:10.1017/cbo9780511623844 1984

  18. [18]

    The Metrical Space of Events

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

    work page doi:10.1007/bf01071439

  19. [19]

    Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales.Fundam

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

    1922

  20. [20]

    Fixed Point Theorems in Partially Ordered Metric Spaces and Applications.Nonlinear Anal

    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

    work page doi:10.1016/j.na.2005.10.017 2006

  21. [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

    2007

  22. [22]

    Regex Matching with Counting-Set Automata.Proc

    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

    doi:10.1145/3428286 2020

  23. [23]

    Learning Regular Sets from Queries and Counterexamples.Inf

    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. 26

    doi:10.1016/0890-5401(87)90052-6 1987

  24. [163]

    https://doi.org/10.1007/978-94-015-9719-7_6

    work page doi:10.1007/978-94-015-9719-7_6

  25. [542]

    https://doi.org/10.1007/3-540-08353-7_177

    work page doi:10.1007/3-540-08353-7_177