8 citations · 16 across the 15 of their papers we have counts for
24 papers
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…
Bidding Graph Games with Partially-Observable Budgets
Guy Avni, Ismael Jecker, Djordje Zikelic
Two-player zero-sum "graph games" are a central model, which proceeds as follows. A token is placed on a vertex of a graph, and the two players move it to produce an infinite "play…
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…
Parikh Automata over Infinite Words
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
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 preserving many of the desirable alg…
A Regular and Complete Notion of Delay for Streaming String Transducers
Emmanuel Filiot, Ismaël Jecker, Christof Löding +1
The notion of delay between finite transducers is a core element of numerous fundamental results of transducer theory. The goal of this work is to provide a similar notion for more…
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann +4
In the Intersection Non-Emptiness problem, we are given a list of finite automata over a common alphabet as input, and the goal is to determine whether some…
Decomposing Permutation Automata
Ismaël Jecker, Nicolas Mazzocchi, Petra Wolf
A deterministic finite automaton (DFA) is composite if its language can be decomposed into an intersection of languages of smaller DFAs. Otherwise, A is prime. This notion of prima…
A Bit of Nondeterminism Makes Pushdown Automata Expressive and Succinct
Shibashis Guha, Ismaël Jecker, Karoliina Lehtinen +1
We study the expressiveness and succinctness of history-deterministic pushdown automata (HD-PDA) over finite words, that is, pushdown automata whose nondeterminism can be resolved…
A Ramsey Theorem for Finite Monoids
Ismaël Jecker
Repeated idempotent elements are commonly used to characterise iterable behaviours in abstract models of computation. Therefore, given a monoid , it is natural to ask how long a…
Simplified Game of Life: Algorithms and Complexity
Krishnendu Chatterjee, Rasmus Ibsen-Jensen, Ismaël Jecker +1
Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A…
Infinite-Duration All-Pay Bidding Games
Guy Avni, Ismaël Jecker, Đorđe Žikelić
In a two-player zero-sum graph game the players move a token throughout a graph to produce an infinite path, which determines the winner or payoff of the game. Traditionally, the p…
The Complexity of Transducer Synthesis from Multi-Sequential Specifications
Léo Exibard, Emmanuel Filiot, Ismaël Jecker
The transducer synthesis problem on finite words asks, given a specification , where and are sets of finite words, whether there exists an implement…
Beyond admissibility: Dominance between chains of strategies
Nicolas Basset, Ismaël Jecker, Arno Pauly +2
Admissible strategies, i.e. those that are not dominated by any other strategy, are a typical rationality notion in game theory. In many classes of games this is justified by resul…
On Delay and Regret Determinization of Max-Plus Automata
Emmanuel Filiot, Ismaël Jecker, Nathan Lhote +2
Decidability of the determinization problem for weighted automata over the semiring , WA for short, is a long-standing open question. We propo…
On Reversible Transducers
Luc Dartois, Paulin Fournier, Ismaël Jecker +1
Deterministic two-way transducers define the robust class of regular functions which is, among other good properties, closed under composition. However, the best known algorithms f…
Degree of sequentiality of weighted automata
Laure Daviaud, Ismael Jecker, Pierre-Alain Reynier +1
Weighted automata (WA) are an important formalism to describe quantitative properties. Obtaining equivalent deterministic machines is a longstanding research problem. In this paper…
On Equivalence and Uniformisation Problems for Finite Transducers
Emmanuel Filiot, Ismaël Jecker, Christof Löding +1
Transductions are binary relations of finite words. For rational transductions, i.e., transductions defined by finite transducers, the inclusion, equivalence and sequential uniform…
Aperiodic String Transducers
Luc Dartois, Ismaël Jecker, Pierre-Alain Reynier
Regular string-to-string functions enjoy a nice triple characterization through deterministic two-way transducers (2DFT), streaming string transducers (SST) and MSO definable funct…
Multi-Sequential Word Relations
Ismaël Jecker, Emmanuel Filiot
Rational relations are binary relations of finite words that are realised by non-deterministic finite state transducers (NFT). A particular kind of rational relations is the sequen…