IMG_20210627_182832811_HDR_edited.jpg

Dr. Petra Wolf

Post-Doc 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

IMG_20220801_104307579_HDR.jpg
 

List of Publications

Click on entry for details.

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)

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)]

 

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

 
 
Lehrer eine Formel auf einer Tafel schre

Teaching

Exercises/Course Administration/Lecturer

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 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

Matheunterricht

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

Contact

Petra Wolf

Universitetet i Bergen
Institutt for informatikk
Postboks 7803
NO-5020 BERGEN
NORWAY

mail[at]wolfp.net

 

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

Edsger Wybe Dijkstra