Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/47656
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorMartins, Ana Teresa de Castro-
dc.contributor.authorMorais, Luis Henrique Bustamante de-
dc.date.accessioned2019-11-11T18:47:58Z-
dc.date.available2019-11-11T18:47:58Z-
dc.date.issued2019-
dc.identifier.citationMORAIS, 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.pt_BR
dc.identifier.urihttp://www.repositorio.ufc.br/handle/riufc/47656-
dc.description.abstractParameterized 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.pt_BR
dc.language.isoenpt_BR
dc.subjectParameterized complexitypt_BR
dc.subjectSatisfiabilitypt_BR
dc.subjectMatchingpt_BR
dc.subjectFirst-order logicpt_BR
dc.titleParameterized complexity investigations on the first-order satisfiability and matching problemspt_BR
dc.typeTesept_BR
dc.contributor.co-advisorFerreira, Francicleber Martins-
dc.description.abstract-ptbrA 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.pt_BR
dc.title.enParameterized complexity investigations on the first-order satisfiability and matching problemspt_BR
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.