京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20157号 / 理博第4242号 / 新制||理||1610(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)准教授 照井 一成, 教授 岡本 久, 教授 長谷川 真人 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM

Este trabalho consiste no desenvolvimento de uma metodologia para a obtenção de representações construtivas de sistemas ordenados de 2ª ordem, baseadas em estruturas de espaços coerentes, com aplicação fundamental na Computação Científica e Matemática Intervalar. Obtêm assim uma representação global para os objetos ditos infinitos relativamente ao conteúdo de informação, como números reais e intervalos reais, de tal forma que possam ser definidos modelos semânticos adequados para os processos computacionais envolvendo tais objetos. Esta representação construtiva é denominada de global, pois é realizada em dois níveis distinguíveis, compreendendo não somente a construção interna dos objetos, no contexto de uma da estrutura de informação, mas também sua estrutura externa de aplicação. A estrutura de informação tem caráter compatível com uma abordagem domínio-teorética, e a estrutura de aplicação e determinada pelo use pretendido do sistema representado. Existe um relacionamento entre os dois níveis de construção, garantindo que cada componente da estrutura de aplicação tenha uma representação interna na estrutura de informação. Os sistemas de representação global resultantes são denominados então espaços coerentes bi-estruturados, e tem a característica adicional de serem gerados por um sistema ordenado basico de universo enumerável. A estrutura de informação é um espaço coerente, com funções lineares e uma estrutura topológica de informação compatível. A estrutura de aplicação - algébrica, de ordem, relacional, funcional, de medidas, topológica, dentre outras - é obtida por um processo construtivo a partir da estrutura do sistema basico. Um espaço coerente bi-estruturado, obtido por esse processo de construção, é a representação global de um dado sistema ordenado de 2ª ordem quando possível recuperar este sistema através do subsistema dos objetos totais do espaço, pela determinação de isomorfismos para a estrutura de aplicação. Da mesma forma, estabelecendo também isomorfismos para o subsistema dos intervalos de elementos do conjunto universo do sistema que esta sendo representado, esse subsistema pode ser recuperado como o subsistema dos objetos quasi-totais do espaço coerente. Apresenta-se também uma abordagem categórica para o processo de construção global, mostrando se que ele determina uma adjunção entre duas subcategorias da categoria SO2 dos sistemas ordenados de 2ª ordem A metodologia proposta se mostrou particularmente interessante na construção do conjunto dos números reais e do conjunto de intervalos reais. Para estes sistemas introduziu-se também uma subestrutura elementar de medidas, pela definição, de forma generalizada, das funções valor absoluto, distância e diâmetro. Foi desenvolvida uma estrutura topológica para os espaços coerentes bi-estruturados, que caracteriza-se também por apresentar dois níveis que se inter-relacionam. Para obter uma caracterização topológica de informação desenvolveu-se a noção de espaços de vizinhanças lineares. No sentido de se obter a caracterização topológica de aplicação, obteve-se, em cada etapa da construção, um espaço de vizinhanças gerado pela função distância generalizada com uma topologia de aplicação associada. Conexões entre as representações de reais e de intervalos de reais e aspectos de computabilidade são referidas de modo preliminar, sugerindo-se este tema como trabalho futuro. Possíveis aplicações dos espaços coerentes bi-estruturados e do processo de construção global a outras áreas da Ciência da Computação são indicadas no final do trabalho. / The aim of this work is to develop a methodology to obtain constructive representations of second order ordered systems, based on coherence space structures, with the main application in Scientific Computation and Interval Mathematics. A global representation for the so-called infinite objects considering the information content they represent, in particularly real numbers and real intervals, is obtained, so that suitable semantical models for real and interval computational processes can be provided. This constructive representation is said to be global. since it is performed in two distinguished levels, dealing with the internal construction of the objects, in the context of an information structure, and, on the other hand, building an external application structure. The information structure is compatible with a domain-theoretic approach, and the application structure is established according the intended usage of the represented system. There exists a relationship between the two levels of the construction, guaranteeing that each component of the application structure should have an internal representation in the information structure. The resulting global representation systems are called bi-structured coherence spaces, and they have the additional feature of being generated by a basic ordered system having a denumerable universe. The information structure is a coherence space endowed with linear functions and a compatible information topological structure. The (algebraic, ordered, relational, functional, measure, topological, etc.) application structure is obtained by the construction process, considering the structure of the basic system as the start point. A bi-structured coherence space, obtained by this construction process, is said to be the global representation of a given second order ordered system if it is possible to recover the latter by the subsystem of the total objects of the former, defining isomorphisms related to the application structure. Following the same pattern, establishing isomorphisms for the subsystem of the intervals of elements of the represented system, it is possible to recover it as the subsystem of quasi-total objects of the bi-structured coherence space. A categorical approach is also presented and it is shown that the global construction process determines an adjunction between two subcategories of the category SO2 of the second order ordered systems. The proposed methodology was shown to be particularly interesting when constructing the sets of real numbers and real intervals. For these systems, an elementary measure structure was introduced in a generalised approach, defining generalised distance, diameter and absolute value functions. The bi-structured coherence spaces were given an interrelated two-level topological characterisation. In order to obtain an information topological characterisation the concept of linear neighbourhood systems was introduced. For the application topological characterisation, at each step of the construction, a neighbourhood system generated by the generalised distance function, with an associated topology, was defined. A brief analysis concerning the connections among other representations of real and real intervals and computability aspects is presented. Other possible applications in Computer Science are indicated.

