• Compressing permutation groups into grammars and polytopes. A graph embedding approach 

      Jaffke, Lars; De Oliveira Oliveira, Mateus; Tiwary, Hans Raj (Journal article; Peer reviewed, 2020)
      It can be shown that each permutation group G ⊑ 𝕊_n can be embedded, in a well defined sense, in a connected graph with O(n+|G|) vertices. Some groups, however, require much fewer vertices. For instance, 𝕊_n itself can ...
    • Learning from positive and negative examples: New proof for binary alphabets 

      Lingg, Jonas; De Oliveira Oliveira, Mateus; Wolf, Petra Henrike Karola (Journal article; Peer reviewed, 2024)
      One of the most fundamental problems in computational learning theory is the problem of learning a finite automaton A consistent with a finite set P of positive examples and with a finite set N of negative examples. By ...
    • On the Satisfiability of Smooth Grid CSPs 

      De Oliveira Oliveira, Mateus; Alferov, Vasily (Journal article; Peer reviewed, 2022)
      Many important NP-hard problems, arising in a wide variety of contexts, can be reduced straightforwardly to the satisfiability problem for CSPs whose underlying graph is a grid. In this work, we push forward the study of ...
    • Order Reconfiguration under Width Constraints 

      Arrighi, Emmanuel Jean Paul Pierre; Fernau, Henning; De Oliveira Oliveira, Mateus; Wolf, Petra Henrike Karola (Journal article; Peer reviewed, 2023)
      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 ...
    • Synthesis and Analysis of Petri Nets from Causal Specifications 

      De Oliveira Oliveira, Mateus (Journal article; Peer reviewed, 2022)
      Petri nets are one of the most prominent system-level formalisms for the specification of causality in concurrent, distributed, or multi-agent systems. This formalism is abstract enough to be analyzed using theoretical ...
    • Three Is Enough for Steiner Trees 

      Arrighi, Emmanuel; De Oliveira Oliveira, Mateus (Journal article; Peer reviewed, 2021)
      In the Steiner tree problem, the input consists of an edge-weighted graph G together with a set S of terminal vertices. The goal is to find a minimum weight tree in G that spans all terminals. This fundamental NP-hard ...
    • Width Notions for Ordering-Related Problems 

      Arrighi, Emmanuel; Fernau, Henning; De Oliveira Oliveira, Mateus; Wolf, Petra (Journal article; Peer reviewed, 2020)
      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 ...