wolfp[at]unitrier.de
Petra Wolf
PhD Student in Theoretical Computer Science
I am currently working at the University of Trier as a researcher in the Theoretical Computer Science group led by Prof. Dr. Henning Fernau.
I am interested in Quantum Computing, Formal Languages, Complexity Theory, Computability, and Automata Theory.
Papers accepted at FSTTCS 2020
Width Notions for OrderingRelated Problems
Synchronization under Dynamic Constraints
Petra Wolf
Synchronization of Deterministic Visibly PushDown Automata
List of Publications
[PV] = Link to Publisher's Version
[Pre] = Link to Preprint Version
Accepted at FSTTCS 2020
Width Notions for OrderingRelated Problems
(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)
We are studying a weighted version of a linear extension problem, given some finite partial order ρ, called Completion of an Ordering. While this problem is NPcomplete, we show that it lies in FPT when parameterized by the interval width of ρ. This ordering problem can be used to model several ordering problems stemming from diverse application areas, such as graph drawing, computational social choice, or computer memory management. Each application yields a special ρ. We also relate the interval width of ρ to parameterizations such as maximum range that have been introduced earlier in these applications, sometimes improving on parameterized algorithms that have been developed for these parameterizations before. This approach also gives some practical subexponential time algorithms for ordering problems.
Accepted at FSTTCS 2020, arXiv [Pre]
Synchronization under Dynamic Constraints
(Petra Wolf)
Imagine an assembly line where a box with a lid and liquid in it enters in some unknown orientation. The box should leave the line with the open lid facing upwards with the liquid still in it. To save costs there are no complex sensors or image recognition software available on the assembly line, so a reset sequence needs to be computed. But how can the dependencies of the deforming impact of a transformation of the box, such as 'do not tilt the box over when the lid is open' or 'open the lid again each time it gets closed' be modeled? We present three attempts to model constraints of these kinds on the order in which the states of an automaton are transitioned by a synchronizing word. The first two concepts relate the last visits of states and form constraints on which states still need to be reached, whereas the third concept concerns the first visits of states and forms constraints on which states might still be reached. We examine the computational complexity of different variants of the problem, whether an automaton can be synchronized with a word that respects the constraints defined in the respective concept, and obtain nearly a full classification. While most of the problems are PSPACEcomplete we also observe NPcomplete variants and variants solvable in polynomial time.
One of them is the careful synchronization problem for partial weakly acyclic automata (which are partial automata, the states of which can be ordered such that no transition leads to a smaller state), which is shown to be solvable in time O(k^2 n^2 log(n)) where n is the size of the state set and k is the size of the alphabet. The algorithm even computes a synchronizing words as a witness. This is quite surprising as the careful synchronization problem uses to be a hard problem for most classes of automata.
We will also observe a drop of the complexity if we track the orders of states on several paths simultaneously instead of tracking the set of active states. Further, we give upper bounds on the length of a synchronizing word depending on the size of the input relation and show that the Cerny conjecture holds for partial weakly acyclic automata.
Acceppted at FSTTCS 2020, arXiv [Pre]
Synchronization of Deterministic Visibly PushDown 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 pushdown automata. Here, a synchronizing word w does not only map all states to the same state but also fulfills some conditions on the stack content of each run after reading w. We consider three types of these stack constraints: after reading w, the stack (1) is empty in each run, (2) contains the same sequence of stack symbols in each run, or (3) contains an arbitrary sequence which is independent of the other runs. We show that in contrast to general deterministic pushdown automata, it is decidable for deterministic visibly pushdown automata whether there exists a synchronizing word with each of these stack constraints, i.e., the problems are in EXPTIME. Under the constraint (1) the problem is even in P. For the subclasses of deterministic very visibly pushdown automata the problem is in P for all three types of constraints. We further study variants of the synchronization problem where the number of turns in the stack height behavior caused by a synchronizing word is restricted, as well as the problem of synchronizing a variant of a sequential transducer, which shows some visibly behavior, by a word that synchronizes the states and produces the same output on all runs.
Synchronizing Deterministic PushDown 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 socalled synchronizing word can be answered in polynomial time. In this paper, we extend this algorithmic question to deterministic automata beyond finite automata. We prove that the question of synchronizability becomes undecidable even when looking at deterministic onecounter automata. This is also true for another classical mild extension of regularity, namely that of deterministic oneturn pushdown automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACEcomplete (and hence decidable) synchronizability problem. Likewise, we arrive at a decidable synchronizability problem for (partially) blind deterministic counter automata.
There are several interpretations of what synchronizability should mean for deterministic pushdown automata. This is depending on the role of the stack: should it be empty on synchronization, should it be always the same or is it arbitrary? For the automata classes studied in this paper, the complexity or decidability status of the synchronizability problem is mostly independent of this technicality, but we also discuss one class of automata where this makes a difference.
ICTCS 2020, arXiv [Pre]
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 P in a potentially infinite given regular set is equivalent to the so called intregproblem of P, which asks for a given DFA A, whether the intersection of P with L(A) is nonempty. The intregproblem generalizes the idea of considering multiple instances at once and connects classical combinatorial problems with the field of automata theory. While the question of the decidability of the intregproblem has been answered positively for several NP and even PSPACEcomplete problems, we are presenting natural problems even from L with an undecidable intregproblem. We also discuss alphabet sizes and different encodingschemes elaborating the boundary between problemvariants with a decidable respectively undecidable intregproblem.
arXiv [Pre]
Regular Intersection Emptiness of Graph Problems: Finding a Needle in a Haystack of Graphs with the Help of Automata
(Heinning Fernau, Petra Wolf)
The Int_regproblem 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 problem P. We consider the Int_regproblem for a number of different graph problems and give general criteria that give decision procedures for these Int_regproblems. To achieve this goal, we consider a natural graph encoding so that the language of all graph encodings is regular. Then, we draw the connection between classical pumping and interchangearguments from the field of formal language theory with the graph operations induced on the encoded graph. Our techniques apply among others to the Int_regproblem of wellknown graph problems like Vertex Cover and Independent Set, as well as to subgraph problems, graphedit problems and graphpartitioning problems, including coloring problems.
MFCS 2019 [PV]
Computational Complexity of Synchronization under Regular Constraints
(Henning Fernau, Vladimir V. Gusev, Stefan Hoffmann, Markus Holzer, Mikhail V. Volkov, Petra Wolf)
Many variations of synchronization of finite automata have been studied in the previous decades. Here, we suggest studying the question if synchronizing words exist that belong to some fixed constraint language, given by some partial finite automaton called constraint automaton. We show that this synchronization problem becomes PSPACEcomplete even for some constraint automata with two states and a ternary alphabet. In addition, we characterize constraint automata with arbitrarily many states for which the constrained synchronization problem is polynomialtime solvable. We classify the complexity of the constrained synchronization problem for constraint automata with two states and two or three letters completely and lift those results to larger classes of finite automata.
DCFS 2019 [PV]
On the Decidability of Finding a Positive ILPInstance in a Regular Set of ILPInstances
(Petra Wolf)
The regular intersection emptiness problem for a decision problem P (intreg(P)) is to decide whether a potentially infinite regular set of encoded Pinstances contains a positive one. Since intreg(P) is decidable for some NPcomplete problems and undecidable for others, its investigation provides insights in the nature of NPcomplete problems. Moreover, the decidability of the intreg problem is usually achieved by exploiting the regularity of the set of instances; thus, it also establishes a connection to formal language and automata theory. We consider the intregproblem for the wellknown NPcomplete problem Integer Linear Programming (ILP). It is shown that any DFA that describes a set of ILPinstances (in a natural encoding) can be reduced to a finite core of instances that contains a positive one if and only if the original set of instances did. This result yields the decidability of intreg(ILP).
FUN 2018 [PV]
We study the game Greedy Spiders, a twoplayer strategic defense game, on planar graphs and show PSPACEcompleteness for the problem of deciding whether one player has a winning strategy for a given instance of the game. We also generalize our results in metatheorems, which consider a large set of strategic defense games. We achieve more detailed complexity results by restricting the possible strategies of one of the players, which leads us to Sigma^p_2 and Pi^p_2hardness results.
LATA 2018 [PV]
Deciding Regular Intersection Emptiness of Complete Problems for PSPACE and the Polynomial Hierarchy
(Demen Güler, Andreas Krebs, KlausJörn Lange, Petra Wolf)
For a regular set R of quantified Boolean formulae we decide whether R contains a true formula. We conclude that there is a PSPACEcomplete problem for which emptiness of intersection with a regular set is decidable. Furthermore, by restricting depth and order of quantification we obtain complete problems for each level of the polynomial hierarchy with this decidability as well.
Bachelor and Master Thesis
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.
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.
Vita
Eberhard Karls Universität Tübingen
Bachelor of Science in Computer Science 2016
Master of Science in Computer Science 2018
Universität Trier
In progress: PhD supervised by Prof. Dr. Henning Fernau
Scholarships and Awards
Master degree with distinction (Master Abschluss mit Auszeichnung)
Deutschlandstipendium 2017  2019
JSPS Summer Program (2020)
Participation in Workshops and Schools

Tübingen's Frontiers of Theory: Lectures and Research (02.2016, 09.2016, 02.2017, 06,2017)

Theorietage (2017, 2018, 2019, 2020)

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

Workshop on Kernelization (2019)
Teaching
Exercises/Course Administration/Lecturer
Universität Trier:

2020/2021

Vorkurs Formale Grundlagen der Informatik

Diskrete Strukturen

Reading Group: Quantum Computing


2019, 2020 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

Contact
Petra Wolf
Theoretische Informatik
Campus II
Universität Trier
D54286 Trier
wolfp[at]unitrier.de
„Computer Science is no more about computers than astronomy is about telescopes.“