A hierarchy of reversible finite automata

Alexander Okhotin; Maria Radionova

REVIEW 2 major objections 5 minor 17 references

A hierarchy of reversible finite automata

T0 review · 2 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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…

desk verdict Solid general-alphabet hierarchy with a genuine gap in the unary equality theorem; worth reviewing, but Theorem 4 needs a real fix. read the letter →

arxiv 2411.14538 v1 pith:7OWWICQL submitted 2024-11-21 cs.FL

Maria Radionova , Alexander Okhotin This is my paper · ORCID

classification cs.FL MSC 68Q45

keywords reversiblefiniteautomatasweepingpermutationmultipleinitialstatesexpressivepowerhierarchyoflanguagefamiliesunarypass-countcollapse

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the 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.

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

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

Referee Report

2 major / 5 minor

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.

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 (2)

[Section 5, Theorem 6 (and abstract)] 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 3, proof of Theorem 4] 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.

minor comments (5)

[Section 5, Example 3] 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 5, Example 4] 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 2, Lemma 1] 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 3, proof of Theorem 4] 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.
[Throughout] The abstract and body use 'sRF A' and 'MRF A' with a space in many places; this should be normalized to 'sRFA' and 'MRFA'.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the hierarchy proofs are self-contained constructions; the only self-citation is contextual and not load-bearing.

full rationale

The paper does not fit parameters to target data, and its main inclusions are established by explicit automata constructions (Lemma 3, Theorem 5) and by self-contained pumping and cycle arguments (Examples 1-4). Pin's Lemma 2 is an external cited lemma, and it is not actually used in the separating examples: Examples 2-4 argue directly from injectivity and cycles. The authors' prior result that 2PerFA equals 1PerFA [13] is mentioned only as motivation and is not invoked in any proof of the main hierarchy. A skeptical reviewer's concrete concern that the unary construction in Theorem 4 may violate injectivity of delta-subset is a correctness issue, not a circular dependency: no equation in the proof is equivalent to an input by construction, and no fitted parameter is renamed as a prediction. Accordingly, the derivation chain is self-contained, and the paper warrants a score of 0 for circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper's main results are unconditional hierarchy theorems. They rely on standard automata theory, the cited pumping lemma for MRFA, and the implicit halting property of reversible automata. No free parameters or invented entities appear.

assumptions (3)

domain assumption Pin's pumping lemma for reversible automata with multiple initial states (Lemma 2): if L is recognized by an MRFA and xy^+z ⊆ L for strings x, z and non-empty y, then xz ∈ L.
Cited from Pin [12] and used without proof in Examples 2 through 4 to show non-recognizability of a* ∪ b*, L_k, and the related languages.
domain assumption Halting and non-looping property of reversible computing devices: a computation of a reversible automaton over a finite input cannot revisit a configuration, otherwise it would loop forever and never accept; used in Example 2 to bound the number of end-marker turns.
This is implicit in the automaton model where acceptance requires the computation to end at an end-marker. It is used in the proof of Example 2 (Section 3) and underlies the cycle arguments in Section 5.
standard math Standard finite set theory and properties of partial injective functions (composition, domain size, extension to bijections on finite sets).
Used throughout the constructions in Lemma 3 and Theorem 5 without proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A hierarchy of reversible finite automata." pith.science (2026). https://pith.science/paper/7OWWICQL

@misc{pith2026241114538,
  author       = {Pith},
  title        = {Pith review of: A hierarchy of reversible finite automata},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7OWWICQL}},
  note         = {Machine review of arXiv:2411.14538}
}

abstract

