mail[at]wolfp.net
Dr. Petra Wolf
Post-Doc in Theoretical Computer Science
I am working as a post-doc researcher at LaBRI at the Universtiy of Bordeaux, France.
I am interested in Parameterized Complexity, Temporal Graphs, Quantum Computing, and Automata Theory.
PACE Solver Description: Zygosity
(Emmanuel Arrighi, Pål Grønås Drange , Kenneth Langedal , Farhad Vadiee , Martin Vatshelle, Petra Wolf)
Kernelizing Temporal Exploration Problems
(Emmanuel Arrighi, Fedor V. Fomin, Petr Golovach,
Petra Wolf)
Cluster Editing with Overlapping Communities
(Emmanuel Arrighi, Matthias Bentert, Pål G. Drange,
Blair Sullivan, Petra Wolf)
Information Processing Letter
Learning from positive and negative examples:
New proof for binary alphabets
(Jonas Lingg, Mateus de Oliveira Oliveira, Petra Wolf)
Synchronization and Diversity of Solutions
(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
(Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz,
Frank Sommer, Petra Wolf)
Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms
(Jonas Lingg, Mateus de Oliveira Oliveira, Petra Wolf)
On the Complexity of Intersection Non-emptiness for Star-Free 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 Ordering-Related Problems
(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)
Synchronization under Dynamic Constraints
(Petra Wolf)
Synchronization of Deterministic Visibly Push-Down Automata
(Henning Fernau, Petra Wolf)
Synchronizing Deterministic Push-Down 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, Klaus-Jörn Lange, Petra Wolf)
PhD, Master, and Bachelor Thesis
PhD Thesis (11.2021)
Generalized Synchronization and Intersection Non-Emptiness of Finite-State 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 push-down automata and generalize the synchronization problem to push-down automata and in the following work, to visibly push-down 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 push-down automata is undecidable and study restricted sub-classes of push-down automata where the problem becomes decidable. For visibly push-down automata we even obtain efficient algorithms for some settings.
The second part of this work studies the intersection non-emptiness 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 non-emptiness problem, we first study the complexity of the, in general PSPACE-complete, problem restricted to subclasses of DFAs associated with the two well known Straubing-Thérien and Cohen-Brzozowski dot-depth 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 intreg-problem for several languages. The intreg-problem 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 intreg-problem 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 intreg-problem for String Equivalence Modulo Padding in a sequential encoding as well as over a unary alphabet in both encodings, SAT, k-TQBF, 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 intreg-problem 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
Studies
Eberhard Karls Universität Tübingen
-
Bachelor of Science
in Computer Science 2016 -
Master of Science
in Computer Science 2018
PhD
Universität Trier
PhD supervised by Prof. Dr. Henning Fernau,
degree obtained Jan. 2022
Post-Doc
Universtiy of Bergen
PostDoc August 2022 - October 2023
LaBRI University of Bordeaux
PostDoc since November 2023
Scholarships and Awards
-
2nd Place Heuristic Track PACE Challenge 2023
-
Award for an outstanding dissertation by the Friends of the University Trier association
-
Nomination for Dissertation Award 2022 of the German Computer Science Society (GI)
-
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
-
Autobóz Workshop (2023)
-
Emerging optimization methods: from metaheuristics to quantum approaches (2023)
-
Autobóz Workshop (2022)
-
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: Output-sensitive, Input-Sensitive, 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
University of Bergen:
-
2023
-
Complexity Theory
-
Universität Trier:
-
2021
-
Ausgewählte Themen zu Quantum-Computing
-
-
2020/2021
-
Vorkurs Formale Grundlagen der Informatik
-
Diskrete Strukturen
-
Reading Group: Quantum Computing
-
-
2019, 2020, 2021, 2022 Kleines Studienprojekt LaTeX-Kurs
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,
- Sven Fiergolla (MA) 2023: Theoretical and Empirical Analysis of the Representability of Dynamic Networks as Edge Periodic Temporal Graphs
- Mehmet Yigit (MA) 2022: Implementation of Cluster Graph Optimization Problems on Quantum Computers
- 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
Université de Bordeaux
LaBRI
351, cours de la Libération
F-33405 Talence cedex
FRANCE
mail[at]wolfp.net
„Computer Science is no more about computers than astronomy is about telescopes.“