Este trabalho consiste no desenvolvimento de uma metodologia para a obtenção de representações construtivas de sistemas ordenados de 2ª ordem, baseadas em estruturas de espaços coerentes, com aplicação fundamental na Computação Científica e Matemática Intervalar. Obtêm assim uma representação global para os objetos ditos infinitos relativamente ao conteúdo de informação, como números reais e intervalos reais, de tal forma que possam ser definidos modelos semânticos adequados para os processos computacionais envolvendo tais objetos. Esta representação construtiva é denominada de global, pois é realizada em dois níveis distinguíveis, compreendendo não somente a construção interna dos objetos, no contexto de uma da estrutura de informação, mas também sua estrutura externa de aplicação. A estrutura de informação tem caráter compatível com uma abordagem domínio-teorética, e a estrutura de aplicação e determinada pelo use pretendido do sistema representado. Existe um relacionamento entre os dois níveis de construção, garantindo que cada componente da estrutura de aplicação tenha uma representação interna na estrutura de informação. Os sistemas de representação global resultantes são denominados então espaços coerentes bi-estruturados, e tem a característica adicional de serem gerados por um sistema ordenado basico de universo enumerável. A estrutura de informação é um espaço coerente, com funções lineares e uma estrutura topológica de informação compatível. A estrutura de aplicação - algébrica, de ordem, relacional, funcional, de medidas, topológica, dentre outras - é obtida por um processo construtivo a partir da estrutura do sistema basico. Um espaço coerente bi-estruturado, obtido por esse processo de construção, é a representação global de um dado sistema ordenado de 2ª ordem quando possível recuperar este sistema através do subsistema dos objetos totais do espaço, pela determinação de isomorfismos para a estrutura de aplicação. Da mesma forma, estabelecendo também isomorfismos para o subsistema dos intervalos de elementos do conjunto universo do sistema que esta sendo representado, esse subsistema pode ser recuperado como o subsistema dos objetos quasi-totais do espaço coerente. Apresenta-se também uma abordagem categórica para o processo de construção global, mostrando se que ele determina uma adjunção entre duas subcategorias da categoria SO2 dos sistemas ordenados de 2ª ordem A metodologia proposta se mostrou particularmente interessante na construção do conjunto dos números reais e do conjunto de intervalos reais. Para estes sistemas introduziu-se também uma subestrutura elementar de medidas, pela definição, de forma generalizada, das funções valor absoluto, distância e diâmetro. Foi desenvolvida uma estrutura topológica para os espaços coerentes bi-estruturados, que caracteriza-se também por apresentar dois níveis que se inter-relacionam. Para obter uma caracterização topológica de informação desenvolveu-se a noção de espaços de vizinhanças lineares. No sentido de se obter a caracterização topológica de aplicação, obteve-se, em cada etapa da construção, um espaço de vizinhanças gerado pela função distância generalizada com uma topologia de aplicação associada. Conexões entre as representações de reais e de intervalos de reais e aspectos de computabilidade são referidas de modo preliminar, sugerindo-se este tema como trabalho futuro. Possíveis aplicações dos espaços coerentes bi-estruturados e do processo de construção global a outras áreas da Ciência da Computação são indicadas no final do trabalho. / The aim of this work is to develop a methodology to obtain constructive representations of second order ordered systems, based on coherence space structures, with the main application in Scientific Computation and Interval Mathematics. A global representation for the so-called infinite objects considering the information content they represent, in particularly real numbers and real intervals, is obtained, so that suitable semantical models for real and interval computational processes can be provided. This constructive representation is said to be global. since it is performed in two distinguished levels, dealing with the internal construction of the objects, in the context of an information structure, and, on the other hand, building an external application structure. The information structure is compatible with a domain-theoretic approach, and the application structure is established according the intended usage of the represented system. There exists a relationship between the two levels of the construction, guaranteeing that each component of the application structure should have an internal representation in the information structure. The resulting global representation systems are called bi-structured coherence spaces, and they have the additional feature of being generated by a basic ordered system having a denumerable universe. The information structure is a coherence space endowed with linear functions and a compatible information topological structure. The (algebraic, ordered, relational, functional, measure, topological, etc.) application structure is obtained by the construction process, considering the structure of the basic system as the start point. A bi-structured coherence space, obtained by this construction process, is said to be the global representation of a given second order ordered system if it is possible to recover the latter by the subsystem of the total objects of the former, defining isomorphisms related to the application structure. Following the same pattern, establishing isomorphisms for the subsystem of the intervals of elements of the represented system, it is possible to recover it as the subsystem of quasi-total objects of the bi-structured coherence space. A categorical approach is also presented and it is shown that the global construction process determines an adjunction between two subcategories of the category SO2 of the second order ordered systems. The proposed methodology was shown to be particularly interesting when constructing the sets of real numbers and real intervals. For these systems, an elementary measure structure was introduced in a generalised approach, defining generalised distance, diameter and absolute value functions. The bi-structured coherence spaces were given an interrelated two-level topological characterisation. In order to obtain an information topological characterisation the concept of linear neighbourhood systems was introduced. For the application topological characterisation, at each step of the construction, a neighbourhood system generated by the generalised distance function, with an associated topology, was defined. A brief analysis concerning the connections among other representations of real and real intervals and computability aspects is presented. Other possible applications in Computer Science are indicated.

