5 papers
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…
Synchronizing Deterministic Push-Down Automata Can Be Really Hard
Henning Fernau, Petra Wolf, Tomoyuki Yamakami
The question if a deterministic finite automaton admits a software reset in the form of a so-called synchronizing word can be answered in polynomial time. In this paper, we extend…
Synchronization of Deterministic Visibly Push-Down Automata
Henning Fernau, Petra Wolf
We generalize the concept of synchronizing words for finite automata, which map all states of the automata to the same state, to deterministic visibly push-down automata. Here, a s…
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
Petra Wolf, Henning Fernau
The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton M as input, whether the language L(M) accepted by M contains any positive instance of the…
From Decidability to Undecidability by Considering Regular Sets of Instances
Petra Wolf
We are lifting classical problems from single instances to regular sets of instances. The task of finding a positive instance of the combinatorial problem in a potentially infi…