The reviewed record of science sign in
Pith

arxiv: 2606.20454 · v1 · pith:GMXWEF2Z · submitted 2026-06-18 · cs.FL

Minimality of Random Moore Automata under Prefix-Dependent Congruences

Mat\'ias Carrasco , Sergio Yovine This is my paper

Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel 2026-06-26 14:55 UTCgrok-4.3pith:GMXWEF2Zrecord.jsonopen to challenge →

classification cs.FL
keywords random Moore automataprefix-dependent congruencestrivial congruenceminimalityprobabilistic automatapruning processfirst-moment argument
0
0 comments X

The pith

If two independent labels agree with probability less than one and each admits at least three symbols, random Moore automata induce a trivial prefix-dependent congruence with high probability.

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

The paper establishes that, under a random transition model with independent uniform choices for transitions and for state labels, the prefix-dependent congruence collapses to the identity relation with high probability whenever any two labels agree with probability strictly below one and every label allows at least three symbols. A sympathetic reader would care because the result supplies a probabilistic certificate that almost every such automaton is minimal: no two distinct states remain indistinguishable once admissible continuations are allowed to depend on the observed prefix. The same guarantee applies directly to probabilistic deterministic finite automata as a special case. The argument proceeds by tracking pairs of states through a pruning process whose early phase is controlled by collision-free exploration and whose later phase is bounded by a first-moment calculation showing that surviving pairs cannot form nontrivial classes.

Core claim

If two independent labels agree with probability strictly less than one, and every label has at least three admissible symbols, then the induced congruence is trivial with high probability. The proof combines a pruning process on pairs, a collision-free exploration controlling its early evolution, and a first-moment argument showing that the remaining pairs cannot organize into nontrivial equivalence classes.

What carries the argument

The prefix-dependent congruence, which equates two states only when no common admissible continuation (whose symbols may depend on the observed prefix) distinguishes their future outputs.

If this is right

  • Almost every automaton generated under the model is minimal.
  • The same conclusion holds for the special case of probabilistic deterministic finite automata.
  • States remain pairwise distinguishable once admissible words are permitted to depend on the prefix observed so far.
  • The pruning-plus-first-moment technique bounds the probability that any nontrivial equivalence class survives.

Where Pith is reading between the lines

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

  • The same random model could be used to generate large minimal automata for testing equivalence algorithms without explicit minimality checks.
  • The argument may adapt to automata whose admissible-symbol sets are drawn from other distributions that still satisfy the three-symbol and sub-unit agreement conditions.
  • Empirical sampling of moderate-size instances could locate the finite-size threshold at which the high-probability statement becomes observable.

Load-bearing premise

Transitions and labels are drawn independently and uniformly at random from their respective domains.

What would settle it

An explicit finite automaton satisfying the label-agreement and symbol-count conditions yet containing two distinct states that remain equivalent under the prefix-dependent congruence would falsify the claim.

read the original abstract

We study prefix-dependent congruences for random deterministic transition systems with state outputs. In this setting, the admissible continuations used to compare two states may depend on the observed prefix, and two states are identified only if no common admissible continuation distinguishes their future outputs. The framework includes probabilistic deterministic finite automata as a motivating special case. We analyze the random transition model in which all transition values are independent and uniform. Each state is also assigned an independent label that specifies both its output and its set of admissible symbols. If two independent labels agree with probability strictly less than one, and every label has at least three admissible symbols, then the induced congruence is trivial with high probability. The proof combines a pruning process on pairs, a collision-free exploration controlling its early evolution, and a first-moment argument showing that the remaining pairs cannot organize into nontrivial equivalence classes.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies prefix-dependent congruences on random Moore automata. Transitions are independent and uniform; each state has an independent label for output and admissible symbols. The claim is that if labels agree with probability <1 and each admits ≥3 symbols, the induced congruence is trivial w.h.p. The proof uses pruning on pairs, collision-free exploration, and a first-moment argument.

Significance. If correct, this gives a probabilistic minimality guarantee for a generalization of equivalence in probabilistic automata. Strengths include the explicit random model with no fitted parameters and direct use of the probabilistic method.

minor comments (2)
  1. Clarify the exact probability bound in the main theorem statement.
  2. Add a reference to standard first-moment method applications in automata theory.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary of the manuscript and for recommending acceptance.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states an explicit random model (independent uniform transitions, independent labels) and derives a high-probability triviality result for the induced prefix-dependent congruence when label agreement probability is <1 and each label has ≥3 symbols. The proof sketch (pruning pairs, collision-free exploration, first-moment argument) applies standard probabilistic-method tools directly to this model without any reduction of the target claim to fitted parameters, self-definitional equations, or load-bearing self-citations. The derivation is therefore self-contained against the stated inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the probabilistic model of independent uniform transitions and independent labels; these are domain assumptions rather than derived quantities.

axioms (2)
  • domain assumption All transition values are independent and uniform.
    Explicitly stated as the random transition model in the abstract.
  • domain assumption Each state is assigned an independent label specifying output and admissible symbols.
    Stated as part of the random model in the abstract.

