pith. machine review for the scientific record. sign in

arxiv: 2605.06269 · v1 · submitted 2026-05-07 · 💻 cs.FL · cs.LO

Recognition: unknown

Edit Distance of Finite-Valued Transducers

Prince Mathew, Saina Sunny

Authors on Pith no claims yet

Pith reviewed 2026-05-08 03:23 UTC · model grok-4.3

classification 💻 cs.FL cs.LO
keywords edit distancefinite-valued transducerscomputabilityword transducersfunctional transducersautomatarelations over words
0
0 comments X

The pith

The edit distance between finite-valued transducers is computable.

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 minimal number of edits needed to transform all outputs of one finite-valued transducer into outputs of another can be calculated by an algorithm. Finite-valued transducers map every input word to at most a fixed number k of output words, a property that sits strictly between functional transducers (which produce exactly one output) and arbitrary transducers. The edit distance is defined per input word as the smallest edit operations that turn every output string of the first transducer into some output string of the second. Prior results established computability only for the functional case and uncomputability in the unrestricted case; the new result widens the decidable region by exploiting the fixed bound on output multiplicity.

Core claim

We show that the edit distance of finite-valued transducers is computable. A transducer is finite-valued when it produces at most k output words for every input word, where k is a fixed constant. The edit distance between two such transducers is the smallest number of edits required, for each input, to turn every output of the first into some output of the second. This class properly contains the functional transducers for which the problem was already known to be computable, while the problem remains uncomputable for transducers without the finite-valued restriction.

What carries the argument

The finite-valued restriction, which caps the number of outputs per input at a constant k, reduces the edit-distance computation to decidable automata constructions that exploit this boundedness.

If this is right

  • Any two finite-valued transducers can be compared for output similarity by a terminating procedure.
  • The decidability frontier for transducer edit distance now includes all relations with bounded output multiplicity per input.
  • Verification tasks that rely on output closeness become feasible for transducers that generate a small but non-singleton set of outputs.
  • The reduction technique separates the finite-valued case from the general undecidable case more tightly than the functional-only boundary.

Where Pith is reading between the lines

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

  • The result may support practical tools for checking consistency in multi-output string transformations used in compilers or data pipelines.
  • Complexity bounds on the decision procedure could be derived by inspecting the automata constructions used in the reduction.
  • Similar boundedness arguments might apply to other distance measures or to transducers equipped with weights.

Load-bearing premise

The transducers produce at most a fixed constant number of outputs for any given input word.

What would settle it

An explicit pair of finite-valued transducers together with a manually verifiable edit distance value that an algorithm claiming to compute the distance fails to return correctly.

read the original abstract

Transducers generalise automata by producing output word(s) for each input word, thereby defining a relation over words. A transducer is said to be finite-valued if, for every input word, it produces at most $k$ output words, for some constant $k$. If $k = 1$, then the transducer is said to be functional. The edit distance between two transducers is the minimal number of edits required to transform every output of one transducer into some output of the other, for each input word. This notion has been studied for functional transducers, where it is shown to be computable. However, it is uncomputable for transducers in general. In this work, we show the computability of the edit distance of finite-valued transducers, a class that is strictly more expressive than functional transducers.

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 claims to show that the edit distance between two finite-valued transducers is computable. Finite-valued transducers produce at most a bounded number k of output words for each input word, generalizing functional transducers (k=1). The edit distance is the minimal number of edits needed to transform the outputs of one transducer into those of the other for every input. The result extends previous computability for functional transducers and contrasts with uncomputability for arbitrary transducers.

Significance. This result is significant because it enlarges the class of transducers for which edit distance is decidable, using the key property of bounded output multiplicity to reduce the problem to effective automata constructions. This has potential applications in areas requiring comparison of string relations, such as in automata-based verification and approximate string matching. The approach aligns with existing methods in formal language theory and provides a natural generalization.

