Use este identificador para citar ou linkar para este item: http://www.repositorio.ufc.br/handle/riufc/17668
Título: Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais
Título em inglês: Descriptive complexity of the logic of higher order with lower fixed point and analysis of expression of some modal logics
Autor(es): Freire, Cibele Matos
Orientador(es): Martins , Ana Teresa de Castro
Palavras-chave: Logigas e semantica de programas
Complexidade descritiva
Logica modal
Logicas de ordem superior
Hierarquia determinstica de tempo exponencial
Operadores de ponto fixo
Descriptive complexity
Modal logic
Higher-order logics
Deterministic exponential time hierarchy
Fixed-point operators
Modalidade (Lógica)
Lógica de computador
Teoria do ponto fixo
Complexidade computacional
Data do documento: 2010
Citação: FREIRE, C. M. (2010)
Resumo: Em Complexidade Descritiva investigamos o uso de logicas para caracterizar classes problemas pelo vies da complexidade. Desde 1974, quando Fagin provou que NP e capturado pela logica existencial de segunda-ordem, considerado o primeiro resultado da area, outras relac~oes entre logicas e classes de complexidade foram estabelecidas. Os resultados mais conhecidos normalmemte envolvem logica de primeira-ordem e suas extens~oes, e classes de complexidade polinomiais em tempo ou espaco. Alguns exemplos são que a l ogica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a l ogica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertação, analisaremos inicialmente a expressividade de algumas l ogicas modais com rela cão ao problema de decisão REACH e veremos que e poss vel express a-lo com as l ogicas temporais CTL e CTL . Analisaremos tamb em o uso combinado de l ogicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada n vel dessa hierarquia captura cada n vel da hierarquia determin stica em tempo exponencial. Como corol ario, provamos que a hierarquia de HOi(LFP) não colapsa, ou seja, HOi(LFP) HOi+1(LFP)
Abstract: In Descriptive Complexity, we investigate the use of logics to characterize computational classes os problems through complexity. Since 1974, when Fagin proved that the class NP is captured by existential second-order logic, considered the rst result in this area, other relations between logics and complexity classes have been established. Wellknown results usually involve rst-order logic and its extensions, and complexity classes in polynomial time or space. Some examples are that the rst-order logic extended by the least xed-point operator captures the class P and the second-order logic extended by the transitive closure operator captures the class PSPACE. In this dissertation, we will initially analyze the expressive power of some modal logics with respect to the decision problem REACH and see that is possible to express it with temporal logics CTL and CTL . We will also analyze the combined use of higher-order logics extended by the least xed-point operator and obtain as result that each level of this hierarchy captures each level of the deterministic exponential time hierarchy. As a corollary, we will prove that the hierarchy of HOi(LFP), for i 2, does not collapse, that is, HOi(LFP) HOi+1(LFP)
Resumo em espanhol: FREIRE, Cibele Matos. Complexidade descritiva das lógicas de ordem superior com menor ponto fixo e análise de expressividade de algumas lógicas modais. 2010. 54 f. : Dissertação (mestrado) - Universidade Federal do Ceará, Centro de Ciências, Departamento de Computação, Fortaleza-CE, 2010.
URI: http://www.repositorio.ufc.br/handle/riufc/17668
Aparece nas coleções:DCOMP - Dissertações defendidas na UFC

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2010_dis_cmfreire.pdf416,79 kBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.