7 papers
Hamming distance between finite transducers
Luc Dartois, Pierre-Cyrille Héam, Ismaël Jecker +1
We study bounded deviation of non-deterministic finite transducers under the Hamming distance: the bounded comparison problem asks, given two transducers and , wh…
Decomposition of Automata recognizing Ideals
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…
Representing One Letter Weighted Automata Over the Tropical Semiring
Shaull Almagor, Ismaël Jecker, Filip Mazowiecki +3
We consider weighted automata over the tropical semiring . Recently, it was shown that determinisation is decidable; in this paper we focus on the comple…
Determinisation and Unambiguisation of Polynomially-Ambiguous Rational Weighted Automata
Ismaël Jecker, Filip Mazowiecki, David Purser
We study the determinisation and unambiguisation problems of weighted automata over the rational field: Given a weighted automaton, can we determine whether there exists an equival…
History-deterministic Parikh Automata
Enzo Erlich, Mario Grobler, Shibashis Guha +3
Parikh automata extend finite automata by counters that can be tested for membership in a semilinear set, but only at the end of a run. Thereby, they preserve many of the desirable…
Finite-valued Streaming String Transducers
Emmanuel Filiot, Ismaël Jecker, Christof Löding +3
A transducer is finite-valued if for some bound k, it maps any given input to at most k outputs. For classical, one-way transducers, it is known since the 80s that finite valuednes…