Search

Your search keyword '"de Oliveira Oliveira, Mateus"' showing total 132 results
Start Over Author "de Oliveira Oliveira, Mateus"
132 results on '"de Oliveira Oliveira, Mateus"'

1. Synthesis and Analysis of Petri Nets from Causal Specifications

Author

de Oliveira Oliveira, Mateus, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Shoham, Sharon, editor, and Vizel, Yakir, editor

Published
2022
Full Text
View/download PDF

6. Succinct Monotone Circuit Certification: Planarity and Parameterized Complexity

Author

Alves, Mateus Rodrigues, de Oliveira Oliveira, Mateus, Silva, Janio Carlos Nascimento, dos Santos Souza, Uéverton, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Kim, Donghyun, editor, Uma, R. N., editor, Cai, Zhipeng, editor, and Lee, Dong Hoon, editor

Published
2020
Full Text
View/download PDF

7. Second-Order Finite Automata

Author

de Melo, Alexsander Andrade, de Oliveira Oliveira, Mateus, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, and Fernau, Henning, editor

Published
2020
Full Text
View/download PDF

8. On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection

Author

de Oliveira Oliveira, Mateus, Wehar, Michael, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, Jonoska, Nataša, editor, and Savchuk, Dmytro, editor

Published
2020
Full Text
View/download PDF

10. State Canonization and Early Pruning in Width-Based Automated Theorem Proving

Author

Mateus de Oliveira Oliveira and Farhad Vadiee, de Oliveira Oliveira, Mateus, Vadiee, Farhad, Mateus de Oliveira Oliveira and Farhad Vadiee, de Oliveira Oliveira, Mateus, and Vadiee, Farhad

Abstract

Width-based automated theorem proving is a framework where counter-examples for graph theoretic conjectures are searched width-wise relative to some graph width measure, such as treewidth or pathwidth. In a recent work it has been shown that dynamic programming algorithms operating on tree decompositions can be combined together with the purpose of width-based theorem proving. This approach can be used to show that several long-standing conjectures in graph theory can be tested in time 2^{2^{k^{O(1)}}} on the class of graphs of treewidth at most k. In this work, we give the first steps towards evaluating the viability of this framework from a practical standpoint. At the same time, we advance the framework in two directions. First, we introduce a state-canonization technique that significantly reduces the number of states evaluated during the search for a counter-example of the conjecture. Second, we introduce an early-pruning technique that can be applied in the study of conjectures of the form ℙ₁ → ℙ₂, for graph properties ℙ₁ and ℙ₂, where ℙ₁ is a property closed under subgraphs. As a concrete application, we use our framework in the study of graph theoretic conjectures related to coloring triangle free graphs. In particular, our algorithm is able to show that Reed’s conjecture for triangle free graphs is valid on the class of graphs of pathwidth at most 5, and on graphs of treewidth at most 3. Perhaps more interestingly, our algorithm is able to construct in a completely automated way counter-examples for non-valid strengthenings of Reed’s conjecture. These are the first results showing that width-based automated theorem proving is a promising avenue in the study of graph-theoretic conjectures.

Published
2024
Full Text
View/download PDF

11. Learning from positive and negative examples : New proof for binary alphabets

Author

Lingg, Jonas, De Oliveira Oliveira, Mateus, Wolf, Petra, Lingg, Jonas, De Oliveira Oliveira, Mateus, and Wolf, Petra

Abstract

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 consistency, we mean that A accepts all strings in P and rejects all strings in N. It is well known that this problem is NP-complete. In the literature, it is stated that NP-hardness holds even in the case of a binary alphabet. As a standard reference for this theorem, the work of Gold from 1978 is either cited or adapted. Nevertheless, the results in Gold's work are stated in terms of Mealy machines, and not in terms of deterministic finite automata (DFAs) as most commonly defined. As Mealy machines are equipped with an output function, they can be more compact than DFAs which accept the same language. We show that the adaptations of Gold's construction for Mealy machines stated in the literature have some issues, and provide a correct proof for the fact that the DFA-consistency problem for binary alphabets is NP-complete.

Published
2024
Full Text
View/download PDF

12. On the Width of Regular Classes of Finite Structures

Author

