Título: Parameterized Complexity Investigations on the First-order

Satisfiability and Matching Problems

Data: 30/08/2019

Horário: 14:00h

Local: Sala de Seminários - Bloco 952

Resumo:

Parameterized complexity theory is a subarea of computational complexity theory in which the run-time analysis of a computational problem handle, besides the input size, an additional term. Many problems from Logic have been received attention by some parameterized analysis technique. We explore two logical tasks using the tools of the parameterized complexity. First, we study the parameterized complexity of the satisfiability problem for some prefix-vocabulary fragments of first-order logic. We consider the natural parameters emerging from the definition of these fragments, such as the quantifier rank, and the number of relation symbols. Following the classical classification of decidable prefix-vocabulary fragments, we observed that, when combining with the finite model property, many fragments have fixed-parameter tractability for the satisfiability concerning some of these parameters. Secondly, we apply parameterized complexity theory for classification for associative, commutative, and associative-commutative matching problems ({A, C, AC}-MATCHING) considering different parameterizations. We primarily consider the number of variables, the size of the substitution, and the size of the vocabulary as parameters. Combining the size of the substitution and the size of the vocabulary, we established the fixed-parameter tractability for these matching problems. For the other cases, we obtained the membership in W[P] for C-MATCHING for the number of variables and, for {A, AC}-MATCHING, when considering the size of the substitution.

Banca:

• Profª. Drª. Ana Teresa de Castro Martins(MDCC/UFC - Orientador)
• Prof. Dr. Francicleber Martins Ferreira (MDCC/UFC - Coorientador)
• Prof. Dr. Carlos Eduardo Fisch de Brito (MDCC/UFC)
• Prof. Dr. Edward Hermann Haeusler (PUC-Rio)
• Prof. Dr. Mário R. Folhadela Benevides (COPPE/UFRJ)