List of Publications

[PV] = Link to Publisher's Version
[Pre] = Link to Preprint Version

[Talk] = Link to presentation

FSTTCS 2021 [PV] [Talk] [Pre]

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)

In the Intersection Non-emptiness problem, we are given a list of finite automata A_1, A_2,… , A_m over a common alphabet Σ as input, and the goal is to determine whether some string w ∈ Σ^* lies in the intersection of the languages accepted by the automata in the list. We analyze the complexity of the Intersection Non-emptiness problem under the promise that all input automata accept a language in some level of the dot-depth hierarchy, or some level of the Straubing-Thérien hierarchy. Automata accepting languages from the lowest levels of these hierarchies arise naturally in the context of model checking. We identify a dichotomy in the dot-depth hierarchy by showing that the problem is already NP-complete when all input automata accept languages of the levels B_0 or B_{1/2} and already PSPACE-hard when all automata accept a language from the level B_1. Conversely, we identify a tetrachotomy in the Straubing-Thérien hierarchy. More precisely, we show that the problem is in AC^0 when restricted to level L_0; complete for L or NL, depending on the input representation, when restricted to languages in the level L_{1/2}; NP-complete when the input is given as DFAs accepting a language in L_1 or L_{3/2}; and finally, PSPACE-complete when the input automata accept languages in level L_2 or higher. Moreover, we show that the proof technique used to show containment in NP for DFAs accepting languages in L_1 or L_{3/2} does not generalize to the context of NFAs. To prove this, we identify a family of languages that provide an exponential separation between the state complexity of general NFAs and that of partially ordered NFAs. To the best of our knowledge, this is the first superpolynomial separation between these two models of computation.

 

CONCUR 2021 [PV] [Pre]

Decomposing Permutation Automata
(Ismaël Jecker, Nicolas Mazzocchi, Petra Wolf)

A deterministic finite automaton (DFA) 𝒜 is composite if its language L(𝒜) can be decomposed into an intersection ⋂_{i = 1}^k L(𝒜_i) of languages of smaller DFAs. Otherwise, 𝒜 is prime. This notion of primality was introduced by Kupferman and Mosheiff in 2013, and while they proved that we can decide whether a DFA is composite, the precise complexity of this problem is still open, with a doubly-exponential gap between the upper and lower bounds. In this work, we focus on permutation DFAs, i.e., those for which the transition monoid is a group. We provide an NP algorithm to decide whether a permutation DFA is composite, and show that the difficulty of this problem comes from the number of non-accepting states of the instance: we give a fixed-parameter tractable algorithm with the number of rejecting states as the parameter. Moreover, we investigate the class of commutative permutation DFAs. Their structural properties allow us to decide compositionality in NL, and even in LOGSPACE if the alphabet size is fixed. Despite this low complexity, we show that complex behaviors still arise in this class: we provide a family of composite DFAs each requiring polynomially many factors with respect to its size. We also consider the variant of the problem that asks whether a DFA is k-factor composite, that is, decomposable into k smaller DFAs, for some given integer k ∈ ℕ. We show that, for commutative permutation DFAs, restricting the number of factors makes the decision computationally harder, and yields a problem with tight bounds: it is NP-complete. Finally, we show that in general, this problem is in PSPACE, and it is in LOGSPACE for DFAs with a singleton alphabet.

 

MFCS 2021 [PV]

Order Reconfiguration Under Width Constraints
(Emmanuel Arrighi, Henning Fernau, Mateus de Oliveira Oliveira, Petra Wolf)

In this work, we consider the following order reconfiguration problem: Given a graph G together with linear orders ω and ω' of the vertices of G, can one transform ω into ω' by a sequence of swaps of adjacent elements in such a way that at each time step the resulting linear order has cutwidth (pathwidth) at most k? We show that this problem always has an affirmative answer when the input linear orders ω and ω' have cutwidth (pathwidth) at most k/2. Using this result, we establish a connection between two apparently unrelated problems: the reachability problem for two-letter string rewriting systems and the graph isomorphism problem for graphs of bounded cutwidth. This opens an avenue for the study of the famous graph isomorphism problem using techniques from term rewriting theory.

 

DLT 2021 [PV] [Pre]

Properties of Graphs Specified by a Regular Language
(Volker Diekert, Henning Fernau, Petra Wolf)

Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property Φ. 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 if is there exists one graph satisfying Φ? We approach this question by using formal languages for specifying families of graphs. In particular, 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.
In order to show our results, we split L into a finite union of subsets Lα. Every Lα defines in a natural way a single finite graph Fα where some edges and vertices are marked. The marked graph in turn defines a set of graphs with a geometric description using the notion of graph retraction and where Fα appears as an induced subgraph.

MFCS 2021 [PV] [Pre]

A Timecop's Chase Around the Table
(Nils Morawietz, Petra Wolf)

