Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/47656
Title in Portuguese: Parameterized complexity investigations on the first-order satisfiability and matching problems
Title: Parameterized complexity investigations on the first-order satisfiability and matching problems
Author: Morais, Luis Henrique Bustamante de
Advisor(s): Martins, Ana Teresa de Castro
Co-advisor(s): Ferreira, Francicleber Martins
Keywords: Parameterized complexity
Satisfiability
Matching
First-order logic
Issue Date: 2019
Citation: MORAIS, Luis Henrique Bustamante de. Parameterized complexity investigations on the first-order satisfiability and matching problems. 2019. 68 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2019.
Abstract in Portuguese: A teoria da complexidade parametrizada é uma sub-área da teoria da complexidade computacional em que a análise de tempo computacional considera, além do tamanho da entrada, um termo adicional e que permite perceber um “certa tratabilidade” para muitos problemas outrora intratáveis. Muitos problemas da Lógica tem sido tratados por alguma técnica de análise parametrizadas. Nós exploramos dois problemas da Lógica usando ferramentas da complexidade parametrizada. Inicialmente, nós estudamos a complexidade parametrizada do problema da satisfatibilidade para alguns fragmentos definidos por prefixo e o vocabulário da lógica de primeira-ordem. Nós consideramos parâmetros naturais retirados da definição desses fragmentos tais como o posto de quantificadores e o número de símbolos relacionais. Seguindo a classificação clássica dos fragmentos decidíveis definidos pelo prefixo e pelo vocabulário, nós observamos que, quando combinados com a propriedade de modelo finito, muitos fragmentos tem a satisfatibilidade tratável por um parâmetro fixo com respeito a um desses parâmetros. Em um segundo momento, nós aplicamos a complexidade parametrizada para a classificação dos problemas de matching associativo, comutativo e associativo-comutativo ({A, C, AC}-MATCHING) para diferentes parametrizações. Nós inicialmente consideramos o número de variáveis, o tamanho da substituição e o tamanho do vocabulário como parâmetros. Combinando o tamanho da substiuição e o tamanho do vocabulário, nós obtivemos a tratabilidade por um parâmetro fixo para esses problemas. Para os outros casos, nós obtivemos a pertinência em W[P] para o matching comutativo (C-MATCHING) considerando o número de variáveis e, para {A, AC}-MATCHING, quando consideramos o tamanho da substituição.
Abstract: Parameterized complexity theory is a subarea of computational complexity theory in which the run-time analysis of a computational problem handles, besides the input size, an additional term that allows us to recognize “some kind of tractability” for many previously intractable problems. 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.
URI: http://www.repositorio.ufc.br/handle/riufc/47656
metadata.dc.type: Tese
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2019_tese_lhbmorais.pdf753,93 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.