In this paper, different variants of reversible finite automata are compared, and their hierarchy by the expressive power is established. It is shown that one-way reversible automata with multiple initial states (MRFA) recognize strictly more languages than sweeping reversible automata (sRFA), which are in turn stronger than one-way reversible automata with a single initial state (1RFA). The latter recognize strictly more languages than one-way permutation automata (1PerFA). It is also shown that the hierarchy of sRFA by the number of passes over the input string collapses: it turns out that three passes are always enough. On the other hand, MRFA form a hierarchy by the number of initial states: their subclass with at most $k$ initial states (MRFA$^k$) recognize strictly fewer languages than MRFA$^{k + 1}$, and also MRFA$^k$ are incomparable with sRFA. In the unary case, sRFA, MRFA$^k$ and MRFA become equal in their expressive power, and the inclusion of 1RFA into sRFA remains proper.

Figures

Figures reproduced from arXiv: 2411.14538 by the authors.

**Figure 2.** Hierarchy in the unary case. question about relative expressive power of MRFA and sRFA is also studied: sweeping reversible automata can be simulated by reversible automata with multiple initial states, whereas a converse simulation is not always possible. A hierarchy in the unary case is also investigated in Section 3. For the majority of models, the results about their expressive power are the same as for unrestri… view at source ↗

