Petra Wolf
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Petra Wolf has a total of 15 co-authors. Here are the top co-authors by number of shared publications:
- Henning Fernau
Universität Trier
4 shared publications - Nils Morawietz
Philipps-Universität Marburg
2 shared publications - Volker Diekert
University of Stuttgart, Stuttgart, Germany
2 shared publications - Emmanuel Arrighi
University of Bergen
1 shared publication - Esther Oest
Universität Trier
1 shared publication - Frank Sommer
Institute of Logic and Computation TU Wien Austria
1 shared publication
Latest Publications
- 3 October 2025
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 156
Decomposing permutation automata
- 3 October 2025
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 156
Decomposing permutation automata
- Open Access
- 13 June 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1051
Parameterized algorithms for multi-label periodic temporal graph realization
- 13 June 2025
- Published by Elsevier in Theoretical Computer Science
- Vol. 1051
Open AccessParameterized algorithms for multi-label periodic temporal graph realization
- 1 January 2023
- Published by Springer Nature
- p. 283-297
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
- 1 January 2023
- Published by Springer Nature
- p. 283-297
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge-Periodic Temporal Graphs
- Open Access
- 12 August 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 357-385
Properties of graphs specified by a regular language
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $$\varPhi $$ . What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $$\varPhi $$ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $$\varSigma $$ , and we define a regular set $$\mathbb {G}\subseteq \varSigma ^*$$ such that every nonempty word $$w\in \mathbb {G}$$ defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $$\varSigma $$ . Then, we ask whether the automaton $$\mathcal {A}$$ specifies some graph satisfying a certain property $$\varPhi $$ . Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph $$F^\infty $$ and therefore the family of finite subgraphs of $$F^\infty $$ where F appears as an induced subgraph. This yields a geometric description of all graphs specified by L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.- 12 August 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 357-385
Open AccessProperties of graphs specified by a regular language
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $$\varPhi $$ . What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $$\varPhi $$ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $$\varSigma $$ , and we define a regular set $$\mathbb {G}\subseteq \varSigma ^*$$ such that every nonempty word $$w\in \mathbb {G}$$ defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $$\varSigma $$ . Then, we ask whether the automaton $$\mathcal {A}$$ specifies some graph satisfying a certain property $$\varPhi $$ . Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph $$F^\infty $$ and therefore the family of finite subgraphs of $$F^\infty $$ where F appears as an induced subgraph. This yields a geometric description of all graphs specified by L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece. - Open Access
- 9 August 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 285-287
Preface to Klaus-Jörn Lange Festschrift
- 9 August 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 285-287
Open AccessPreface to Klaus-Jörn Lange Festschrift
- Open Access
- 4 August 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 505-519
On the decidability of finding a positive ILP-instance in a regular set of ILP-instances
The regular intersection emptiness problem for a decision problemP( $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (P)) is to decide whether a potentially infinite regular set of encodedP-instances contains a positive one. Since $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (P) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the $${{\textit{int}}_{{\mathrm {Reg}}}}$$ -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 $${{\textit{int}}_{{\mathrm {Reg}}}}$$ -problem for the well-known NP-complete problemInteger Linear Programming(ILP). It is shown that any DFA that describes a set ofILP-instances (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 $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (ILP).- 4 August 2022
- Published by Springer Nature in Acta Informatica
- Vol. 59 (4) , 505-519
Open AccessOn the decidability of finding a positive ILP-instance in a regular set of ILP-instances
The regular intersection emptiness problem for a decision problemP( $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (P)) is to decide whether a potentially infinite regular set of encodedP-instances contains a positive one. Since $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (P) is decidable for some NP-complete problems and undecidable for others, its investigation provides insights in the nature of NP-complete problems. Moreover, the decidability of the $${{\textit{int}}_{{\mathrm {Reg}}}}$$ -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 $${{\textit{int}}_{{\mathrm {Reg}}}}$$ -problem for the well-known NP-complete problemInteger Linear Programming(ILP). It is shown that any DFA that describes a set ofILP-instances (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 $${{\textit{int}}_{{\mathrm {Reg}}}}$$ (ILP). - 29 May 2022
- Published by Springer Nature
- p. 398-411
Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms
- 29 May 2022
- Published by Springer Nature
- p. 398-411
Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms
- Open Access
Synchronization under Dynamic Constraints
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 PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. 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.
Open AccessSynchronization under Dynamic Constraints
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 PSPACE-complete we also observe NP-complete variants and variants solvable in polynomial time. 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.
- Open Access
Properties of Graphs Specified by a Regular Language
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $\Phi$. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $\Phi$ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language $L$ if a certain torsion condition is satisfied. This condition holds trivially if $L$ is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $\Sigma$, and we define a regular set $\mathbb{G}\subseteq \Sigma^*$ such that every nonempty word $w\in \mathbb{G}$ defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $\Sigma$. Then, we ask whether the automaton $\mathcal{A}$ specifies some graph satisfying a certain property~$\Phi$. Our structural results show that we can answer this question for all "typical" graph properties. In order to show our results, we split $L$ into a finite union of subsets and every subset of this union defines in a natural way a single finite graph $F$ where some edges and vertices are marked. The marked graph in turn defines an infinite graph $F^\infty$ and therefore the family of finite subgraphs of $F^\infty$ where $F$ appears as an induced subgraph. This yields a geometric description of all graphs specified by $L$ based on splitting $L$ into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.Open AccessProperties of Graphs Specified by a Regular Language
Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property $\Phi$. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying $\Phi$ in the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language $L$ if a certain torsion condition is satisfied. This condition holds trivially if $L$ is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet $\Sigma$, and we define a regular set $\mathbb{G}\subseteq \Sigma^*$ such that every nonempty word $w\in \mathbb{G}$ defines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over $\Sigma$. Then, we ask whether the automaton $\mathcal{A}$ specifies some graph satisfying a certain property~$\Phi$. Our structural results show that we can answer this question for all "typical" graph properties. In order to show our results, we split $L$ into a finite union of subsets and every subset of this union defines in a natural way a single finite graph $F$ where some edges and vertices are marked. The marked graph in turn defines an infinite graph $F^\infty$ and therefore the family of finite subgraphs of $F^\infty$ where $F$ appears as an induced subgraph. This yields a geometric description of all graphs specified by $L$ based on splitting $L$ into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.