pith-pipeline@v0.9.1-grok · 5670 in / 1263 out tokens · 17375 ms · 2026-06-26T14:55:10.971092+00:00 · methodology

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

18 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Bassino, J

    F. Bassino, J. David, C. Nicaud, On the Average Com- plexity of Moore’s State Minimization Algorithm, in: S. Albers, J.-Y. Marion (Eds.), 26th International Sym- posium on Theoretical Aspects of Computer Science, Vol. 3 of Leibniz International Proceedings in Infor- matics (LIPIcs), Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 200...

    2009

  2. [2]

    David, Average complexity of moore’s and hopcroft’s algorithms, Theoretical Computer Science 417 (2012) 50–65, mathematical Foundations of Computer Science (MFCS 2010)

    J. David, Average complexity of moore’s and hopcroft’s algorithms, Theoretical Computer Science 417 (2012) 50–65, mathematical Foundations of Computer Science (MFCS 2010)

    2012

  3. [3]

    Nicaud, Random deterministic automata, in: Inter- national Symposium on Mathematical Foundations of Computer Science, Springer, 2014, pp

    C. Nicaud, Random deterministic automata, in: Inter- national Symposium on Mathematical Foundations of Computer Science, Springer, 2014, pp. 5–23

    2014

  4. [4]

    Peled, M

    D. Peled, M. Y. Vardi, M. Yannakakis, Black box checking., J. Autom. Lang. Comb. 7 (2) (2002) 225– 246

    2002

  5. [5]

    A. Abel, J. Reineke, Gray-box learning of serial compo- sitions of mealy machines, in: NASA Formal Methods Symposium, Springer, 2016, pp. 272–287

    2016

  6. [6]

    Carrasco, F

    M. Carrasco, F. Mayr, S. Yovine, J. Kidd, M. Itur- bide, J. P. da Silva, A. Garat, Analyzing con- strained llm through pdfa-learning, arXiv preprint arXiv:2406.08269 (2024)

    work page arXiv 2024

  7. [7]

    Angluin, Learning regular sets from queries and counterexamples, Information and computation 75 (2) (1987) 87–106

    D. Angluin, Learning regular sets from queries and counterexamples, Information and computation 75 (2) (1987) 87–106

    1987

  8. [8]

    Bassino, J

    F. Bassino, J. David, A. Sportiello, Asymptotic enu- meration of minimal automata, in: 29th International Symposium on Theoretical Aspects of Computer Sci- ence, 2012, pp. 88–99

    2012

  9. [9]

    Babaali, C

    P. Babaali, C. Knaplund, On the construction of a family of automata that are generically non-minimal, in: A.-H. Dediu, C. Martín-Vide, B. Truthe (Eds.), Language and Automata Theory and Applications, Springer Berlin Heidelberg, Berlin, Heidelberg, 2013, pp. 80–91

    2013

  10. [10]

    Vidal, F

    E. Vidal, F. Thollard, C. De La Higuera, F. Casacu- berta, R. C. Carrasco, Probabilistic finite-state machines-part i, IEEE transactions on pattern analysis and machine intelligence 27 (7) (2005) 1013–1025

    2005

  11. [11]

    Balle, J

    B. Balle, J. Castro, R. Gavalda, Learning probabilistic automata: A study in state distinguishability, Theo- retical Computer Science 473 (2013) 46–60

    2013

  12. [12]

    Peyrière, Moore machines duality, Theoretical Com- puter Science 951 (2023) 113774

    J. Peyrière, Moore machines duality, Theoretical Com- puter Science 951 (2023) 113774

    2023

  13. [13]

    B. T. Willard, R. Louf, Efficient guided gener- ation for large language models, arXiv preprint arXiv:2307.09702 (2023)

    work page internal anchor Pith review Pith/arXiv arXiv 2023

  14. [14]

    Raspanti, T

    F. Raspanti, T. Ozcelebi, M. Holenderski, Grammar- constrained decoding makes large language models better logical parsers, in: Proceedings of the 63rd Annual Meeting of the Association for Computational Linguistics (Volume 6: Industry Track), 2025, pp. 485– 499

    2025

  15. [15]

    N. C. Wormald, The differential equation method for random graph processes and greedy algorithms, in: Lectures on Approximation and Randomized Algo- rithms, PWN, Warsaw, 1999, pp. 73–155

    1999

  16. [16]

    Bennett, A

    P. Bennett, A. Dudek, A gentle introduction to the dif- ferential equation method and dynamic concentration, Discrete Math. 345 (12) (2022) 17, id/No 113071

    2022

  17. [17]

    J.E.Hopcroft, J.D.Ullman, R.Motwani, Introduction to automata theory, languages, and computation., 2nd Edition, Reading, MA: Addison-Wesley, 2001

    2001

  18. [18]

    Carayol, C

    A. Carayol, C. Nicaud, Distribution of the number of accessible states in a random deterministic automa- ton, in: STACS’12 (29th Symposium on Theoretical Aspects of Computer Science), Vol. 14, LIPIcs, 2012, pp. 194–205. 9

    2012