Este trabalho consiste no desenvolvimento de uma metodologia para a obtenção de representações construtivas de sistemas ordenados de 2ª ordem, baseadas em estruturas de espaços coerentes, com aplicação fundamental na Computação Científica e Matemática Intervalar. Obtêm assim uma representação global para os objetos ditos infinitos relativamente ao conteúdo de informação, como números reais e intervalos reais, de tal forma que possam ser definidos modelos semânticos adequados para os processos computacionais envolvendo tais objetos. Esta representação construtiva é denominada de global, pois é realizada em dois níveis distinguíveis, compreendendo não somente a construção interna dos objetos, no contexto de uma da estrutura de informação, mas também sua estrutura externa de aplicação. A estrutura de informação tem caráter compatível com uma abordagem domínio-teorética, e a estrutura de aplicação e determinada pelo use pretendido do sistema representado. Existe um relacionamento entre os dois níveis de construção, garantindo que cada componente da estrutura de aplicação tenha uma representação interna na estrutura de informação. Os sistemas de representação global resultantes são denominados então espaços coerentes bi-estruturados, e tem a característica adicional de serem gerados por um sistema ordenado basico de universo enumerável. A estrutura de informação é um espaço coerente, com funções lineares e uma estrutura topológica de informação compatível. A estrutura de aplicação - algébrica, de ordem, relacional, funcional, de medidas, topológica, dentre outras - é obtida por um processo construtivo a partir da estrutura do sistema basico. Um espaço coerente bi-estruturado, obtido por esse processo de construção, é a representação global de um dado sistema ordenado de 2ª ordem quando possível recuperar este sistema através do subsistema dos objetos totais do espaço, pela determinação de isomorfismos para a estrutura de aplicação. Da mesma forma, estabelecendo também isomorfismos para o subsistema dos intervalos de elementos do conjunto universo do sistema que esta sendo representado, esse subsistema pode ser recuperado como o subsistema dos objetos quasi-totais do espaço coerente. Apresenta-se também uma abordagem categórica para o processo de construção global, mostrando se que ele determina uma adjunção entre duas subcategorias da categoria SO2 dos sistemas ordenados de 2ª ordem A metodologia proposta se mostrou particularmente interessante na construção do conjunto dos números reais e do conjunto de intervalos reais. Para estes sistemas introduziu-se também uma subestrutura elementar de medidas, pela definição, de forma generalizada, das funções valor absoluto, distância e diâmetro. Foi desenvolvida uma estrutura topológica para os espaços coerentes bi-estruturados, que caracteriza-se também por apresentar dois níveis que se inter-relacionam. Para obter uma caracterização topológica de informação desenvolveu-se a noção de espaços de vizinhanças lineares. No sentido de se obter a caracterização topológica de aplicação, obteve-se, em cada etapa da construção, um espaço de vizinhanças gerado pela função distância generalizada com uma topologia de aplicação associada. Conexões entre as representações de reais e de intervalos de reais e aspectos de computabilidade são referidas de modo preliminar, sugerindo-se este tema como trabalho futuro. Possíveis aplicações dos espaços coerentes bi-estruturados e do processo de construção global a outras áreas da Ciência da Computação são indicadas no final do trabalho. / The aim of this work is to develop a methodology to obtain constructive representations of second order ordered systems, based on coherence space structures, with the main application in Scientific Computation and Interval Mathematics. A global representation for the so-called infinite objects considering the information content they represent, in particularly real numbers and real intervals, is obtained, so that suitable semantical models for real and interval computational processes can be provided. This constructive representation is said to be global. since it is performed in two distinguished levels, dealing with the internal construction of the objects, in the context of an information structure, and, on the other hand, building an external application structure. The information structure is compatible with a domain-theoretic approach, and the application structure is established according the intended usage of the represented system. There exists a relationship between the two levels of the construction, guaranteeing that each component of the application structure should have an internal representation in the information structure. The resulting global representation systems are called bi-structured coherence spaces, and they have the additional feature of being generated by a basic ordered system having a denumerable universe. The information structure is a coherence space endowed with linear functions and a compatible information topological structure. The (algebraic, ordered, relational, functional, measure, topological, etc.) application structure is obtained by the construction process, considering the structure of the basic system as the start point. A bi-structured coherence space, obtained by this construction process, is said to be the global representation of a given second order ordered system if it is possible to recover the latter by the subsystem of the total objects of the former, defining isomorphisms related to the application structure. Following the same pattern, establishing isomorphisms for the subsystem of the intervals of elements of the represented system, it is possible to recover it as the subsystem of quasi-total objects of the bi-structured coherence space. A categorical approach is also presented and it is shown that the global construction process determines an adjunction between two subcategories of the category SO2 of the second order ordered systems. The proposed methodology was shown to be particularly interesting when constructing the sets of real numbers and real intervals. For these systems, an elementary measure structure was introduced in a generalised approach, defining generalised distance, diameter and absolute value functions. The bi-structured coherence spaces were given an interrelated two-level topological characterisation. In order to obtain an information topological characterisation the concept of linear neighbourhood systems was introduced. For the application topological characterisation, at each step of the construction, a neighbourhood system generated by the generalised distance function, with an associated topology, was defined. A brief analysis concerning the connections among other representations of real and real intervals and computability aspects is presented. Other possible applications in Computer Science are indicated.

