Zobrazeno 1 - 10
of 20
pro vyhledávání: '"Grobler, Mario"'
Autor:
Grobler, Mario, Maaz, Stephanie, Mouawad, Amer E., Nishimura, Naomi, Ramamoorthi, Vijayaragunathan, Siebertz, Sebastian
In the solution discovery variant of a vertex (edge) subset problem $\Pi$ on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph $G$ together with a budget $b$. The question is whether we can transform th
Externí odkaz:
http://arxiv.org/abs/2409.17250
Autor:
Grobler, Mario, Siebertz, Sebastian
Various variants of Parikh automata on infinite words have recently been introduced in the literature. However, with some exceptions only their non-deterministic versions have been considered. In this paper we study the deterministic versions of all
Externí odkaz:
http://arxiv.org/abs/2401.14737
Autor:
Grobler, Mario, Maaz, Stephanie, Megow, Nicole, Mouawad, Amer E., Ramamoorthi, Vijayaragunathan, Schmand, Daniel, Siebertz, Sebastian
In the recently introduced framework of solution discovery via reconfiguration [Fellows et al., ECAI 2023], we are given an initial configuration of $k$ tokens on a graph and the question is whether we can transform this configuration into a feasible
Externí odkaz:
http://arxiv.org/abs/2311.13478
We study reduction rules for Directed Feedback Vertex Set (DFVS) on instances without long cycles. A DFVS instance without cycles longer than $d$ naturally corresponds to an instance of $d$-Hitting Set, however, enumerating all cycles in an $n$-verte
Externí odkaz:
http://arxiv.org/abs/2308.15900
Several variants of Parikh automata on infinite words were recently introduced by Guha et al. [FSTTCS, 2022]. We show that one of these variants coincides with blind counter machine as introduced by Fernau and Stiebe [Fundamenta Informaticae, 2008].
Externí odkaz:
http://arxiv.org/abs/2307.07238
Autor:
Fellows, Michael R., Grobler, Mario, Megow, Nicole, Mouawad, Amer E., Ramamoorthi, Vijayaragunathan, Rosamond, Frances A., Schmand, Daniel, Siebertz, Sebastian
The dynamics of real-world applications and systems require efficient methods for improving infeasible solutions or restoring corrupted ones by making modifications to the current state of a system in a restricted way. We propose a new framework of s
Externí odkaz:
http://arxiv.org/abs/2304.14295
Autor:
Grobler, Mario, Siebertz, Sebastian
B\"uchi's theorem states that $\omega$-regular languages are characterized as languages of the form $\bigcup_i U_i V_i^\omega$, where $U_i$ and $V_i$ are regular languages. Parikh automata are automata on finite words whose transitions are equipped w
Externí odkaz:
http://arxiv.org/abs/2302.04087
Parikh automata on finite words were first introduced by Klaedtke and Rue{\ss} [Automata, Languages and Programming, 2003]. In this paper, we introduce several variants of Parikh automata on infinite words and study their expressiveness. We show that
Externí odkaz:
http://arxiv.org/abs/2301.08969
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
Autor:
Grobler, Mario, Jiang, Yiting, Ossona de Mendez, Patrice, Siebertz, Sebastian, Vigny, Alexandre
Publikováno v:
In Journal of Combinatorial Theory, Series B November 2024 169:96-133