minor comments (2)
  1. The abstract asserts the main result but supplies no proof sketch, reduction outline, or complexity bound; adding one sentence on how boundedness is exploited would improve accessibility without altering the technical content.
  2. Ensure all definitions (e.g., the precise formulation of edit distance over relations) are restated or cross-referenced in the main body before the proof, to avoid any ambiguity for readers unfamiliar with the functional case.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of our work and for correctly summarizing the main contribution: the computability of edit distance between finite-valued transducers, which properly generalizes the known functional case while remaining decidable (in contrast to the general case). We appreciate the recognition of the result's significance and the recommendation for minor revision. No specific major comments were raised, so we will incorporate any minor editorial or presentational improvements in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper claims computability of edit distance for finite-valued transducers by extending the functional case via the bounded-output property (at most k outputs per input word) to reduce the problem to decidable automata constructions. No load-bearing steps, equations, or reductions in the abstract or described argument reduce the result to a self-definition, a fitted parameter renamed as a prediction, or a self-citation chain. The technique is a standard extension in transducer theory, independent of the target result by construction, with no enumerated circularity patterns present. The derivation is self-contained against external benchmarks in automata theory.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard automata-theoretic facts (decidability of emptiness, closure properties of regular languages, and constructions for finite-valued transducers) rather than new parameters or entities.

axioms (1)
  • domain assumption Finite-valued transducers admit effective constructions that reduce output-bounded relations to ordinary automata problems
    The proof must invoke this property to obtain decidability; it is standard in the transducer literature but not re-proved here.

pith-pipeline@v0.9.0 · 5424 in / 1144 out tokens · 53799 ms · 2026-05-08T03:23:12.278868+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