Neste trabalho desenvolve-se um estudo sobre os Espaços Coerentes Gerados por Conjuntos Básicos, dotados de uma estrutura adicional. Por estrutura adicional entende-se uma estrutura algébrica, de ordem pontual, de medidas, topológica e lógica. Estes espaços, denotados por , constituem uma subcategoria dos Espaços Coerentes, cujos objetos, ordenados pela inclusão, são conjuntos coerentes constituídos por subconjuntos do conjunto básico, os quais estão relacionados pela relação de coerência induzida, que estrutura a teia deste espaço. Os morfismos desta categoria são as funções de objetos geradas por funções básicas. As propriedades algébricas e relacionais destas funções básicas, externas ao processo de construção, ao se propagarem, passam a influenciar na verificação das propriedades internas das funções de objetos. Contudo, este trabalho não é um estudo categórico. A metodologia adotada utiliza a linguagem simples e intuitiva da Teoria dos Conjuntos, que possibilita a visualização e a análise dos relacionamentos existentes, não apenas entre os morfismos que envolvem os objetos totais ou parciais desta categoria, mas também das estruturas ou pré-estruturas externas que os formam, representados pelas funções de tokens e funções básicas. Mostra-se que as funções de objetos são totais e bem definidas, alem de serem monótonas e continuas neste espaço. Entretanto a análise da estabilidade, e consequentemente da linearidade esta associada a injetividade das funções básicas. Uma das características mais importantes da construção proposta e o desenvolvimento de um sistema de representação linear para funções localmente lineares, com a definição do espaço coerente A* gerado pelo produto de subteias. Neste espaço, as funções de objetos são lineares e coincidem com os morfismo da categoria dos espaços coerentes. Além disso, mostra-se que A* e isomorfo ao espaço coerente gerado pelo produto direto dos sub-espaços, ПĄ. Desta forma, toda transformação definida para um tipo de dado estruturado a partir de um conjunto básico enumerável tem uma representação linear, constituída pelos morfismos da categoria dos espaços coerentes. A existência da representação linear para as funções elementares garante a existência da representação linear para outras funções derivadas destas. Apresenta-se ainda uma especificação desta construção, introduzindo-se o Espaço Coerente de Intervalos Racionais, IIQ. Na busca de uma aplicação compatível com uma abordagem computacional, em especial para Análise Real, mostra-se que, em IIQ, cada função real elementar esta identificada com uma função de objetos linear, definida a partir da correspondente função elementar racional. Dentre as funções que foram analisadas destacam-se: a exponencial, a logarítmica, a potência, a potência estendida, a raiz n-ésima, as funções trigonométricas como seno, cosseno e tangente e suas correspondentes funções inversas, como também a função polinomial. Verificou-se que todas estas funções de objetos são totais, bem definidas, ou pertencem ou possuem uma representação linear na categoria COSP-LIN dos espaços coerentes, alem de serem fechadas para os objetos totais e quasi-totais deste espaço, sendo possível estabelecer o correspondente par-projeção para cada uma delas. / In this work the Coherence Spaces Generated by Basic Sets with additional structure are studied. By additional structure one means an algebraic, topological and logical structure with a punctual order and a measure system. These spaces, indicated by A, are a subcategory of the category of Coherence Spaces, whose objects, ordered by inclusion, are coherent sets formed by the induced web coherence relation. The morphisms of this category are the functions of objects generated by basic functions. The algebraic and relational properties of these basic functions - external to the construction process - are propagated and cause important influences in the verification of the internal properties of the functions of objects However, this research is not a categorical study. The methodology uses the simple and intuitive language of the Set Theory, which allows the visualization and the analysis of the existing relationships, not only among, the morphisms of the total and partial objects of this category, but also among their structures or pre-structures, represented by the functions of tokens and basic functions. It is shown that the functions of objects are total and well defined. They are also monotone and continuous. However the stability and the linearity of the functions of objects depend on the fact if the basic functions are injective or not. One of the most important features of this construction is the development of a linear representation system for the local linear functions, by the definition of a coherence space A*, which is generated by the subweb product. In this space the functions of objects are linear and therefore they are the morphisms of the category of Coherence Spaces. Moreover, it is proved that A* is isomorphic to the coherence space generated by the directed product of the subspaces, denoted by ПĄ . Then, for each transformation defined for a structured data type considering a denumerable basic set there exists its related linear representation. The existence of a linear representation for elementary functions guarantees the existence of a linear representation for others derived functions. As an application of this construction, the Coherence Space of Rational Intervals, denoted by IIQ, is introduced. In order to show an application which is compatible to a computational approach, specially for the real analysis, each elementary real function is identified with a linear function of objects, defined considering the related elementary rational function. Some of the analyzed functions are the exponential, the logarithmic, the power , the extended power, the root, the trigonometric (sine, cosine and tangent and their relates inverses), and the polynomial functions. It is proved that all of these functions of objects are total and well defined. Moreover, either they belong to the category COPS-LIN of the coherence spaces or they have a linear representation in the same category. It is also possible to define a related projection pair for each one of them.

