pith. machine review for the scientific record. sign in

arxiv: 2604.25398 · v1 · submitted 2026-04-28 · 💻 cs.FL

Recognition: unknown

Hamming distance between finite transducers

Isma\"el Jecker, Luc Dartois, Pierre-Cyrille H\'eam, Silvio Vescovo

Authors on Pith no claims yet

Pith reviewed 2026-05-07 13:41 UTC · model grok-4.3

classification 💻 cs.FL
keywords Hamming distancefinite transducersbounded comparisonNL-completeco-NP-completeDP-completecomputational complexity
0
0 comments X

The pith

Deciding whether two finite transducers produce outputs at Hamming distance at most k for every input is NL-complete when k is fixed and co-NP-complete when k is given in binary.

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

The paper classifies the computational complexity of checking whether two non-deterministic finite transducers always stay within a Hamming distance of k on their outputs for any input. It proves that the bounded comparison problem is NL-complete for fixed k, co-NP-complete when k appears in binary in the input, and DP-complete when deciding whether the distance equals exactly k. The paper further shows that any pair of transducers with bounded comparison has maximum Hamming distance at most quadratic in their sizes, and that this quadratic bound is asymptotically tight. The same complexity results hold for the related deviations problem on a single transducer, and the two families of problems are equivalent under logspace reductions.

Core claim

The bounded comparison problem for the Hamming distance between outputs of two transducers is NL-complete for constant k, co-NP-complete for k given in binary, and deciding whether the distance is exactly k is DP-complete. When the comparison is bounded, the maximal distance is at most quadratic in the sizes of the two transducers and this bound is tight. The analogous questions for the deviations of a single transducer are logspace equivalent to the comparison problems.

What carries the argument

The bounded comparison problem, which asks whether the Hamming distance between the outputs of two transducers is at most k for every input word.

If this is right

  • The problem admits nondeterministic logspace algorithms when k is fixed.
  • Practical verification must account for co-NP hardness once k is part of the input.
  • The quadratic bound makes it feasible to compute the exact maximum distance in polynomial time whenever the comparison is bounded.
  • All results carry over to the single-transducer deviations problem via the logspace equivalence.

Where Pith is reading between the lines

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

  • The same complexity landscape may appear for other output metrics such as Levenshtein distance.
  • The quadratic bound implies that bounded transducers can be compared by enumerating a polynomial number of critical paths.
  • Heuristics for transducer comparison in verification tools can exploit the NL algorithm for small fixed k.
  • The logspace equivalence suggests that comparison and deviation problems share the same structural properties inside automata theory.

Load-bearing premise

The transducers are non-deterministic finite transducers over finite alphabets and the Hamming distance between their output words is well-defined for every input.

What would settle it

A pair of transducers with bounded comparison whose maximum output Hamming distance exceeds the square of their combined sizes, or a deterministic logspace algorithm for the bounded comparison problem when k is given in binary.

read the original abstract

We study bounded deviation of non-deterministic finite transducers under the Hamming distance: the bounded comparison problem asks, given two transducers and $k \in \mathbb{N}$, whether for every input the two transducers produce words at Hamming distance at most $k$. This problem is known to be decidable in polynomial time when $k$ is fixed, and in co-NP otherwise. We show that the problem is NL-complete when $k$ is fixed, co-NP-complete when $k$ is given in binary, and it is DP-complete to decide if the distance is exactly $k$. We also prove that if the two transducers have bounded comparison, then the maximal distance is at most quadratic in the size of both transducers, and that this bound is asymptotically tight. We prove the results on deviations problem, which asks similar questions on the distance of the pairs of input and output of a single transducer, and show that these two families of problems are logspace many-one equivalent.

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 paper examines the bounded comparison problem for non-deterministic finite transducers with respect to the Hamming distance between their output words for the same input. It establishes that this problem is NL-complete for fixed k, co-NP-complete for k given in binary, and that deciding if the distance is exactly k is DP-complete. The authors also show a quadratic upper bound on the maximal distance under bounded comparison, prove it is tight, and demonstrate logspace equivalence to the deviations problem for a single transducer.

Significance. If these results are correct, they offer a refined and complete picture of the computational complexity of transducer comparison under Hamming distance, improving upon previously known polynomial and co-NP bounds. The proof of a tight quadratic bound on the distance provides quantitative insight into transducer behavior, and the logspace equivalence between comparison and deviation problems is a notable technical achievement that allows results to transfer between the two settings. These findings are significant for the field of automata theory and formal verification.

minor comments (2)
  1. [Abstract] The abstract states that the maximal distance is 'at most quadratic' and 'asymptotically tight' but does not reference the specific theorem or construction establishing the lower bound; adding a pointer would improve readability.
  2. The weakest assumption on well-defined Hamming distance for variable-length outputs is acknowledged but would benefit from an explicit definition or example of how padding or alignment is handled in the problem setup.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading and positive assessment of our work, including the accurate summary of our results on the complexity of bounded Hamming-distance comparison for transducers and the tight quadratic bound. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The derivation relies on explicit reductions to established complexity classes (NL, co-NP, DP) and standard automata constructions for the quadratic bound and logspace equivalence between bounded comparison and deviations problems. These steps are independent of self-citations or self-definitions; prior decidability results are cited as background without load-bearing circularity. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard automata theory without introducing new free parameters or invented entities.