21 extracted references · 17 canonical work pages

  1. [1]

    Aiswarya, Amaldev Manuel, and Saina Sunny

    C. Aiswarya, Amaldev Manuel, and Saina Sunny. Deciding conjugacy of a rational relation - (extended abstract). In 28th International Conference on Developments in Language Theory, DLT 2024 , volume 14791 of Lecture Notes in Computer Science , pages 37--50. Springer, 2024. https://doi.org/10.1007/978-3-031-66159-4\_4 doi:10.1007/978-3-031-66159-4\_4

    work page doi:10.1007/978-3-031-66159-4 2024

  2. [2]

    Edit Distance of Finite State Transducers

    C. Aiswarya, Amaldev Manuel, and Saina Sunny. Edit Distance of Finite State Transducers . In 51st International Colloquium on Automata, Languages, and Programming ICALP 2024 , volume 297 of LIPIcs , pages 125:1--125:20. Schloss Dagstuhl -- Leibniz-Zentrum f \"u r Informatik, 2024. https://doi.org/10.4230/LIPIcs.ICALP.2024.125 doi:10.4230/LIPIcs.ICALP.2024.125

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

  3. [3]

    The equivalence of finite valued transducers (on HDT0L languages) is decidable

    Karel Cul \' k II and Juhani Karhum \" a ki. The equivalence of finite valued transducers (on HDT0L languages) is decidable. Theoretical Computer Science , 47(3):71--84, 1986. https://doi.org/10.1016/0304-3975(86)90134-9

    work page doi:10.1016/0304-3975(86)90134-9 1986

  4. [4]

    On the decidability of the equivalence for k -valued transducers

    Rodrigo de Souza. On the decidability of the equivalence for k -valued transducers. In 12th International Conference on Developments in Language Theory, DLT 2008 , volume 5257 of Lecture Notes in Computer Science , pages 252--263. Springer, 2008. https://doi.org/10.1007/978-3-540-85780-8\_20

    work page doi:10.1007/978-3-540-85780-8 2008

  5. [5]

    Automata, languages, and machines

    Samuel Eilenberg. Automata, languages, and machines. vol. A . Pure and applied mathematics. Academic Press, 1974

    1974

  6. [6]

    Approximate problems for finite transducers

    Emmanuel Filiot, Isma \" e l Jecker, Khushraj Madnani, and Saina Sunny. Approximate problems for finite transducers. In 52nd International Colloquium on Automata, Languages, and Programming ICALP 2024 , volume 334 of LIPIcs , pages 155:1--155:19. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2025

    2024

  7. [7]

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

    Emmanuel Filiot and Pierre - Alain Reynier. Transducers, logic and algebra for functions of finite words. ACM SIGLOG News , 3(3):4--19, 2016. https://doi.org/10.1145/2984450.2984453 doi:10.1145/2984450.2984453

    work page doi:10.1145/2984450.2984453 2016

  8. [8]

    Fischer and Arnold L

    Patrick C. Fischer and Arnold L. Rosenberg. Multitape one-way nonwriting automata. Journal of Computer and System Sciences , 2(1):88--101, 1968. https://doi.org/10.1016/S0022-0000(68)80006-6 doi:10.1016/S0022-0000(68)80006-6

    work page doi:10.1016/s0022-0000(68)80006-6 1968

  9. [9]

    Seymour Ginsburg and Gene F. Rose. A characterization of machine mappings. Journal of Symbolic Logic , 33(3):468--468, 1968. https://doi.org/10.2307/2270340 doi:10.2307/2270340

    work page doi:10.2307/2270340 1968

  10. [10]

    Gurari and Oscar H

    Eitan M. Gurari and Oscar H. Ibarra. A note on finitely-valued and finitely ambiguous transducers. Mathemtical Systems Theory , 16(1):61--66, 1983. https://doi.org/10.1007/BF01744569 doi:10.1007/BF01744569

    work page doi:10.1007/bf01744569 1983

  11. [11]

    Transductions and Context-Free Languages

    Jean Berstel . Transductions and Context-Free Languages . Teubner, Stuttgart, 1979

    1979

  12. [12]

    Multi-sequential word relations

    Isma \" e l Jecker and Emmanuel Filiot. Multi-sequential word relations. International Journal of Foundations of Computer Science , 29(2):271--296, 2018. https://doi.org/10.1142/S0129054118400075 doi:10.1142/S0129054118400075

    work page doi:10.1142/s0129054118400075 2018

  13. [13]

    The many facets of string transducers (invited talk)

    Anca Muscholl and Gabriele Puppis. The many facets of string transducers (invited talk). In 36th International Symposium on Theoretical Aspects of Computer Science STACS 2019 , volume 126 of LIPIcs , pages 2:1--2:21. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, 2019. https://doi.org/10.4230/LIPICS.STACS.2019.2 doi:10.4230/LIPICS.STACS.2019.2

    work page doi:10.4230/lipics.stacs.2019.2 2019

  14. [14]

    George N. Raney. Sequential functions. Journal of the ACM , 5(2):177--180, 1958. https://doi.org/10.1145/320924.320930 doi:10.1145/320924.320930

    work page doi:10.1145/320924.320930 1958

  15. [15]

    Kufleitner

    Jacques Sakarovitch and Rodrigo de Souza. On the decidability of bounded valuedness for transducers. In Mathematical Foundations of Computer Science 2008, 33rd International Symposium, MFCS 2008 Proceedings , Lecture Notes in Computer Science, pages 588--600. Springer, 2008. https://doi.org/10.1007/978-3-540-85238-4\_48 doi:10.1007/978-3-540-85238-4\_48

    work page doi:10.1007/978-3-540-85238-4 2008

  16. [16]

    On the decomposition of k-valued rational relations

    Jacques Sakarovitch and Rodrigo de Souza. On the decomposition of k-valued rational relations. In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2008 , LIPIcs, pages 621--632. Schloss Dagstuhl - Leibniz-Zentrum f \" u r Informatik, Germany, 2008. https://doi.org/10.4230/LIPICS.STACS.2008.1324 doi:10.4230/LIPICS....

    work page doi:10.4230/lipics.stacs.2008.1324 2008

  17. [17]

    Hunt III

    Richard Edwin Stearns and Harry B. Hunt III . On the equivalence and containment problems for unambiguous regular expressions, regular grammars and finite automata. SIAM Journal on Computing , 14(3):598--611, 1985. https://doi.org/10.1137/0214044

    work page doi:10.1137/0214044 1985

  18. [18]

    doi:10.1145/800125.804029

    Larry J. Stockmeyer and Albert R. Meyer. Word problems requiring exponential time: Preliminary report. In 5th Symposium on Theory of Computing, STOC 1973 , pages 1--9. ACM , 1973. https://doi.org/10.1145/800125.804029

    work page doi:10.1145/800125.804029 1973

  19. [19]

    Distance and Conjugacy of Word Transducers

    Saina Sunny. Distance and Conjugacy of Word Transducers . PhD thesis, School of Mathematics and Computer Science, Indian Institute of Technology (IIT) Goa, India, 2025. available at https://saisunny1994.github.io/pdfs/ThesisSigned.pdf

    2025

  20. [20]

    On the valuedness of finite transducers

    Andreas Weber. On the valuedness of finite transducers. Acta Informatica , 27(8):749--780, 1990. https://doi.org/10.1007/BF00264285 doi:10.1007/BF00264285

    work page doi:10.1007/bf00264285 1990

  21. [21]

    Decomposing finite-valued transducers and deciding their equivalence

    Andreas Weber. Decomposing finite-valued transducers and deciding their equivalence. SIAM Journal on Computing , 22(1):175--202, 1993. https://doi.org/10.1137/0222014

    work page doi:10.1137/0222014 1993