Neste trabalho desenvolve-se um estudo sobre os Espaços Coerentes Gerados por Conjuntos Básicos, dotados de uma estrutura adicional. Por estrutura adicional entende-se uma estrutura algébrica, de ordem pontual, de medidas, topológica e lógica. Estes espaços, denotados por , constituem uma subcategoria dos Espaços Coerentes, cujos objetos, ordenados pela inclusão, são conjuntos coerentes constituídos por subconjuntos do conjunto básico, os quais estão relacionados pela relação de coerência induzida, que estrutura a teia deste espaço. Os morfismos desta categoria são as funções de objetos geradas por funções básicas. As propriedades algébricas e relacionais destas funções básicas, externas ao processo de construção, ao se propagarem, passam a influenciar na verificação das propriedades internas das funções de objetos. Contudo, este trabalho não é um estudo categórico. A metodologia adotada utiliza a linguagem simples e intuitiva da Teoria dos Conjuntos, que possibilita a visualização e a análise dos relacionamentos existentes, não apenas entre os morfismos que envolvem os objetos totais ou parciais desta categoria, mas também das estruturas ou pré-estruturas externas que os formam, representados pelas funções de tokens e funções básicas. Mostra-se que as funções de objetos são totais e bem definidas, alem de serem monótonas e continuas neste espaço. Entretanto a análise da estabilidade, e consequentemente da linearidade esta associada a injetividade das funções básicas. Uma das características mais importantes da construção proposta e o desenvolvimento de um sistema de representação linear para funções localmente lineares, com a definição do espaço coerente A* gerado pelo produto de subteias. Neste espaço, as funções de objetos são lineares e coincidem com os morfismo da categoria dos espaços coerentes. Além disso, mostra-se que A* e isomorfo ao espaço coerente gerado pelo produto direto dos sub-espaços, ПĄ. Desta forma, toda transformação definida para um tipo de dado estruturado a partir de um conjunto básico enumerável tem uma representação linear, constituída pelos morfismos da categoria dos espaços coerentes. A existência da representação linear para as funções elementares garante a existência da representação linear para outras funções derivadas destas. Apresenta-se ainda uma especificação desta construção, introduzindo-se o Espaço Coerente de Intervalos Racionais, IIQ. Na busca de uma aplicação compatível com uma abordagem computacional, em especial para Análise Real, mostra-se que, em IIQ, cada função real elementar esta identificada com uma função de objetos linear, definida a partir da correspondente função elementar racional. Dentre as funções que foram analisadas destacam-se: a exponencial, a logarítmica, a potência, a potência estendida, a raiz n-ésima, as funções trigonométricas como seno, cosseno e tangente e suas correspondentes funções inversas, como também a função polinomial. Verificou-se que todas estas funções de objetos são totais, bem definidas, ou pertencem ou possuem uma representação linear na categoria COSP-LIN dos espaços coerentes, alem de serem fechadas para os objetos totais e quasi-totais deste espaço, sendo possível estabelecer o correspondente par-projeção para cada uma delas. / In this work the Coherence Spaces Generated by Basic Sets with additional structure are studied. By additional structure one means an algebraic, topological and logical structure with a punctual order and a measure system. These spaces, indicated by A, are a subcategory of the category of Coherence Spaces, whose objects, ordered by inclusion, are coherent sets formed by the induced web coherence relation. The morphisms of this category are the functions of objects generated by basic functions. The algebraic and relational properties of these basic functions - external to the construction process - are propagated and cause important influences in the verification of the internal properties of the functions of objects However, this research is not a categorical study. The methodology uses the simple and intuitive language of the Set Theory, which allows the visualization and the analysis of the existing relationships, not only among, the morphisms of the total and partial objects of this category, but also among their structures or pre-structures, represented by the functions of tokens and basic functions. It is shown that the functions of objects are total and well defined. They are also monotone and continuous. However the stability and the linearity of the functions of objects depend on the fact if the basic functions are injective or not. One of the most important features of this construction is the development of a linear representation system for the local linear functions, by the definition of a coherence space A*, which is generated by the subweb product. In this space the functions of objects are linear and therefore they are the morphisms of the category of Coherence Spaces. Moreover, it is proved that A* is isomorphic to the coherence space generated by the directed product of the subspaces, denoted by ПĄ . Then, for each transformation defined for a structured data type considering a denumerable basic set there exists its related linear representation. The existence of a linear representation for elementary functions guarantees the existence of a linear representation for others derived functions. As an application of this construction, the Coherence Space of Rational Intervals, denoted by IIQ, is introduced. In order to show an application which is compatible to a computational approach, specially for the real analysis, each elementary real function is identified with a linear function of objects, defined considering the related elementary rational function. Some of the analyzed functions are the exponential, the logarithmic, the power , the extended power, the root, the trigonometric (sine, cosine and tangent and their relates inverses), and the polynomial functions. It is proved that all of these functions of objects are total and well defined. Moreover, either they belong to the category COPS-LIN of the coherence spaces or they have a linear representation in the same category. It is also possible to define a related projection pair for each one of them.

