Lógicas Modais e Complexidade Descritiva

• Cibele Matos Freire UFC
• Ana Teresa Martins UFC

Resumo

Na Complexidade Computacional, medimos a eficiência de um algoritmo pelo tempo e espaço dispendido em sua execução, induzindo a definição de classes de problemas. Em 1974, Fagin demonstrou que a classe NP é aquela cujos problemas são descritos pela lógica de segunda-ordem existencial. Este resultado mostrou que a complexidade de um problema pode ser caracterizado por um viés independente da máquina, através da expressividade de uma linguagem capaz de definir uma classe a qual este problema pertence, e lançou a área de Complexidade Descritiva. Estamos aqui interessados no papel dos operadores modais das lógicas K, S4, S5, CTL e CTL^∗ na expressão de problemas de decisão e caracterização de classes de problemas.

Palavras-chave: Representação do conhecimento, Expressividade de lógicas, Complexidade Computacional, Complexidade Descritiva

Referências

Blackburn, P., de Rijke, M., and Venema, Y. (2001). Modal Logic. Cambridge University Press.

Chellas, B. F. (1980). Modal logic: an introduction. Cambridge University Press.

Davis, M. D., Sigal, R., and Weyuker, E. J. (1994). Computability, complexity, and languages: fundamentals of theoretical computer science. Academic Press, 2nd edition.

Ebbinghaus, H.-D., Flum, J., and Thomas, W. (1994). Mathematical Logic. Springer, 2nd edition.

Fagin, R. (1974). Generalized first-order spectra and polynomial-time recognizable sets. In Complexity of computation, volume 7, pages 43–73. AMS Bookstore.

Immerman, N. (1999). Descriptive Complexity. Springer.

Libkin, L. (2004). Elements of finite model theory. Springer.

Papadimitriou, C. H. (1994). Computational Complexity. Addison Wesley Logman.