DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2026.47

Hamming Distance Between Finite Transducers

Authors: Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, and Silvio Vescovo

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

Abstract

We study bounded deviation of non-deterministic finite transducers under the Hamming distance: the bounded comparison problem asks, given two transducers and k ∈ ℕ, 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 deviation problems, 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.

Cite as

Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker, and Silvio Vescovo. Hamming Distance Between Finite Transducers. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dartois_et_al:LIPIcs.MFCS.2026.47,
  author =	{Dartois, Luc and H\'{e}am, Pierre-Cyrille and Jecker, Isma\"{e}l and Vescovo, Silvio},
  title =	{{Hamming Distance Between Finite Transducers}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.47},
  URN =		{urn:nbn:de:0030-drops-274285},
  doi =		{10.4230/LIPIcs.MFCS.2026.47},
  annote =	{Keywords: Transducers, Hamming distance, NL-completeness, DP-completeness}
}

Search Results

Documents authored by Vescovo, Silvio

Hamming Distance Between Finite Transducers

Abstract

Cite as

Thanks for your feedback!

Could not send message