axioms (1)
  • domain assumption Non-deterministic finite transducers are standard models whose comparison problems are amenable to complexity analysis via reductions.
    The bounded comparison and deviations problems are defined directly on these models.

pith-pipeline@v0.9.0 · 5474 in / 1202 out tokens · 52118 ms · 2026-05-07T13:41:48.529299+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

11 extracted references · 10 canonical work pages

  1. [1]

    Edit Distance of Finite State Transducers

    1 C. Aiswarya, Amaldev Manuel, and Saina Sunny. Edit distance of finite state transducers. In51st International Colloquium on Automata, Languages, and Programming, ICALP 2024, Tallinn, Estonia, July 8-12, 2024, LIPIcs, pages 125:1–125:20. Schloss Dagstuhl - Leibniz- Zentrum für Informatik, 2024.doi:10.4230/LIPICS.ICALP.2024.125. 2 C. Aiswarya, Amaldev Man...

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

  2. [2]

    3 Christian Choffrut and Giovanni Pighizzini

    URL:https://arxiv.org/abs/2404.16518,arXiv:2404.16518. 3 Christian Choffrut and Giovanni Pighizzini. Distances between languages and reflexivity of relations.Theor. Comput. Sci., 286(1):117–138,

    work page arXiv

  3. [3]

    4 Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, and Saina Sunny

    doi:10.1016/S0304-3975(01)00238-9. 4 Emmanuel Filiot, Ismaël Jecker, Khushraj Madnani, and Saina Sunny. Approximate problems for finite transducers. In52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark, July 8-11, 2025, LIPIcs, pages 155:1–155:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.doi:1...

    work page doi:10.1016/s0304-3975(01)00238-9 2025

  4. [4]

    Transducers, logic and algebra for functions of finite words.ACM SIGLOG News, 3(3):4–19, 2016.doi:10.1145/2984450.2984453

    5 Emmanuel Filiot and Pierre-Alain Reynier. Transducers, logic and algebra for functions of finite words.ACM SIGLOG News, 3(3):4–19, 2016.doi:10.1145/2984450.2984453. 6 Seymour Ginsburg and Gene F. Rose. A characterization of machine mappings.Journal of Symbolic Logic, 33(3):468–468, 1968.doi:10.2307/2270340. 7 R. W. Hamming. Error detecting and error cor...

    work page doi:10.1145/2984450.2984453 2016

  5. [5]

    Computing the edit-distance between a regular language and a context-free language

    9 Yo-Sub Han, Sang-Ki Ko, and Kai Salomaa. Computing the edit-distance between a regular language and a context-free language. In Hsu-Chun Yen and Oscar H. Ibarra, editors, Developments in Language Theory , DLT 2012, Lecture Notes in Computer Science, pages 85–96. Springer, 2012.doi:10.1007/978-3-642-31653-1\_9. 10 Thomas A. Henzinger, Jan Otop, and Roops...

    work page doi:10.1007/978-3-642-31653-1 2012

  6. [6]

    Edit-distance of weighted automata: General definitions and algorithms.Int

    13 Mehryar Mohri. Edit-distance of weighted automata: General definitions and algorithms.Int. J. Found. Comput. Sci., 14(6):957–982, 2003.doi:10.1142/S0129054103002114. 14 Anca Muscholl and Gabriele Puppis. The many facets of string transducers (invited talk). In36th International Symposium on Theoretical Aspects of Computer Science STACS 2019, volume 126...

    work page doi:10.1142/s0129054103002114 2003

  7. [7]

    16Christos H

    doi: 10.1016/0022-0000(84)90068-0. 16Christos H. Papadimitriou.Computational complexity.Addison-Wesley,

    work page doi:10.1016/0022-0000(84)90068-0

  8. [8]

    18 Hiroaki Sakoe and Seibi Chiba

    doi: 10.1145/320924.320930. 18 Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition.IEEE Transactions on Acoustics, Speech, and Signal Processing, pages 43–49,

    work page doi:10.1145/320924.320930

  9. [9]

    Dartois, P.-C

    L. Dartois, P.-C. Héam, I. Jecker, and S. Vescovo 15 19 Roopsha Samanta, Jyotirmoy V. Deshmukh, and Swarat Chaudhuri. Robustness ana- lysis of string transducers. InATV A 2013, pages 427–441. Springer, 2013.doi:10.1007/ 978-3-319-02444-8\_30. 20 Helena Skutkova, Martin Vítek, Petr Babula, René Kizek, and Ivo Provazník. Classification of genomic signals us...

    work page doi:10.1186/1471-2105-14-s10-s1 2013

  10. [10]

    22 Róbert Szelepcsényi

    available athttps://saisunny1994.github.io/. 22 Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata.Acta Informatica, 26(3):279–284, 1988.doi:10.1007/BF00299636. 23 T. K. Vintsyuk. Speech discrimination by dynamic programming.Cybernetics, 4:52–57,

    work page doi:10.1007/bf00299636 1988

  11. [11]

    Russian Kibernetika 4(1):81-88 (1968). 16 Hamming distance between finite transducers A Proofs for Section 2 (Preliminaries) A.1 Input-atomic transducer We introduce the notion ofinput-atomic transduceras it will be used to simplify some proofs in the Section

    1968