Browsing Bergen Open Research Archive by Author "Oliveira, Mateus De Oliveira"

Now showing items 1-7 of 7

    • Co-Degeneracy and Co-Treewidth: Using the Complement to Solve Dense Instances 

      Duarte, Gabriel; Oliveira, Mateus De Oliveira; Souza, Uéverton S. (Journal article; Peer reviewed, 2021)
      Clique-width and treewidth are two of the most important and useful graph parameters, and several problems can be solved efficiently when restricted to graphs of bounded clique-width or treewidth. Bounded treewidth implies ...

    • Diversity of solutions: An exploration through the lens of fixed-parameter tractability theory 

      Baste, Julien; Fellows, Michael Ralph; Jaffke, Lars; Masařík, Tomáš; Oliveira, Mateus De Oliveira; Philip, Geevarghese; Rosamond, Frances (Journal article; Peer reviewed, 2022)
      When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse ...

    • On Supergraphs Satisfying CMSO Properties 

      Oliveira, Mateus De Oliveira (Journal article; Peer reviewed, 2021)
      Let CMSO denote the counting monadic second order logic of graphs. We give a constructive proof that for some computable function f, there is an algorithm A that takes as input a CMSO sentence φ, a positive integer t, and ...

    • On the Complexity of Intersection Non-emptiness for Star-Free Language Classes 

      Arrighi, Emmanuel Jean Paul Pierre; Fernau, Henning; Hoffmann, Stefan; Holzer, Markus; Jecker, Ismaël; Oliveira, Mateus De Oliveira; Wolf, Petra (Journal article; Peer reviewed, 2021)
      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 ...

    • Order Reconfiguration Under Width Constraints 

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

    • Second-Order Finite Automata 

      de Melo, Alexsander Andrade; Oliveira, Mateus De Oliveira (Journal article; Peer reviewed, 2022)
      Traditionally, finite automata theory has been used as a framework for the representation of possibly infinite sets of strings. In this work, we introduce the notion of second-order finite automata, a formalism that combines ...

    • Unitary Branching Programs: Learnability and Lower Bounds 

      Diaz Andino, Fidel Ernesto; Kokkou, Maria; Oliveira, Mateus De Oliveira; Vadiee, Farhad (Journal article; Peer reviewed, 2021)
      Bounded width branching programs are a formalism that can be used to capture the notion of non-uniform constant-space computation. In this work, we study a generalized version of bounded width branching programs where ...