1 citations · 3 across the 8 of their papers we have counts for
11 papers
Towards Settling the Complexity of the Lettericity Problem
Mario Grobler, Nils Morawietz, Silas Cato Sacher
The lettericity of a graph is defined as the smallest size of an alphabet such that there is a word and a decoder $\mathcal{D} \subseteq Σ…
Kernelization Complexity of Solution Discovery Problems
Mario Grobler, Stephanie Maaz, Amer E. Mouawad +3
In the solution discovery variant of a vertex (edge) subset problem on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph tog…
Deterministic Parikh automata on infinite words
Mario Grobler, Sebastian Siebertz
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…
Solution discovery via reconfiguration for problems in P
Mario Grobler, Stephanie Maaz, Nicole Megow +4
In the recently introduced framework of solution discovery via reconfiguration [Fellows et al., ECAI 2023], we are given an initial configuration of tokens on a graph and the q…
Data reduction for directed feedback vertex set on graphs without long induced cycles
Jona Dirks, Enna Gerhard, Mario Grobler +2
We study reduction rules for Directed Feedback Vertex Set (DFVS) on directed graphs without long cycles. A DFVS instance without cycles longer than naturally corresponds to an…
Parikh Automata on Finite and Infinite Words
Mario Grobler, Leif Sabellek, Sebastian Siebertz
We study Parikh automata on finite and infinite words. First we establish some results for Parikh automata on finite words. Following, we present several definitions of Parikh auto…
On Solution Discovery via Reconfiguration
Michael R. Fellows, Mario Grobler, Nicole Megow +5
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…
Büchi-like characterizations for Parikh-recognizable omega-languages
Mario Grobler, Sebastian Siebertz
Büchi's theorem states that -regular languages are characterized as languages of the form , where and are regular languages. Parikh automata are…
Parikh Automata on Infinite Words
Mario Grobler, Leif Sabellek, Sebastian Siebertz
Parikh automata on finite words were first introduced by Klaedtke and Rueß [Automata, Languages and Programming, 2003]. In this paper, we introduce several variants of Parikh autom…
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…
Discrepancy and Sparsity
Mario Grobler, Yiting Jiang, Patrice Ossona de Mendez +2
We study the connections between the notions of combinatorial discrepancy and graph degeneracy. In particular, we prove that the maximum discrepancy over all subgraphs of a gra…