4 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…
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…
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…
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…