Andrade de Melo, Alexsander, de Oliveira Oliveira, Mateus, Goos, Gerhard, Founding Editor, Hartmanis, Juris, Founding Editor, Bertino, Elisa, Editorial Board Member, Gao, Wen, Editorial Board Member, Steffen, Bernhard, Editorial Board Member, Woeginger, Gerhard, Editorial Board Member, Yung, Moti, Editorial Board Member, and Fontaine, Pascal, editor

Published
2019
Full Text
View/download PDF

14. Intersection Non-emptiness and Hardness Within Polynomial Time

Author

de Oliveira Oliveira, Mateus, Wehar, Michael, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Hoshi, Mizuho, editor, and Seki, Shinnosuke, editor

Published
2018
Full Text
View/download PDF

15. On Weak Isomorphism of Rooted Vertex-Colored Graphs

Author

Jaffke, Lars, de Oliveira Oliveira, Mateus, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brandstädt, Andreas, editor, Köhler, Ekkehard, editor, and Meer, Klaus, editor

Published
2018
Full Text
View/download PDF

16. Graph Amalgamation Under Logical Constraints

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series Editor, Kanade, Takeo, Series Editor, Kittler, Josef, Series Editor, Kleinberg, Jon M., Series Editor, Mattern, Friedemann, Series Editor, Mitchell, John C., Series Editor, Naor, Moni, Series Editor, Pandu Rangan, C., Series Editor, Steffen, Bernhard, Series Editor, Terzopoulos, Demetri, Series Editor, Tygar, Doug, Series Editor, Weikum, Gerhard, Series Editor, Brandstädt, Andreas, editor, Köhler, Ekkehard, editor, and Meer, Klaus, editor

Published
2018
Full Text
View/download PDF

19. Parameterized Provability in Equational Logic

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Schmidt, Renate A., editor, and Nalon, Cláudia, editor

Published
2017
Full Text
View/download PDF

22. A Slice Theoretic Approach for Embedding Problems on Digraphs

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Mayr, Ernst W., editor

Published
2016
Full Text
View/download PDF

23. Causality in Bounded Petri Nets is MSO Definable

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Väänänen, Jouko, editor, Hirvonen, Åsa, editor, and de Queiroz, Ruy, editor

Published
2016
Full Text
View/download PDF

24. Satisfiability via Smooth Pictures

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Creignou, Nadia, editor, and Le Berre, Daniel, editor

Published
2016
Full Text
View/download PDF

25. MSO Logic and the Partial Order Semantics of Place/Transition-Nets

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Leucker, Martin, editor, Rueda, Camilo, editor, and Valencia, Frank D., editor

Published
2015
Full Text
View/download PDF

26. Reachability in Graph Transformation Systems and Slice Languages

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Parisi-Presicce, Francesco, editor, and Westfechtel, Bernhard, editor

Published
2015
Full Text
View/download PDF

27. On the Satisfiability of Quantum Circuits of Small Treewidth

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Beklemishev, Lev D., editor, and Musatov, Daniil V., editor

Published
2015
Full Text
View/download PDF

28. Synchronization and Diversity of Solutions

Author

Arrighi, Emmanuel, Fernau, Henning, De Oliveira Oliveira, Mateus, Wolf, Petra, Arrighi, Emmanuel, Fernau, Henning, De Oliveira Oliveira, Mateus, and Wolf, Petra

Abstract

A central computational problem in the realm of automata theory is the problem of determining whether a finite automaton A has a synchronizing word. This problem has found applications in a variety of subfields of artificial intelligence, including planning, robotics, and multi-agent systems. In this work, we study this problem within the framework of diversity of solutions, an up-and-coming trend in the field of artificial intelligence where the goal is to compute a set of solutions that are sufficiently distinct from one another. We define a notion of diversity of solutions that is suitable for contexts were solutions are strings that may have distinct lengths. Using our notion of diversity, we show that for each fixed r ∈ N, each fixed finite automaton A, and each finite automaton B given at the input, the problem of determining the existence of a diverse set {w1,w2, . . . ,wr} ⊆ L(B) of words that are synchronizing for A can be solved in polynomial time. Finally, we generalize this result to the realm of conformant planning, where the goal is to devise plans that achieve a goal irrespectively of initial conditions and of nondeterminism that may occur during their execution.