We consider the cops and robbers game variant consisting of one cop and one robber on time-varying graphs (TVG). The considered TVGs are edge periodic graphs, i.e., for each edge, a binary string s_e determines in which time step the edge is present, namely the edge e is present in time step t if and only if the string s_e contains a 1 at position t mod |s_e|. This periodicity allows for a compact representation of an infinite TVG. We prove that even for very simple underlying graphs, i.e., directed and undirected cycles the problem whether a cop-winning strategy exists is NP-hard and W[1]-hard parameterized by the number of vertices. Our second main result are matching lower bounds for the ratio between the length of the underlying cycle and the least common multiple (lcm) of the lengths of binary strings describing edge-periodicies over which the graph is robber-winning. Our third main result improves the previously known EXPTIME upper bound for Periodic Cop & Robber on general edge periodic graphs to PSPACE-membership.

 
 

IJCAI 2021 [PV] [Pre]

Diversity in Kemeny Rank Aggregation: A Parameterized Approach
(Emmanuel Arrighi, Henning Fernau, Daniel Lokshtanov, Mateus de Oliveira Oliveira, Petra Wolf)

In its most traditional setting, the main concern of optimization theory is the search for optimal solutions for instances of a given computational problem. A recent trend of research in artificial intelligence, called solution diversity, has focused on the development of notions of optimality that may be more appropriate in settings where subjectivity is essential. The idea is instead of aiming at the development of algorithms that output a single optimal solution, the goal is to investigate algorithms outputting a small set of sufficiently good solutions that are sufficiently diverse from one another. This way, the user has the opportunity to choose the solution being most appropriate to the context at hand. It also displays the richness of the solution space.
When combined with techniques from parameterized complexity theory, the paradigm of diversity of solutions offers a powerful algorithmic framework to address problems of practical relevance. In this work, we investigate the impact of this combination in the field of Kemeny Rank Aggregation, a well-studied class of problems lying in the intersection of order theory and social choice theory and also in the field of order theory itself. In particular, we show that the Kemeny Rank Aggregation problem is fixed-parameter tractable with respect to natural parameters providing natural formalizations of the notions of diversity and of the notion of a sufficiently good solution. Our main results work both when considering the traditional setting of aggregation over linearly ordered votes, and in the more general setting where votes are partially ordered.

 

DCC 2021 [PV] [Talk] [Pre]

Improving Run Length Encoding by Preprocessing
(Sven Fiergolla, Petra Wolf)

The Run Length Encoding (RLE) compression method is a long standing simple lossless compression scheme which is easy to implement and achieves a good compression on input data which contains repeating consecutive symbols. In its pure form RLE is not applicable on natural text or other input data with short sequences of identical symbols. We present a combination of preprocessing steps that turn arbitrary input data in a byte-wise encoding into a bit-string which is highly suitable for RLE compression. The main idea is to first read all most significant bits of the input byte-string, followed by the second most significant bit, and so on. We combine this approach by a dynamic byte remapping as well as a Burrows-Wheeler-Scott transform on a byte level. Finally, we apply a Huffman Encoding on the output of the bit-wise RLE encoding to allow for more dynamic lengths of code words encoding runs of the RLE. With our technique we can achieve a lossless average compression which is better than the standard RLE compression by a factor of 8 on average.

 

FSTTCS 2020 [PV] [Talk]

Width Notions for Ordering-Related 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 NP-complete, 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 sub-exponential time algorithms for ordering problems.

 

FSTTCS 2020 [PV] [Talk] [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 PSPACE-complete we also observe NP-complete 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.

 

FSTTCS 2020 [PV] [Talk] [Pre]

Synchronization of Deterministic Visibly Push-Down 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 push-down 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 push-down automata, it is decidable for deterministic visibly push-down 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 sub-classes of deterministic very visibly push-down 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.

 

MFCS 2020 [PV] [Talk] [Pre]

Synchronizing Deterministic Push-Down 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 so-called 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 one-counter automata. This is also true for another classical mild extension of regularity, namely that of deterministic one-turn push-down automata. However, when we combine both restrictions, we arrive at scenarios with a PSPACE-complete (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 push-down 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.

 

TCS [PV] / ICTCS 2020 [PV] [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 intreg-problem of P, which asks for a given DFA A, whether the intersection of P with L(A) is non-empty. The intreg-problem 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 intreg-problem has been answered positively for several NP- and even PSPACE-complete problems, we are presenting natural problems even from L with an undecidable intreg-problem. We also discuss alphabet sizes and different encoding-schemes elaborating the boundary between problem-variants with a decidable respectively undecidable intreg-problem.

 

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 PSPACE-complete 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 polynomial-time 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 ILP-Instance in a Regular Set of ILP-Instances
(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 P-instances contains a positive one. Since intreg(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 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 intreg-problem for the well-known NP-complete problem Integer Linear Programming (ILP). It is shown that any DFA that describes a set of ILP-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  intreg(ILP).

 

FUN 2018 [PV]

We study the game Greedy Spiders, a two-player strategic defense game, on planar graphs and show PSPACE-completeness 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_2-hardness results.

 

LATA 2018 [PV]

For a regular set R of quantified Boolean formulae we decide whether R contains a true formula. We conclude that there is a PSPACE-complete 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.

 

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_reg-problem 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_reg-problem for a number of different graph problems and give general criteria that give decision procedures for these Int_reg-problems. 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 interchange-arguments from the field of formal language theory with the graph operations induced on the encoded graph. Our techniques apply among others to the Int_reg-problem of well-known graph problems like Vertex Cover and Independent Set, as well as to subgraph problems, graph-edit problems and graph-partitioning problems, including coloring problems.