**Figure 3.** Computations of an sRFA recognizing the language ( [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

Figures from the paper (2 more)

**Figure 4.** Figure 4: Constructing the function f from the function g. It is obtained, that the pair (p, f) satisfies both properties for the string u, and hence, by the induction hypothesis, this pair is reachable in the MRFA by the string u from one of its initial states. Also, it is know…

**Figure 5.** Figure 5: Cycles in sRFA follows that the state (q, g) is indeed reachable by the string v. Now let us show the mutual containment between the languages recognized by the sRFA and by the constructed MRFA. For the given string s, the computation of the sRFA on it is accepting if…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

17 extracted references · 16 canonical work pages

[1]

Inference of Reversible Languages

D. Angluin, “Inference of Reversible Languages”, Journal of the ACM , 29:3 (1982), 741–765

work page 1982
[2]

PSPACE-complete problems for subgroups of free groups and inverse finite automata

J.-C. Birget, S. W. Margolis, J. C. Meakin, P. Weil, “PSPACE-complete problems for subgroups of free groups and inverse finite automata”,The- oretical Computer Science, 242:1–2 (2000), 247–281

work page 2000
[3]

A Lower Bound For Reversible Automata

P.-C. H´ eam, “A Lower Bound For Reversible Automata”,RAIRO The- oretical Informatics and Applications , 34(5):331–341 (2000)

work page 2000
[4]

Minimal and hyper-minimal biautomata

M. Holzer, S. Jakobi, “Minimal and hyper-minimal biautomata”, In- ternational Journal of Foundations of Computer Science , 27:2 (2016), 161–186

work page 2016
[5]

Minimal Reversible Deterministic Finite Automata

M. Holzer, S. Jakobi, M. Kutrib, “Minimal Reversible Deterministic Finite Automata”, International Journal of Foundations of Computer Science 29:2 (2018), 251–270

work page 2018
[6]

On the state complexity of k-entry deterministic finite automata

M. Holzer, K. Salomaa, S. Yu, “On the state complexity of k-entry deterministic finite automata”, Journal of Automata, Languages and Combinatorics, 6:4 (2001), 453–466

work page 2001
[7]

Operations on Permutation Automata

M. Hospod´ ar, P. Mlyn´ arˇ cik, “Operations on Permutation Automata”, DLT 2020, LNCS 12086, 122–136. 28

work page 2020
[8]

Decomposing Permutation Au- tomata

I. Jecker, N. Mazzocchi, P. Wolf, “Decomposing Permutation Au- tomata”, CONCUR 2021, LIPIcs 203, 18:1–18:19

work page 2021

Show all 17 references

[9]

On the power of quantum finite state au- tomata

A. Kondacs, J. Watrous, “On the power of quantum finite state au- tomata”, 38th Annual Symposium on Foundations of Computer Science (FOCS 1997, Miami Beach, Florida, USA, 19–22 October 1997), IEEE, 66–75

1997
[10]

Irreversibility and heat generation in the computing pro- cess

R. Landauer, “Irreversibility and heat generation in the computing pro- cess”, IBM Journal of Research and Development, 5(3):183—191 (1961)

1961
[11]

GF(2)-operations on basic families of formal languages

A. Okhotin, M. Radionova, E. Sazhneva, “GF(2)-operations on basic families of formal languages”, Theoretical Computer Science, 995 (2024), article 114489

2024
[12]

On the Language Accepted by Finite Reversible Automata

J.- ´E. Pin, “On the Language Accepted by Finite Reversible Automata”, Automata, Languages and Programming, 14th International Colloquium, (ICALP 1987, Karlsruhe, Germany, July 13–17, 1987), LNCS 267, 237– 249

1987
[13]

Sweeping permutation automata

M. Radionova, A. Okhotin, “Sweeping permutation automata”, Pro- ceedings of the 13th International Workshop on Non-Classical Models of Automata and Applications (NCMA 2023, Famagusta, North Cyprus, 18–19 September 2023), EPTCS 388, 110–124

2023
[14]

On the accepting state complexity of operations on permutation automata

C. Rauch, M. Holzer, “On the accepting state complexity of operations on permutation automata”, RAIRO Theoretical Informatics and Appli- cations, 57:9 (2023)

2023
[15]

The reduction of two-way automata to one-way automata

J. C. Shepherdson, “The reduction of two-way automata to one-way automata”, IBM Journal of Research and Development , 3 (1959), 198– 200

1959
[16]

Lower bounds on the size of sweeping automata

M. Sipser, “Lower bounds on the size of sweeping automata”, Journal of Computer and System Sciences , 21:2 (1980), 195–202. https://doi. org/10.1016/0022-0000(80)90034-3

1980 doi
[17]

Permutation Automata

G. Thierrin, “Permutation Automata”, Mathematical Systems Theory , 2:1 (1968), 83–90. 29

1968

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Inference of Reversible Languages

D. Angluin, “Inference of Reversible Languages”, Journal of the ACM , 29:3 (1982), 741–765

work page 1982

[2] [2]

PSPACE-complete problems for subgroups of free groups and inverse finite automata

J.-C. Birget, S. W. Margolis, J. C. Meakin, P. Weil, “PSPACE-complete problems for subgroups of free groups and inverse finite automata”,The- oretical Computer Science, 242:1–2 (2000), 247–281

work page 2000

[3] [3]

A Lower Bound For Reversible Automata

P.-C. H´ eam, “A Lower Bound For Reversible Automata”,RAIRO The- oretical Informatics and Applications , 34(5):331–341 (2000)

work page 2000

[4] [4]

Minimal and hyper-minimal biautomata

M. Holzer, S. Jakobi, “Minimal and hyper-minimal biautomata”, In- ternational Journal of Foundations of Computer Science , 27:2 (2016), 161–186

work page 2016

[5] [5]

Minimal Reversible Deterministic Finite Automata

M. Holzer, S. Jakobi, M. Kutrib, “Minimal Reversible Deterministic Finite Automata”, International Journal of Foundations of Computer Science 29:2 (2018), 251–270

work page 2018

[6] [6]

On the state complexity of k-entry deterministic finite automata

M. Holzer, K. Salomaa, S. Yu, “On the state complexity of k-entry deterministic finite automata”, Journal of Automata, Languages and Combinatorics, 6:4 (2001), 453–466

work page 2001

[7] [7]

Operations on Permutation Automata

M. Hospod´ ar, P. Mlyn´ arˇ cik, “Operations on Permutation Automata”, DLT 2020, LNCS 12086, 122–136. 28

work page 2020

[8] [8]

Decomposing Permutation Au- tomata

I. Jecker, N. Mazzocchi, P. Wolf, “Decomposing Permutation Au- tomata”, CONCUR 2021, LIPIcs 203, 18:1–18:19

work page 2021