mail[at]wolfp.net
Dr. Petra Wolf
PostDoc in Theoretical Computer Science
I am working as a researcher in the Algorithms group at the University of Bergen in Norway.
I am interested in Parameterized Complexity, Temporal Graphs, Quantum Computing, and Automata Theory.
Aug. 2022
New Position at University of Bergen
List of Publications
Click on entry for details.
Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms
(Jonas Lingg, Mateus de Oliveira Oliveira, Petra Wolf)
On the Complexity of Intersection Nonemptiness for StarFree Language Classes
(Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann, Markus Holzer, Ismaël Jecker, Mateus de Oliveira Oliveira, Petra Wolf)
Decomposing Permutation Automata
(Ismaël Jecker, Nicolas Mazzocchi, Petra Wolf)
Order Reconfiguration Under Width Constraints
(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)
A Timecop's Chase Around the Table
(Nils Morawietz, Petra Wolf)
Properties of Graphs Specified by a Regular Language
(Volker Diekert, Henning Fernau, Petra Wolf)
Diversity in Kemeny Rank Aggregation: A Parameterized Approach
(Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf)
Improving Run Length Encoding by Preprocessing
(Sven Fiergolla, Petra Wolf)
Width Notions for OrderingRelated Problems
(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)
Synchronization under Dynamic Constraints
(Petra Wolf)
Synchronization of Deterministic Visibly PushDown Automata
(Henning Fernau, Petra Wolf)
Synchronizing Deterministic PushDown Automata Can Be Really Hard
(Henning Fernau, Petra Wolf, Tomoyuki Yamakami)
Computational Complexity of Synchronization under Regular Constraints
(Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, Petra Wolf)
Restricted Power  Computational Complexity Results for Strategic Defense Games
(Ronald de Haan, Petra Wolf)
Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy
(Demen Güler, Andreas Krebs, KlausJörn Lange, Petra Wolf)
PhD, Master, and Bachelor Thesis
PhD Thesis (11.2021)
Generalized Synchronization and Intersection NonEmptiness of FiniteState Automata
The main focus of this work is to study the computational complexity of generalizations of the synchronization problem for deterministic finite automata (DFA). This problem asks for a given DFA, whether there exists a word w that maps each state of the automaton to one state. We call such a word w a synchronizing word. A synchronizing word brings a system from an unknown configuration into a well defined configuration and thereby resets the system.
We generalize this problem in four different ways. First, we restrict the set of potential synchronizing words to a fixed regular language associated with the synchronization under regular constraint problem. The motivation here is to control the structure of a synchronizing word so that, for instance, it first brings the system from an operate mode to a reset mode and then finally again into the operate mode.
The next generalization concerns the order of states in which a synchronizing word transitions the automaton. Here, a DFA A and a partial order R is given as input and the question is whether there exists a word that synchronizes A and for which the induced state order is consistent with R. Thereby, we study different ways for a word to induce an order on the state set.
Then, we change our focus from DFAs to pushdown automata and generalize the synchronization problem to pushdown automata and in the following work, to visibly pushdown automata. Here, a synchronizing word still needs to map each state of the automaton to one state but it further needs to fulfill some constraints on the stack. We study three different types of stack constraints where after reading the synchronizing word, the stacks associated to each run in the automaton must be (1) empty, (2) identical, or (3) can be arbitrary.
We observe that the synchronization problem for general pushdown automata is undecidable and study restricted subclasses of pushdown automata where the problem becomes decidable. For visibly pushdown automata we even obtain efficient algorithms for some settings.
The second part of this work studies the intersection nonemptiness problem for DFAs. This problem is related to the problem of whether a given DFA A can be synchronized into a state q as we can see the set of words synchronizing A into q as the intersection of languages accepted by automata obtained by copying A with different initial states and q as their final state.
For the intersection nonemptiness problem, we first study the complexity of the, in general PSPACEcomplete, problem restricted to subclasses of DFAs associated with the two well known StraubingThérien and CohenBrzozowski dotdepth hierarchies.
Finally, we study the problem whether a given minimal DFA A can be represented as the intersection of a finite set of smaller DFAs such that the language L(A) accepted by A is equal to the intersection of the languages accepted by the smaller DFAs. There, we focus on the subclass of permutation and commutative permutation DFAs and improve known complexity bounds.
Master Thesis (10.2018)
Decidability of the Regular Intersection Emptiness Problem
We determine the decidability of the intregproblem for several languages. The intregproblem of a fixed language L asks whether the intersection of L with a given regular language R is empty or not. We prove undecidability of the intregproblem for variations of the Machine Language, Bounded Tiling, Corridor Tiling, Bounded PCP, Equivalence of Regular Expressions in a shuffled encoding, and String Equivalence Modulo Padding in a shuffled encoding. We prove decidability of the intregproblem for String Equivalence Modulo Padding in a sequential encoding as well as over a unary alphabet in both encodings, SAT, kTQBF, True Quantified Boolean Formula, Integer Linear Programming, Vertex Cover, Independent Set, Knapsack, and Integer Knapsack. In the most cases we show the decidability of the intregproblem by constructing a condensed automaton condensed(A) from a given DFA A. In L(condensed(A)) only finitely many words have to be tested for membership in the intersection (defined by intreg) under which there is one element in the intersection if and only there is one in the original regular language described by A. We develop the three techniques merging, separating, and replacing of constructing the automaton condensed(A) and demonstrate them on the problems Vertex Cover, Independent Set, and Knapsack.
Bachelor Thesis (12.2016)
Computational Complexity of Computer Games  Gaming under Time Pressure
Identification of combination of game elements which give a game, in which they
occur, a certain computational complexity. Abstracted game elements have been studied instead of
concrete games. The work focused on the stopwatch as a game element.
Vita
Eberhard Karls Universität Tübingen

