{"id":"ef99f547-124d-4bee-b590-022bb8dc4f21","arxiv_id":"2411.14538","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Reversible automata with multiple initial states recognize more languages than sweeping reversible automata, which recognize more than single-start one-way reversible automata and permutation automata.","lead":"This paper compares the expressive power of several variants of reversible finite automata, establishing a strict hierarchy among them. It shows that sweeping reversible automata sit between one-way reversible automata and reversible automata with multiple starting states, and that three passes always suffice for sweeping automata.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The general-alphabet hierarchy (Theorem 3) appears sound, but the proof of Theorem 4 (unary sRFA = MRFA) has a concrete gap: the construction implicitly sends multiple non-accepting first-pass states to one backward-path state, violating the injectivity of δ⊣ required by Definition 5.","rationale":"I read the paper in good faith and checked the arguments supporting Theorem 3, the central general-alphabet hierarchy. Lemma 3's transformation of sRFA to MRFA is detailed and its reversibility claim (Claim 1) is valid: the domain-preservation condition exactly prevents the MRFA from computing an irreversible forget. Example 2's non-recognizability of a* ∪ b* by sRFA is a standard reversible-cycle argument and is convincing. Therefore the reader's weakest-assumption, Pin's Lemma 2, is not the load-bearing point for the main separations; Examples 3 and 4 in Section 5 do not use that lemma. The genuine concern I found is in Theorem 4, the unary equality. The construction as printed defines a single Q−-path and implicitly needs δ⊣ to send every non-accepting first-pass state into that path. Definition 5 requires δ⊣ to be injective, and the natural interpretation violates this. Since the paper's abstract explicitly advertises the unary collapse sRFA = MRFA^k = MRFA, this is a load-bearing gap for the paper's full set of claims, even though the general-alphabet hierarchy survives. A referee should ask for a corrected construction or a proof that an injective δ⊣ can be chosen. I therefore recommend conditional acceptance rather than unconditional acceptance; the central theorem does not need to be rejected, but the unary theorem's proof must be repaired.","tokens_in":17267,"tokens_out":31851,"duration_ms":322442,"concrete_test":"Instantiate Theorem 4 with L = (a^3)^* ∪ {a, a^2} over a unary alphabet. The permutation part has states r0,r1,r2 on an a-cycle with accepting set E={r0}, and ℓ=2. The strings a and a^2 end in r1 and r2 respectively, both non-accepting, so both must turn at the right end-marker and use the single backward path to accept. Write down the required partial function δ⊣; any injective δ⊣ with image in {q1,q2,q3} must map r1 and r2 to distinct states, and the printed acceptance condition F∩Q− = {q_i | a^{i-1}∈L(A)} must then be checked for both lengths. Try the obvious repair with one backward path for each non-accepting first-pass state and verify that all end-marker and symbol transitions remain injective. If such a repair exists, Theorem 4 needs only a corrected construction; if not, the unary result is false.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The reader's identified weak point, Pin's Lemma 2, is not actually load-bearing for the separations: Examples 3 and 4 prove their lower bounds by a self-contained injective-cycle/pigeonhole argument (if an initial state accepts infinitely many words from (ab^i)^*, injectivity of the transition by (ab^i)^c forces that initial state onto a cycle), and they never invoke Lemma 2. The real gap is in Theorem 4. To recognize L(A) = L(B) ∪ L≤ℓ, the proof defines Q− as a single path q1,...,qℓ+1 and has the automaton turn at the right end-marker after a rejecting first pass to test L≤ℓ on the way back. This requires defining δ⊣ on every non-accepting first-pass state that can occur for a short accepted word. With the natural completion δ⊣(p)=q1 for all such p, injectivity of δ⊣ fails as soon as two distinct non-accepting states are reached. The proof gives no alternative injective assignment of first-pass states to starting positions in the single path, and it does not replicate the path per state. Thus the unary equality claimed in Theorem 4 (and in the abstract) is not established as written. This does not undermine the general-alphabet chain 1PerFA ⊊ 1RFA ⊊ sRFA ⊊ MRFA, whose proofs appear coherent and sound.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper compares the expressive power of reversible finite automata variants: one-way permutation automata (1PerFA), one-way reversible automata (1RFA), sweeping reversible automata (sRFA), and one-way reversible automata with multiple initial states (MRFA). The claimed results are the chain 1PerFA ⊊ 1RFA ⊊ sRFA ⊊ MRFA, a collapse of the sRFA pass hierarchy to three passes, a strict hierarchy MRFA^k ⊊ MRFA^{k+1}, incomparability of MRFA^k with sRFA, and, in the unary case, equality of sRFA, MRFA^k and MRFA with 1RFA still properly contained. The main technical tools are a behavior-function simulation of sRFA by MRFA and pumping/pigeonhole separations.","tokens_in":17542,"tokens_out":19646,"duration_ms":181001,"significance":"If the results hold, the paper settles the relative expressive power of the principal reversible finite automata models and adds two natural hierarchy results (pass count and number of initial states). The general-alphabet inclusions and separations are supported by detailed proofs, and the simulation of sRFA by MRFA (Lemma 3) is carefully argued. The three-pass construction (Theorem 5) is elaborate and, on reading, coherent. The weaknesses are concentrated in the unary equality proof and in the unqualified statement of Theorem 6; neither undermines the main general-alphabet chain, but both must be fixed before the paper can be accepted.","major_comments":[{"comment":"The statement that MRFA^k are incomparable with sRFA is false for k=1. Since MRFA^1 is exactly 1RFA, Theorem 2 proves L(1RFA) ⊊ L(sRFA), i.e., MRFA^1 is strictly contained in sRFA and therefore not incomparable with it. The theorem should be restricted to k ≥ 2, or the k=1 case should be stated as a strict containment. The same qualification is needed in the abstract, which currently claims incomparability without any restriction on k.","section":"Section 5, Theorem 6 (and abstract)"},{"comment":"The construction of an sRFA for L(B) ∪ L≤ℓ is not a valid sweeping reversible automaton as written. The proof sets Q− to the single path q1,...,q_{ℓ+1} and uses it to test L≤ℓ on the way back, but it never defines the end-marker transition δ⊣. To test L≤ℓ after a rejecting first pass, δ⊣ must map every non-accepting state of Q+ = P that is reachable at the right end-marker into Q−. The natural mapping δ⊣(p)=q1 for all such p violates the injectivity required by Definition 5. Any injective mapping into a single path changes the starting point of the backward test, so the final state after reading a^m is q_{j+m}, and the acceptance condition a^{j+m-1} ∈ L(A) no longer coincides with the required condition a^m ∈ L≤ℓ; a unary permutation automaton B can easily have several non-accepting states on its cycle, so the issue is not vacuous. For example, with B a 4-cycle accepting even lengths and L≤ℓ = {a, a^3}, two non-accepting states require different starting positions, but a single path cannot accommodate both. The proof would need either one path per non-accepting state or an explicit injective assignment with a matching acceptance condition; neither is supplied. Consequently, the unary equality claimed in Theorem 4 and in the abstract is not established as written.","section":"Section 3, proof of Theorem 4"}],"minor_comments":[{"comment":"The sentence 'the state qi itself must be accepting' is false in general, since an initial state can accept infinitely many words from a cycle without itself being accepting (e.g., a two-state automaton accepting odd-length words). The contradiction does not actually require qi to be accepting, so the sentence should be removed or corrected. Also, 'loops in qi by a string ab^i' should read 'by some power of ab^i'; the following sentence does say 'some power', so this is mainly a wording issue.","section":"Section 5, Example 3"},{"comment":"The lower-bound proof has the same imprecision as Example 3: 'there is a cycle by the string ab^i in qi' should say 'by some power of ab^i'.","section":"Section 5, Example 4"},{"comment":"Lemma 1 is presented only as 'a sketch of a proof'. Since the conversion from acceptance at both end-markers to acceptance at one side is used in the proof of Theorem 4 and in Example 4, the authors should give the full construction and explicitly verify that the modified δ⊢ remains injective.","section":"Section 2, Lemma 1"},{"comment":"The end-marker transitions δ⊢ and δ⊣ of the constructed sRFA are never written out; this omission is the direct source of the gap described in Major Comment 2, and the proof should be completed by defining them explicitly.","section":"Section 3, proof of Theorem 4"},{"comment":"The abstract and body use 'sRF A' and 'MRF A' with a space in many places; this should be normalized to 'sRFA' and 'MRFA'.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper is a good fit for the journal and the main general-alphabet hierarchy is likely correct. The two load-bearing issues are the unary equality construction in Theorem 4 and the k=1 overstatement in Theorem 6; neither appears to be a fundamental flaw, so I recommend major revision rather than rejection. The reader's report is largely accurate, but it overlooks the k=1 problem in Theorem 6."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my take. The main results for general alphabets look right: Theorem 3 gives the strict chain 1PerFA ⊊ 1RFA ⊊ sRFA ⊊ MRFA, with Example 2 (a*∪b*) as a clean witness that sRFA can't do; Lemma 3's simulation of sRFA by MRFA is detailed and the reversibility argument holds. Theorem 5's three-pass collapse is elaborate and plausible; I didn't find an error. Section 5's k-initial-state hierarchy (Theorem 6) is also new, and the proofs in Examples 3 and 4 are self-contained injective-cycle/pigeonhole arguments—they don't rely on Pin's Lemma 2, contrary to what might be feared. So the reader's worry about the pumping lemma as a black box is not real.\n\nThe soft spot is Theorem 4, the unary equality sRFA = MRFA. The construction as written defines Q− as one path q1,...,q_{ℓ+1} and says the automaton checks L≤ℓ on the way back. But it never specifies δ⊣ injectively. If multiple non-accepting states in Q+ after the first pass all need to turn into the same Q− path, the natural completion δ⊣(p)=q1 for every such p violates injectivity, and the proof gives no alternative assignment or replicated paths. This is a concrete gap, not a missing detail: the unary equality, which the abstract advertises, is not established as written. The rest of the hierarchy does not depend on it, so the main chain survives, but the paper overclaims in the unary case. Lemma 1 is also only sketched, but that one is fixable and minor; Example 3 has a small imprecision about looping, also minor.\n\nWho is this for? People working on reversible automata and expressiveness hierarchies. It's a niche subfield, but the questions are natural and the general-alphabet results are a solid step. I'd send it to a serious referee: it deserves review because the core is strong and the gap in Theorem 4 is identifiable and likely repairable. But acceptance should be conditional on fixing that proof.","headline":"Solid general-alphabet hierarchy with a genuine gap in the unary equality theorem; worth reviewing, but Theorem 4 needs a real fix.","tokens_in":18104,"tokens_out":2993,"would_cite":true,"duration_ms":27701,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q45"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that sweeping reversible automata recognize strictly more languages than one-way reversible automata and strictly fewer than one-way reversible automata with multiple initial states, and that every additional initial…","keywords":["reversible finite automata","sweeping automata","permutation automata","multiple initial states","expressive power","hierarchy of language families","unary automata","pass-count collapse"],"falsifier":"Build an explicit sweeping reversible automaton that accepts $a^* \\cup b^*$; Example 2 claims none exists, so one working example would refute Theorem 3. Alternatively, for some $k$, build an MRFA with at most $k$ initial states accepting $\\bigcup_{i=1}^{k+1}(ab^i)^*$; Example 3 claims this is impossible, so it would refute Theorem 6.","tokens_in":17033,"feed_emoji":"🔁","tokens_out":13991,"duration_ms":116324,"temperature":0.7,"pith_summary":"This paper sets out to determine which reversible finite automaton models are more expressive than which. It proves a strict chain of language families: one-way permutation automata, where every symbol acts as a permutation of the states, recognize fewer languages than one-way reversible automata with one initial state, which recognize fewer than sweeping reversible automata that may scan the input back and forth, which in turn recognize fewer than one-way reversible automata with several allowed starting states. Along the way it proves that every additional starting state adds power, that any sweeping reversible automaton can be replaced by one making at most three passes, and that over a one-letter alphabet the sweeping and multi-start models coincide. The result matters because reversible computation is the known route around the thermodynamic cost of erasing bits, so knowing exactly what these models can and cannot recognize bounds what reversible hardware could in principle compute.","feed_headline":"Strict hierarchy proven for reversible finite automata","feed_subtitle":"One-way, sweeping and multi-start reversible automata are nested, and three passes always suffice.","key_machinery":"The load-bearing construction is the behavior function of a sweeping automaton: a partial injective function $f\\colon Q^- \\to Q^+$ recording, for each state at the right end of an already read prefix, where the automaton ends after reading that prefix from right to left and then from left to right. A one-way MRFA simulates an sRFA by storing a pair $(p,f)$, guessing the domain of $f$ among its initial states, and allowing a transition on a symbol only when the domain size remains unchanged; any transition that would shrink the domain is left undefined, which preserves injectivity. The three-pass normalization uses the same function after arbitrarily completing the sRFA to a permutation automaton, checks on the backward pass that no undefined transition is needed, and then uses the third pass only to accept.","core_discovery":"The central discovery is a strict expressiveness hierarchy among deterministic reversible automata: $L(\\mathrm{1PerFA}) \\subsetneq L(\\mathrm{1RFA}) \\subsetneq L(\\mathrm{sRFA}) \\subsetneq L(\\mathrm{MRFA})$, where $\\mathrm{1PerFA}$ are one-way permutation automata, $\\mathrm{1RFA}$ are one-way reversible automata with one initial state, $\\mathrm{sRFA}$ are sweeping reversible automata, and $\\mathrm{MRFA}$ are one-way reversible automata with multiple initial states. The paper proves the new inclusions $\\mathrm{1RFA} \\subsetneq \\mathrm{sRFA}$ (Theorem 2) and $\\mathrm{sRFA} \\subsetneq \\mathrm{MRFA}$ (Theorem 3), shows that the classes $\\mathrm{MRFA}^k$ with at most $k$ initial states form a strict hierarchy and are each incomparable with $\\mathrm{sRFA}$ (Theorem 6), and shows that the number of passes of an $\\mathrm{sRFA}$ collapses to three (Theorem 5). In the unary case, $\\mathrm{sRFA}$ and $\\mathrm{MRFA}$ recognize exactly the same languages (Theorem 4); the paper also proves the finer inclusions and incomparabilities among single-accepting variants in Theorem 1.","pith_inferences":["Editorial extension: the domain-guessing construction suggests a succinctness question not addressed in the paper: how large must an $\\mathrm{MRFA}$ be compared with the $\\mathrm{sRFA}$ it simulates, and is the state blow-up unavoidable?","Editorial extension: the same behavior-function method could be applied to other reversible models with direction changes, such as tree-walking automata, to see whether similar pass-count collapses hold.","Editorial extension: because the unary hierarchy collapses, the initial-state hierarchy is essentially a two-symbol phenomenon; it would be natural to test where the hierarchy begins as the alphabet grows from one symbol to two.","Editorial extension: the three-pass normalization is for deterministic automata; a nondeterministic or probabilistic variant of sweeping reversible automata may not collapse in the same way."],"forward_implications":["Every language recognized by an $\\mathrm{sRFA}$ is recognized by an $\\mathrm{MRFA}$, and the reverse fails: sweeping reversibility is strictly weaker than multiple allowed starting states.","The MRFA pumping lemma now applies to every $\\mathrm{sRFA}$ language: if $xy^+z$ lies in the language with $y$ nonempty, then so does $xz$.","The number of passes over the input is not an expressive resource for sweeping reversible automata beyond three passes.","Each additional allowed initial state in an $\\mathrm{MRFA}$ adds languages, and for each fixed $k$, $\\mathrm{MRFA}^k$ and $\\mathrm{sRFA}$ are incomparable.","Over a unary alphabet, sweeping reversibility gives no expressive advantage over one-way multi-start reversibility."],"supporting_citations":[{"why":"Defines the MRFA model with multiple initial states and supplies the pumping lemma (Lemma 2) the paper applies to prove non-representability and extends to all sRFA languages.","marker":"[12]"},{"why":"Introduces one-way reversible automata with a single initial state, the base class that Theorem 1 and Theorem 2 separate from stronger models.","marker":"[1]"},{"why":"Provides the classical behavior-function reduction of sweeping automata to one-way automata that the simulations in Lemma 3 and Theorem 5 adapt.","marker":"[15]"},{"why":"Shows sweeping permutation automata recognize exactly the one-way permutation languages, the contrast that highlights the extra power of sweeping reversible automata.","marker":"[13]"}],"fun_headline_variants":["Reversible automata: strict hierarchy, three passes enough","Three passes always suffice in sweeping reversible automata","Multi-start reversible automata top the hierarchy","Unary reversible automata: sweeping equals multi-start","Incomparability emerges in reversible automata hierarchy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The hierarchy assumes that a finite reversible automaton accepting infinitely many strings from a periodic set must contain a cycle reachable from one initial state, so that a single initial state cannot serve two independent periodic families without also accepting a mixed string outside the target language.","fun_headline_variants_meta":{"raw":{"variants":["Reversible automata: strict hierarchy, three passes enough","Three passes always suffice in sweeping reversible automata","Multi-start reversible automata top the hierarchy","Unary reversible automata: sweeping equals multi-start","Incomparability emerges in reversible automata hierarchy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000683,"raw_usage":{"total_tokens":3134,"prompt_tokens":1011,"completion_tokens":2123,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":627,"completion_tokens_details":{"reasoning_tokens":2050}},"tokens_in":627,"tokens_out":2123,"duration_ms":12823,"temperature":1.0,"reasoning_tokens":2050,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:10:29.142012+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Build an explicit sweeping reversible automaton that accepts $a^* \\cup b^*$; Example 2 claims none exists, so one working example would refute Theorem 3. Alternatively, for some $k$, build an MRFA with at most $k$ initial states accepting $\\bigcup_{i=1}^{k+1}(ab^i)^*$; Example 3 claims this is impossible, so it would refute Theorem 6.","supporting_citations":[{"cited_title":"On the Language Accepted by Finite Reversible Automata","cited_arxiv_id":null,"evidence_quote":"Defines the MRFA model with multiple initial states and supplies the pumping lemma (Lemma 2) the paper applies to prove non-representability and extends to all sRFA languages."},{"cited_title":"Inference of Reversible Languages","cited_arxiv_id":null,"evidence_quote":"Introduces one-way reversible automata with a single initial state, the base class that Theorem 1 and Theorem 2 separate from stronger models."},{"cited_title":"The reduction of two-way automata to one-way automata","cited_arxiv_id":null,"evidence_quote":"Provides the classical behavior-function reduction of sweeping automata to one-way automata that the simulations in Lemma 3 and Theorem 5 adapt."},{"cited_title":"Sweeping permutation automata","cited_arxiv_id":null,"evidence_quote":"Shows sweeping permutation automata recognize exactly the one-way permutation languages, the contrast that highlights the extra power of sweeping reversible automata."}],"review_version":1}