1 citations · 3 across the 8 of their papers we have counts for
14 papers · 1 filter
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…
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…
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…
Reachability in 3-VASS is Elementary
Wojciech Czerwiński, Ismaël Jecker, Sławomir Lasota +1
The reachability problem in 3-dimensional vector addition systems with states (3-VASS) is known to be PSpace-hard, and to belong to Tower. We significantly narrow down the complexi…
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…
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…