Estratégias de computação seqüenciais e paralelas sobre espaços coerentes / Sequential and parallel computational strategies of coherence spaces

AUTOR(ES)

Schneider Sellanes, Ruben Gerardo

DATA DE PUBLICAÇÃO

2010

RESUMO

As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos.

ASSUNTO(S)

coherence spaces teoria : ciencia : computacao teoria : dominios concrete data structures algoritmos sequenciais concrete domains events structures paralelismo events domains linear functions stables functions sequential functions sequential algorithms linear algorithms sequentiality parallelism semantic

Documentos Relacionados

• SEQUENTIAL AND PARALLEL STRATEGIES OF GRASP WITH PATH-RELINKING FOR THE 2-PATH NETWORK DESIGN PROBLEM
• A Máquina geométrica : modelo computacional para concorrência e não-determinismo usando como estrutura espaços coerentes
• Tipo e cotipo de espaços de Banach e espaços Lp de Banach
• A categoria computável dos espaços coerentes gerados por conjuntos básicos com aplicação em análise real
• Estratégias de aplicações sequenciais e paralelas da metaheurística otimização por enxame de partículas ao problema do caixeiro viajante