Zobrazeno 1 - 10
of 68
pro vyhledávání: '"Jecker, Ismaël"'
Autor:
Filiot, Emmanuel, Jecker, Ismaël, Puppis, Gabriele, Löding, Christof, Muscholl, Anca, Winter, Sarah
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 valuedness entails decidability of the equivalence problem. This decidability r
Externí odkaz:
http://arxiv.org/abs/2405.08171
We investigate the dimension-parametric complexity of the reachability problem in vector addition systems with states (VASS) and its extension with pushdown stack (pushdown VASS). Up to now, the problem is known to be $\mathcal{F}_k$-hard for VASS of
Externí odkaz:
http://arxiv.org/abs/2310.09008
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 equivalent deterministic, respectively unambiguous, weighted automaton? Recen
Externí odkaz:
http://arxiv.org/abs/2310.02204
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", which determines the winner or payoff of the game. Traditionally, t
Externí odkaz:
http://arxiv.org/abs/2211.13626
Autor:
Erlich, Enzo, Grobler, Mario, Guha, Shibashis, Jecker, Ismaël, Lehtinen, Karoliina, Zimmermann, Martin
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 properties of finite automata. Deterministic Parikh automata are stri
Externí odkaz:
http://arxiv.org/abs/2209.07745
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 algorithmic properties of finite automata. Here, we study the extension o
Externí odkaz:
http://arxiv.org/abs/2207.07694
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 complex abstract machines: we introduce a new notion of delay tailore
Externí odkaz:
http://arxiv.org/abs/2205.04287
Autor:
Arrighi, Emmanuel, Fernau, Henning, Hoffmann, Stefan, Holzer, Markus, Jecker, Ismaël, Oliveira, Mateus de Oliveira, Wolf, Petra
In the Intersection Non-Emptiness problem, we are given a list of finite automata $A_1,A_2,\dots,A_m$ over a common alphabet $\Sigma$ as input, and the goal is to determine whether some string $w\in \Sigma^*$ lies in the intersection of the languages
Externí odkaz:
http://arxiv.org/abs/2110.01279
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 primality was introduced by Kupferman and Mosheiff in 2013, and while they
Externí odkaz:
http://arxiv.org/abs/2107.04683
Publikováno v:
Logical Methods in Computer Science, Volume 20, Issue 1 (January 11, 2024) lmcs:10156
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 based on the run constructed so far, but independently of the remainde
Externí odkaz:
http://arxiv.org/abs/2105.02611