1 citations · 4 across the 10 of their papers we have counts for
6 papers · 1 filter
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…
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov +2
In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of resea…
Properties of Graphs Specified by a Regular Language
Volker Diekert, Henning Fernau, Petra Wolf
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property . What happens if this question is modified i…
A Timecop's Chase Around the Table
Nils Morawietz, Petra Wolf
We consider the cops and robber game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge, a…
Improving Run Length Encoding by Preprocessing
Sven Fiergolla, Petra Wolf
The Run Length Encoding (RLE) compression method is a long standing simple lossless compression scheme which is easy to implement and achieves a good compression on input data whic…