Complexidade descritiva das lÃgicas de ordem superior com menor ponto fixo e anÃlise de expressividade de algumas lÃgicas modais / Descriptive complexity of the logic of higher order with lower fixed point and analysis of expression of some modal logics
AUTOR(ES)
Cibele Matos Freire
FONTE
IBICT - Instituto Brasileiro de Informação em Ciência e Tecnologia
DATA DE PUBLICAÇÃO
13/08/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 logica de primeira-ordem estendida com o operador de menor ponto xo captura a clsse P e que a logica de segunda-ordem estendida com o operador de fecho transitivo captura a classe PSPACE. Nesta dissertaÃÃo, analisaremos inicialmente a expressividade de algumas logicas modais com relacÃo ao problema de decisÃo REACH e veremos que e possvel expressa-lo com as logicas temporais CTL e CTL. Analisaremos tambem o uso combinado de logicas de ordem superior com o operador de menor ponto xo e obteremos como resultado que cada nvel dessa hierarquia captura cada nvel da hierarquia determinstica em tempo exponencial. Como corolario, provamos que a hierarquia de HOi(LFP) nÃo colapsa, ou seja, HOi(LFP) HOi+1(LFP)
ASSUNTO(S)
logicas 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
