INTRODUÇÃO À TEORIA DOS DOMÍNIOS

Obrigatória: Não

Carga Horária: 60

Créditos: 4

OBJETIVOS:
Estudar os conceitos básicos da Teoria dos Domínios e suas aplicações.

EMENTA:
Ordens Parciais Completas (CPO's), CPO's algébricos, w-algébricos, consistentemente completos, construções em CPO's. Domínios de Scott, construções em domínios, espaço de funções. Estudo do teorema do ponto fixo. Noções de categorias de domínios. Domínios Qualitativos, Espaços Coerentes e construções em Espaços Coerentes. Aplicações de domínios.

PROGRAMA:
1. Revisão sobre os conceitos básicos de estruturas ordenadas.
1.1 Relação de Ordem como relação de aproximação
1.2 Elementos minimais (maximais), menor (maior) elemento
1.3 Cotas inferiores (superiores), ínfimo (supremo)
1.4 Conjuntos limitados e consistentes
2. Ordens Parciais Completas (CPO)
2.1 Conjunto dirigido
2.2 CPO e exemplos clássicos
2.3 Funções monótonas, funções que preservam a ordem, Funções contínuas, isomorfismos para a ordem
2.4 Sub-CPO
2.5 Construções em CPO?s: produtos, espaço de funções, somas, lifting
3. Domínios
3.1 Elemento compacto ou finito
3.2 CPO algébrico
3.3 CPO consistentemente completo
3.4 Domínios de Scott
3.5 Domínios Contínuos
3.6 Teoria do Ponto Fixo
3.7 Domínios SPF
3.8 Domínios Potência
4. Domínios Qualitativos
4.1 Origem e definição geral dos domínios qualitativos de Girard
4.2 Tokens, relação de coerência e teia
4.3 Conjunto coerente
4.4 Espaços Coerentes
4.5 Propriedades
4.6 Funções monótonas, contínuas, estáveis e lineares
4.7 Produto direto de espaços coerentes, espaço de funções, ordem de Berry
4.8 Construções em espaços coerentes: negação, tensor, implicação linear, conjunção, disjunção, exponenciais (OfCourse, WhyNot)
5. Estudo de Aplicações
5.1 Semântica de linguagens de programação
5.2 Computação com números reais e intervalos de reais
5.3 Modelagem de processos de medida
5.4 Modelagem de fusão de informações
5.5 Lógica Linear
5.6 Modelos computacionais baseados em Espaços Coerentes

Bibliografia:
- ALLISON, L. A Practical Introduction to Denotational Semantics. Cambridge. (Cambridge Computer Science Texts)
DAVEY, B. A.; PRIESTLEY, H. A. Introduction to Lattices and Order. Cambridge: Cambridge University Press, 1991. 248p.

- GIRARD, J.-Y. The System F of Variable Types, Fifteen Years Later. Theorical Computer Science, Amsterdam, n.45, p.159-192, 1986.

- GIRARD, J.-Y. Linear Logic. Theorical Computer Science, Amsterdam, n.50, p.1-102, 1987.

- GIRARD, J.-Y.; LAFONT, Y.; TAYLOR, P. Proofs and Types. Cambridge: Cambridge University Press, 1989. 176p.

- GIRARD, J.-Y.; LAFONT, Y.; and Regnier, L. (Eds.) Advances in Linear Logic. Cambridge: Cambridge University Press, 1995 (Londo Mathematical Society Lecture Note Series, 222)

- SCHMIDT, D. A. A Methodology for language Development. Manhattan: Kansas State University, 1986. (disponível em http://www.cis.ksu.edu/~schmidt/text/densem.html)

- STOLTENBERG-HANSEN, V.; LINDSTRÖM, I.; GRIFFOR, E. R. Mathematical Theory of Domains. Cambridge: Cambridge University Press, 1994. 349p.

- STOY, J.E. Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory. Cambridge: MIT Press.

- TROELSTRA, A. S. Lectures on Linear Logic. Stanford: CSLI/Leland Stanford Junior University, 1992. (Lecture Notes, n.29).

- WINSKEL, G. The Formal Semantics of Programming Languages, An Introduction. Cambridge: MIT Press, 1993. (Foundations of Computing Series)

- ZHANG, G. Logic of Domains. Boston: Birkhäuser, 1991. (Progress in Theoretical Computer Science).