top of page

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.

Start: Kenntnisse

Nov 2023

New Position: Post-Doc at LaBRI, University of Bordeaux

Start: Pubication Overview

List of Publications

Click on entry for details.


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)

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)

Diversity in Kemeny Rank Aggregation: A Parameterized Approach

(Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf)

Width Notions for Ordering-Related Problems

(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)

Computational Complexity of Synchronization under Regular Constraints

(Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, 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.

[Download (English)]

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.

[Download (English)]

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.

[Download (German)]

Start: Abschluss



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


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

Start: Vita
Start: Teaching
Lehrer eine Formel auf einer Tafel schre


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
Keyboard and Mouse
Start: Students
Black Notebook


Petra Wolf

Université de Bordeaux
351, cours de la Libération

F-33405 Talence cedex


Start: Contact

„Computer Science is no more about computers than astronomy is about telescopes.“

Edsger Wybe Dijkstra

Start: Zitat
bottom of page