Bachelor of Science in Computer Science 2016

Master of Science in Computer Science 2018
Universität Trier
PhD supervised by Prof. Dr. Henning Fernau,
degree obtained Jan. 2022
Scholarships and Awards

Teaching award of University Trier in the cathegory 'Crossing Boundaries' with #LechturesForFuture 2022

Publication award of the graduate college of University Trier Faculty Four 2021
(Publikationspreis im Fachbereich 4 des Graduiertenkollegs der Universität Trier) 2021 
JSPS Summer Program 2020

Deutschlandstipendium 2017  2019

Master degree with distinction (Master Abschluss mit Auszeichnung) 2018
Participation in Workshops and Schools

Graph Searching in Canada (2022)

Dagstuhl Seminar: Quantum Complexity: Theory and Application (2021)

Dagstuhl Klausurtagung (organized): Modern Aspects of Complexity Theory in Automata Theory (2020)

Workshop on Kernelization (2019)

Dagstuhl Seminar: Algorithmic Enumeration: Outputsensitive, InputSensitive, Parameterized, Approximative (2018)

Theorietage (2017, 2018, 2019, 2020, 2021)

Tübingen's Frontiers of Theory: Lectures and Research (02.2016, 09.2016, 02.2017, 06,2017)
Teaching
Exercises/Course Administration/Lecturer
Universität Trier:

2021

Ausgewählte Themen zu QuantumComputing


2020/2021

Vorkurs Formale Grundlagen der Informatik

Diskrete Strukturen

Reading Group: Quantum Computing


2019, 2020, 2021 Kleines Studienprojekt LaTeXKurs
Eberhard Karls Universität Tübingen:

2018

Proseminar Komplexität von Computerspielen


2017/2018

Theoretische Informatik

Proseminar Theoretische Informatik  Große Informatiker der Geschichte


2017

Berechenbarkeit

Formale Sprachen

Proseminar Theoretische Informatik  Reguläre Sprachen


2016/2017

Theoretische Informatik

Mathematischer Vorkurs


2016

Komplexitätstheorie


2015/2016

Theoretische Informatik

Student Supervision
RP = Research Project
BA = Bachelor Thesis,
MA = Master Thesis,
 Esther Oest (BA) 2022: Kombinatorische Analyse von Roma
 Kevin Goergen (BA) 2021: Computational Complexity of the Puzzle Game Roma
 Alexander Pet (BA) 2021: Implementierung des historischen Brettspiels Latrunculi mit einer künstlichen Intelligenz in Unity
 Sven Fiergolla (BA) 2020: Improving Run Length Encoding on bit level by preprocessing
 Jonas Lingg (RP) 2020: The Consistency Problem for Partially Ordered Automata and Permutation Automata
Contact
Petra Wolf
Universitetet i Bergen
Institutt for informatikk
Postboks 7803
NO5020 BERGEN
NORWAY
mail[at]wolfp.net
„Computer Science is no more about computers than astronomy is about telescopes.“