Published
2023
Full Text
View/download PDF

29. From Width-Based Model Checking to Width-Based Automated Theorem Proving

Author

De Oliveira Oliveira, Mateus, Vadiee, Farhad, De Oliveira Oliveira, Mateus, and Vadiee, Farhad

Abstract

In the field of parameterized complexity theory, the study of graph width measures has been intimately connected with the development of width-based model checking algorithms for combinatorial properties on graphs. In this work, we introduce a general framework to convert a large class of width-based model-checking algorithms into algorithms that can be used to test the validity of graph-theoretic conjectures on classes of graphs of bounded width. Our framework is modular and can be applied with respect to several well-studied width measures for graphs, including treewidth and cliquewidth. As a quantitative application of our framework, we prove analytically that for several long-standing graph-theoretic conjectures, there exists an algorithm that takes a number k as input and correctly determines in time double-exponential in a polynomial of k whether the conjecture is valid on all graphs of treewidth at most k. These upper bounds, which may be regarded as upper-bounds on the size of proofs/disproofs for these conjectures on the class of graphs of treewidth at most k, improve significantly on theoretical upper bounds obtained using previously available techniques.

Published
2023
Full Text
View/download PDF

38. Subgraphs Satisfying MSO Properties on z-Topologically Orderable Digraphs

Author

de Oliveira Oliveira, Mateus, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Gutin, Gregory, editor, and Szeider, Stefan, editor

Published
2013
Full Text
View/download PDF

39. Canonizable Partial Order Generators

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Dediu, Adrian-Horia, editor, and Martín-Vide, Carlos, editor

Published
2012
Full Text
View/download PDF

40. Hasse Diagram Generators and Petri Nets

Author

de Oliveira Oliveira, Mateus, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Franceschinis, Giuliana, editor, and Wolf, Karsten, editor

Published
2009
Full Text
View/download PDF

41. On the Satisfiability of Smooth Grid CSPs

Author

Alferov, Vasily, de Oliveira Oliveira, Mateus, Alferov, Vasily, and de Oliveira Oliveira, Mateus

Abstract

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 grid CSPs by analyzing, from an experimental perspective, a symbolic parameter called smoothness. More specifically, we implement an algorithm that provably works in polynomial time on grids of polynomial smoothness. Subsequently, we compare our algorithm with standard combinatorial optimization techniques, such as SAT-solving and integer linear programming (ILP). For this comparison, we use a class of grid-CSPs encoding the pigeonhole principle. We demonstrate, empirically, that these CSPs have polynomial smoothness and that our algorithm terminates in polynomial time. On the other hand, as strong evidence that the grid-like encoding is not destroying the essence of the pigeonhole principle, we show that the standard propositional translation of pigeonhole CSPs remains hard for state-of-the-art SAT solvers, such as minisat and glucose, and even to state-of-the-art integer linear-programming solvers, such as Coin-OR CBC.

Published
2022
Full Text
View/download PDF

42. On the Satisfiability of Smooth Grid CSPs

Author

Vasily Alferov and Mateus de Oliveira Oliveira, Alferov, Vasily, de Oliveira Oliveira, Mateus, Vasily Alferov and Mateus de Oliveira Oliveira, Alferov, Vasily, and de Oliveira Oliveira, Mateus

Abstract

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 grid CSPs by analyzing, from an experimental perspective, a symbolic parameter called smoothness. More specifically, we implement an algorithm that provably works in polynomial time on grids of polynomial smoothness. Subsequently, we compare our algorithm with standard combinatorial optimization techniques, such as SAT-solving and integer linear programming (ILP). For this comparison, we use a class of grid-CSPs encoding the pigeonhole principle. We demonstrate, empirically, that these CSPs have polynomial smoothness and that our algorithm terminates in polynomial time. On the other hand, as strong evidence that the grid-like encoding is not destroying the essence of the pigeonhole principle, we show that the standard propositional translation of pigeonhole CSPs remains hard for state-of-the-art SAT solvers, such as minisat and glucose, and even to state-of-the-art integer linear-programming solvers, such as Coin-OR CBC.

Published
2022
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results