Ismaël Jecker

Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker et al.

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.

Mathias Berry, Pierre-Cyrille Héam, Ismaël Jecker

Minimizing the size of finite automata is a fundamental problem in theoretical computer science. Beyond standard minimization, further reductions can be achieved by decomposing an automaton into smaller components whose languages combine via intersection or union to recover the original language. However, in general, no polynomial-time algorithm is known for computing such decompositions. In this paper, we focus on automata that recognize ideals, that is, languages at level 1/2 in the Straubing-Thérien hierarchy. Equivalently, these languages are expressible as a finite union of languages of the form $Σ^*a_1Σ^*\dotsΣ^*a_nΣ^*$ where $Σ$ is an alphabet and $a_i$ are letters of $Σ$. We show that the two problems of deciding whether such a language can be decomposed into an intersection or a union of smaller automata are decidable in NL. Moreover, we provide a polynomial-time algorithm that computes a decomposition into an intersection, if one exists, while ensuring that the resulting components also recognize ideal languages.