Neste trabalho desenvolve-se um estudo sobre os Espaços Coerentes Gerados por Conjuntos Básicos, dotados de uma estrutura adicional. Por estrutura adicional entende-se uma estrutura algébrica, de ordem pontual, de medidas, topológica e lógica. Estes espaços, denotados por , constituem uma subcategoria dos Espaços Coerentes, cujos objetos, ordenados pela inclusão, são conjuntos coerentes constituídos por subconjuntos do conjunto básico, os quais estão relacionados pela relação de coerência induzida, que estrutura a teia deste espaço. Os morfismos desta categoria são as funções de objetos geradas por funções básicas. As propriedades algébricas e relacionais destas funções básicas, externas ao processo de construção, ao se propagarem, passam a influenciar na verificação das propriedades internas das funções de objetos. Contudo, este trabalho não é um estudo categórico. A metodologia adotada utiliza a linguagem simples e intuitiva da Teoria dos Conjuntos, que possibilita a visualização e a análise dos relacionamentos existentes, não apenas entre os morfismos que envolvem os objetos totais ou parciais desta categoria, mas também das estruturas ou pré-estruturas externas que os formam, representados pelas funções de tokens e funções básicas. Mostra-se que as funções de objetos são totais e bem definidas, alem de serem monótonas e continuas neste espaço. Entretanto a análise da estabilidade, e consequentemente da linearidade esta associada a injetividade das funções básicas. Uma das características mais importantes da construção proposta e o desenvolvimento de um sistema de representação linear para funções localmente lineares, com a definição do espaço coerente A* gerado pelo produto de subteias. Neste espaço, as funções de objetos são lineares e coincidem com os morfismo da categoria dos espaços coerentes. Além disso, mostra-se que A* e isomorfo ao espaço coerente gerado pelo produto direto dos sub-espaços, ПĄ. Desta forma, toda transformação definida para um tipo de dado estruturado a partir de um conjunto básico enumerável tem uma representação linear, constituída pelos morfismos da categoria dos espaços coerentes. A existência da representação linear para as funções elementares garante a existência da representação linear para outras funções derivadas destas. Apresenta-se ainda uma especificação desta construção, introduzindo-se o Espaço Coerente de Intervalos Racionais, IIQ. Na busca de uma aplicação compatível com uma abordagem computacional, em especial para Análise Real, mostra-se que, em IIQ, cada função real elementar esta identificada com uma função de objetos linear, definida a partir da correspondente função elementar racional. Dentre as funções que foram analisadas destacam-se: a exponencial, a logarítmica, a potência, a potência estendida, a raiz n-ésima, as funções trigonométricas como seno, cosseno e tangente e suas correspondentes funções inversas, como também a função polinomial. Verificou-se que todas estas funções de objetos são totais, bem definidas, ou pertencem ou possuem uma representação linear na categoria COSP-LIN dos espaços coerentes, alem de serem fechadas para os objetos totais e quasi-totais deste espaço, sendo possível estabelecer o correspondente par-projeção para cada uma delas. / In this work the Coherence Spaces Generated by Basic Sets with additional structure are studied. By additional structure one means an algebraic, topological and logical structure with a punctual order and a measure system. These spaces, indicated by A, are a subcategory of the category of Coherence Spaces, whose objects, ordered by inclusion, are coherent sets formed by the induced web coherence relation. The morphisms of this category are the functions of objects generated by basic functions. The algebraic and relational properties of these basic functions - external to the construction process - are propagated and cause important influences in the verification of the internal properties of the functions of objects However, this research is not a categorical study. The methodology uses the simple and intuitive language of the Set Theory, which allows the visualization and the analysis of the existing relationships, not only among, the morphisms of the total and partial objects of this category, but also among their structures or pre-structures, represented by the functions of tokens and basic functions. It is shown that the functions of objects are total and well defined. They are also monotone and continuous. However the stability and the linearity of the functions of objects depend on the fact if the basic functions are injective or not. One of the most important features of this construction is the development of a linear representation system for the local linear functions, by the definition of a coherence space A*, which is generated by the subweb product. In this space the functions of objects are linear and therefore they are the morphisms of the category of Coherence Spaces. Moreover, it is proved that A* is isomorphic to the coherence space generated by the directed product of the subspaces, denoted by ПĄ . Then, for each transformation defined for a structured data type considering a denumerable basic set there exists its related linear representation. The existence of a linear representation for elementary functions guarantees the existence of a linear representation for others derived functions. As an application of this construction, the Coherence Space of Rational Intervals, denoted by IIQ, is introduced. In order to show an application which is compatible to a computational approach, specially for the real analysis, each elementary real function is identified with a linear function of objects, defined considering the related elementary rational function. Some of the analyzed functions are the exponential, the logarithmic, the power , the extended power, the root, the trigonometric (sine, cosine and tangent and their relates inverses), and the polynomial functions. It is proved that all of these functions of objects are total and well defined. Moreover, either they belong to the category COPS-LIN of the coherence spaces or they have a linear representation in the same category. It is also possible to define a related projection pair for each one of them.

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. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

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. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.

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. / The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.