Orientador: Germán Jesus Lozada Cruz / Banca: Marcos Roberto Teixeira Primo / Banca: Andréa Cristina Prokopezyk Arita / Resumo: Neste trabalho vamos estudar a existência e unicidade de solução para equações da forma { u + Au = f(t,u) u(t0)= u0 ∈ X, (I) onde X é um espaço de Banach, A : D(A) ⊂ X → X é um operador linear, f é uma função não linear conhecida, u0 ∈ X é um dado inical conhecido e u : I ⊂ R → X é uma função desconhecida e t0 ∈ I. Faremos este estudo usando a Teoria dos Semigrupos de Operadores Lineares. Para melhor entendimento do estudo das equações (I), faremos duas aplicações. A primeira tratando de um modelo (linear) de divisão celular e a segunda, do modelo (não linear) de condução do calor. / Abstract: In this work we will study the existence and uniqueness of the solutions for the following equation { u + Au = f(t,u) u(t0)= u0 ∈ X, (I) where X is a Banach space, A : D(A) ⊂ X → X is a linear operator, f is a nonlinear function, u : I ⊂ R → X is unknown function. In this study we will use the theory of semigroup of linear operators. For a best understanding of the study of equations (I), we will do two applications. The first one, is a (linear) model of cellular division and the second one, is about the (nonlinear) model od conduction of the heat. / Mestre

The overall goal of the field of natural language processing is to facilitate the communication between humans and computers, and to help humans with natural language problems such as translation. In this thesis, we focus on semantic language processing. Modelling semantics – the meaning of natural language – requires both a structure to hold the semantic information and a device that can enforce rules on the structure to ensure well-formed semantics while not being too computationally heavy. The devices used in natural language processing are preferably weighted to allow for comparison of the alternative semantic interpretations outputted by a device. The structure employed here is the abstract meaning representation (AMR). We show that AMRs representing well-formed semantics can be generated while leaving out AMRs that are not semantically well-formed. For this purpose, we use a type of graph grammar called contextual hyperedge replacement grammar (CHRG). Moreover, we argue that a more well-known subclass of CHRG – the hyperedge replacement grammar (HRG) – is not powerful enough for AMR generation. This is due to the limitation of HRG when it comes to handling co-references, which in its turn depends on the fact that HRGs only generate graphs of bounded treewidth. Furthermore, we also address the N best problem, which is as follows: Given a weighted device, return the N best (here: smallest-weighted, or more intuitively, smallest-errored) structures. Our goal is to solve the N best problem for devices capable of expressing sophisticated forms of semantic representations such as CHRGs. Here, however, we merely take a first step consisting in developing methods for solving the N best problem for weighted tree automata and some types of weighted acyclic hypergraphs.

The thesis consists of four research papers. The first three deal with the Choquet theory of function spaces. In Chapter 1, a theory on products and projective limits of function spaces is developed. It is shown that the product of simplicial spaces is a simplicial space. The stability of the space of maximal measures under continuous affine mappings is studied in Chapter 2. The third chapter employs results from the previous chapters to construct an example of a function space where the abstract Dirichlet problem is not solvable for any class of Baire-n functions with $n\in N$. It is shown that such an example cannot be constructed via the space of harmonic functions. In the final chapter, the recently introduced class of sequentially Right Banach spaces is being investigated. Connections to other isomorphic properties of Banach spaces are established and several characterizations are given.

A noção de tipo é intrínseca ao raciocínio humano, na medida que os seres humanos tendem a "classificar" os objetos segundo seu use e seu comportamento como parte do processo de resolução de problemas. Tal classificação dos objetos implica numa abstração das características irrelevantes dos mesmos,permitindo dessa maneira uma simplificação importante da complexidade do universo de discurso Por outro lado, certos problemas são altamente complexos e requerem um tratamento diferenciado.Esses problemas exigem, para sua resolução, um grande conhecimento do universo de discurso. O ponto critico nesta situação é que o domínio do problema não é exato como poderia ser um domínio matemático. Pelo contrario, ele inclui geralmente aspectos ambíguos e pouco formais que dificultam seu entendimento. Tal domínio a chamado de senso comum e é objeto de estudo de uma linha da computação, a Inteligência Artificial (IA). Para [KRA 87], entre outros, as soluc6es pare muitos problemas de IA dependern mais da capacidade de adquirir e manipular conhecimento do que de algoritmos sofisticados. Por este motivo, existem na IA muitos tipos de linguagens que tentam, de di verses maneiras,facilitar a representação de conhecirnentos sobre universos de discurso de problemas particulares. São as chamadas Linguagens de Representação de Conhecimento. A noção de tipo e implícita nas linguagens de representação de conhecimento, uma vez que tal noção é natural no raciocínio humano e esta intimamente ligada ao conceito de abstração. Este trabalho visa explicitar a noção de tipo subjacente ao núcleo definido da linguagem RECON-II. Para isto, foi realizado um estudo semântico prévio para identificar os tipos semânticos da linguagem. A partir da noção semântica dos tipos foi possível definir a correspondente sintática e finalmente, descrever um Sistema de Tipos para RECON-II. Um Sistema de Tipos consiste numa Linguagem de Tipos (tipos básicos + construtores de tipos) e num Sistema de Dedução que relaciona as expresses da linguagem objeto (linguagem de programação com as expresses da linguagem de tipos. Para a primeira etapa realizada neste trabalho, a determinação da semântica da linguagem, foi utilizado o método algébrico. Nele toda expressão RECON-II é um termo de uma assinatura Z, de modo quo cada assinatura Z determina um conjunto de expressos RECON-UL Mas, por outro lado, uma assinatura também determina um conjunto de álgebras. Dessas álgebras-Z só um subconjunto significativo para as expressões RECON-II. As álgebras-Z significativas são aquelas que satisfazem a assinatura-Z mais um conjunto E de axiomas. A assinatura-Z junto como o conjunto E de axiomas constituem o quo se denomina Tipo Abstrato de Dados, T=CZ, E), e as álgebras-Z significativas são os chamados modelos-Z do tipo T. Assim, uma expressão RECON-II a e um elemento da álgebra de termos quo g uma Álgebra gerada a partir do E. Essa álgebra, 44 4-) conjunto das expressi5es_: RECON-II significativas, e o modelo inicial de tais expressões WOG 781 Dado um tipo abstrato T existe um único modelo para T, ou uma classe de modelos, não isomórficos, denominada MCT>. No segundo caso, asses modelos constituem uma "quasi" ordem parcial com modelo inicial e terminal. A existência e unicidade do modelo inicial para qualquer tipo T foi demonstrada por [GOG 77] Com Σ = (S, F). a (Ws )para 9 S, e o conjunto dos termos de "sort." e. Na RECON-II, são os termos de uma categoria sintática determinada. As categorias sintáticas principais são : Conceitos, Relações, Funções e Redes. Um tipo semântico para s E S é um subconjunto M(T) S M(T) quo satisfaz os axiomas E exigidos de (WΣ) s, constituindo o tipo abstrato T .s.(por exemplo TConceitos, TRedes, etc.) Por último foi definido o Sistema de Tipos, que consiste numa estrutura sintática adequada para os tipos semânticos de cada expressão-RECON e, para cada expressão de tipo, um conjunto de regras de inferências que permuta, a partir de uma expressão-RECON inferir seu tipo mais geral. / The notion of type is intrinsic to human reasoning, since human beings tend to classify objects according their use and behaviour as part of the problem solving process. By classifying objects, their irrevelant characteristics are abstrated; in this way, the complexity of the universe of discourse is much reduced. On the other hand, certain problems are higly complex and require a differentiated treatament. In order to solve these problems, a great knowledge of de universe of discourse is needed. The critical proint in this situation is that the domain of the problem isn't as precise as a matliematic domain. On the contrary, it generally, includes ambiguous and not very formal aspects wich make its uderstanding difficult.. Such a domains is known as common sense and this is the object of studies of one line of Computer Science, Artificial Intelligence CAI). For [KRA 871, among others, the solutions for many AI problems depend on the ability for acquiring and manipulating knowledge rather than on sophisticated algorithm. For this reason, there are in AI many type of languages that attemps in different ways, to represent the UD of a particular problem. These languagesare known as Knowledge Representation Languages. The notion of type is implicit in Knowledge Representation Languages, since it is natural in human reasoning and closely rrelated to the concept of abstraction. This work intends to make the notion of type intrinsic to the RECON-II's kernel language, explicity. In order to do this, a preliminary semantic stidy was carriedaut to identify the semantic types of the languages. From the semantic notion of the types it was possible to define the sintactic counterpart and finally to describe a Type System for RECON- II. A Type System conssit of a type language (basic types + types constructors) end a deduction system that relattes expressions in the language object (programming language) to the expressions in the type language. In the first step of this work, language semantic determination, the algebric method was used. In it every RECON-II expression is one term of a signature 2, so Chet every signature 2 determines a RECON-II expressions set. On the other hand, a signature also determines a set of algebras. Out of these 2-algebras only one subset is significant to the RECON-II expressions. The significant 2-algebras are those t.het satisfy the 2-signature and a' set E of axioms. Together the 2-siganture and the set E of axioms, constitute what is called Abstract Data Type T = (2, E) and the significant E-algebras are the so-called Z-models of type T. Therefore a RECON-II expressions a is an element, of the wich is an algebra generated from E. This 2- 211)1`.9 is the set. of Sl !.171-11. RECON-II expressions, and is the initia; model of such expressions CLOG 78]. Given an abstract type T there is one single model for T or one class of nonisomorphic models denominated M(T). In the second cas,4, these models constitute a "quasi" partial order with an initial and terminal model. the exixstence nad uniqueness of the inititia1 model for any type T was shown at. CLOG 773. With r = <SS, F ) , (W ) for s S. is the set of terms of e sort. In RECON-II, those are •he term of determinate sintactic category. The main -sintactic categories are Concepts, Relations, Functions and Nets. A semantic type for s E S is s subset MCI') S MCT> that satisfies the axioms E required from C.W_), constituting the 8 2- abstract type T (for instance Tconcepts, Tnets, etc.). 8 Finally, the type systems was defined, consisting a syntatic structure suitable for the semantic types of each RECON-II expressions and for every type expressions, a set of inference rules wich allows infering its more general type from a RECON-II expressions.

This thesis studies the extensions of the four-valued Belnap-Dunn logic, called super-Belnap logics, from the point of view of abstract algebraic logic. We describe the global structure of the lattice of super-Belnap logics and show that this lattice can be fully described in terms of classes of finite graphs satisfying some closure conditions. We also introduce a theory of so- called explosive extensions and use it to prove new completeness theorems for super-Belnap logics. A Gentzen-style proof theory for these logics is then developed and used to establish interpolation for many of them. Finally, we also study the expansion of the Belnap-Dunn logic by the truth operator ∆. Keywords: abstract algebraic logic, Belnap-Dunn logic, paraconsistent logic, super-Belnap logics

La recherche d'une borne supérieure au temps d'exécution d'un programme est une partie essentielle du processus de vérification de systèmes temps-réel critiques. Les programmes de tels systèmes ont généralement des temps d'exécution variables et il est difficile, voire impossible, de prédire l'ensemble de ces temps possibles. Au lieu de cela, il est préférable de rechercher une approximation du temps d'exécution pire-cas ou Worst-Case Execution Time (WCET). Une propriété cruciale de cette approximation est qu'elle doit être sûre, c'est-à-dire qu'elle doit être garantie de majorer le WCET. Parce que nous cherchons à prouver que le système en question se termine en un temps raisonnable, une surapproximation est le seul type d'approximation acceptable. La garantie de cette propriété de sûreté ne saurait raisonnablement se faire sans analyse statique, un résultat se basant sur une série de tests ne pouvant être sûr sans un traitement exhaustif des cas d'exécution. De plus, en l'absence de certification du processus de compilation (et de transfert des propriétés vers le binaire), l'extraction de propriétés doit se faire directement sur le code binaire pour garantir leur fiabilité. Toutefois, cette approximation a un coût : un pessimisme - écart entre le WCET estimé et le WCET réel - important entraîne des surcoûts superflus de matériel pour que le système respecte les contraintes temporelles qui lui sont imposées. Il s'agit donc ensuite, tout en maintenant la garantie de sécurité de l'estimation du WCET, d'améliorer sa précision en réduisant cet écart de telle sorte qu'il soit suffisamment faible pour ne pas entraîner des coûts supplémentaires démesurés. Un des principaux facteurs de surestimation est la prise en compte de chemins d'exécution sémantiquement impossibles, dits infaisables, dans le calcul du WCET. Ceci est dû à l'analyse par énumération implicite des chemins ou Implicit Path Enumeration Technique (IPET) qui raisonne sur un surensemble des chemins d'exécution. Lorsque le chemin d'exécution pire-cas ou Worst-Case Execution Path (WCEP), correspondant au WCET estimé, porte sur un chemin infaisable, la précision de cette estimation est négativement affectée. Afin de parer à cette perte de précision, cette thèse propose une technique de détection de chemins infaisables, permettant l'amélioration de la précision des analyses statiques (dont celles pour le WCET) en les informant de l'infaisabilité de certains chemins du programme. Cette information est passée sous la forme de propriétés de flot de données formatées dans un langage d'annotation portable, FFX, permettant la communication des résultats de notre analyse de chemins infaisables vers d'autres analyses. Les méthodes présentées dans cette thèse sont inclues dans le framework OTAWA, développé au sein de l'équipe TRACES à l'IRIT. Elles usent elles-mêmes d'approximations pour représenter les états possibles de la machine en différents points du programme. / The search for an upper bound of the execution time of a program is an essential part of the verification of real-time critical systems. The execution times of the programs of such systems generally vary a lot, and it is difficult, or impossible, to predict the range of the possible times. Instead, it is better to look for an approximation of the Worst-Case Execution Time (WCET). A crucial requirement of this estimate is that it must be safe, that is, it must be guaranteed above the real WCET. Because we are looking to prove that the system in question terminates reasonably quickly, an overapproximation is the only acceptable form of approximation. The guarantee of such a safety property could not sensibly be done without static analysis, as a result based on a battery of tests could not be safe without an exhaustive handling of test cases. Furthermore, in the absence of a certified compiler (and tech- nique for the safe transfer of properties to the binaries), the extraction of properties must be done directly on binary code to warrant their soundness. However, this approximation comes with a cost : an important pessimism, the gap between the estimated WCET and the real WCET, would lead to superfluous extra costs in hardware in order for the system to respect the imposed timing requirements. It is therefore important to improve the precision of the WCET by reducing this gap, while maintaining the safety property, as such that it is low enough to not lead to immoderate costs. A major cause of overestimation is the inclusion of semantically impossible paths, said infeasible paths, in the WCET computation. This is due to the use of the Implicit Path Enumeration Technique (IPET), which works on an superset of the possible execution paths. When the Worst-Case Execution Path (WCEP), corresponding to the estimated WCET, is infeasible, the precision of that estimation is negatively affected. In order to deal with this loss of precision, this thesis proposes an infeasible paths detection technique, enabling the improvement of the precision of static analyses (namely for WCET estimation) by notifying them of the infeasibility of some paths of the program. This information is then passed as data flow properties, formatted in the FFX portable annotation language, and allowing the communication of the results of our infeasible path analysis to other analyses.

Ce travail porte sur la vérification de composants logiciels dans les systèmes embarqués critiques avioniques. Les conséquences d’une erreur dans de tels systèmes pouvant s'avérer catastrophiques, il se doivent de respecter leur spécification. La vérification formelle tend à prouver cette adéquation si elle est vraie, ou à produire un contre-exemple si elle ne l’est pas. Les méthodes actuelles ne sont pas capable de traiter les les systèmes industriels. La découverte d’informations supplémentaires (invariants) sur le système permet de réduire l’espace de recherche afin de renforcer l’objectif de preuve: les informations découvertes sont suffisantes pour conclure “facilement”. Nous définissons une architecture parallèle permettant à des méthodes de découverte d’invariants de collaborer autour d’un moteur de kinduction. Dans ce contexte nous proposons HullQe, une nouvelle heuristique de génération d’invariants potentiels combinant un calcul de pré-image par élimination de quantificateurs et des calculs d’enveloppes convexes. Nous montrons que HullQe est capable, automatiquement, de renforcer des objectifs de preuve correspondant à la vérification de patrons de conception courants en avionique. Pour autant que nous sachions, les méthodes actuelles sont incapables de conclure sur ces problèmes. Nous détaillons nos améliorations de l’algorithme d’élimination de quantificateurs de Monniaux afin d’assurer le passage à l’échelle sur nos systèmes. Notre framework formel Stuff est une implémentation de notre architecture parallèle composée de HullQe, d'une technique de découverte d’invariants basée sur des templates, et d'une généralisation de PDR à l’arithmétique. / This work studies the verification of software components in avionics critical embedded systems. As the failure of suchsystems can have catastrophic consequences, it is mandatory to make sure they are consistent with their specification.Formal verification consists in proving that a system respects its specification if it does, or to produce a counterexample if itdoes not. Current methods are unable to handle the verification problems stemming from realistic systems. Discoveringadditional information (invariants) on the system can however restrict the search space enough to strengthen the proofobjective: the information discovered allow to "easily" reach a conclusion. We define a parallel architecture for invariantdiscovery methods allowing them to collaborate around a k-induction engine. In this context we propose a new heuristic forthe generation of potential invariants by combining an iterated preimage calculus by quantifier elimination with convexhull computations, called HullQe. We show that HullQe is able to automatically strengthen proof objectives correspondingto safety properties on widespread design patterns in our field. To the best of our knowledge, these systems elude currenttechniques. We also detail our improvements to the quantifier elimination algorithm by David Monniaux in 2008, so that itscales to computing preimages on our systems. Our formal framework Stuff is an implementation of the parallel architecturewe propose in which we implemented not only HullQe, but also a template-based invariant discovery technique, and ageneralisation to Property Directed Reachability to linear real arithmetic and integer octagons.

A teoria da sociedade de risco foi estabelecida por Ulrich Beck no ano de 1986 por meio da obra Risikogesellschaft - Auf dem Weg in eine andere Mordene. Beck propõe um novo rumo para a pesquisa sociológico segundo o qual o parâmetro clássico de estudo das ciências sociais baseado na luta entre classe deveria ser superado, pois esse modelo seria incapaz de explicar as complexas relações da sociedade moderna (pós-industrial) em que a característica principal não mais se encontra na disputa entre detentores do capital e explorado, mas, sim, em tentar reduzir ou repartir de modo mais justo os riscos sociais. Foi estabelecida a teoria da sociedade de risco a partir do incremento da tecnologia (por exemplo, energia nuclear, produção de alimentos transgênicos, etc). Com essas novas técnicas científicas praticamente impossível é conter os riscos sociais, uma vez que são neste momento difusos, ou seja, atingem um número indeterminado de pessoas. Neste ambiente de proliferação de riscos a demanda social direcionada à proteção por meio de intrumentos de controle dos riscos ganha papel de destaque. O sentimento social de insegurança baseia-se, principalmente, no fato de não ser mais o ser humano capaz de prever todos os efeitos das condutas a que está sendo diariamente exposto. Diante desse novo quadro social, o Direito, em especial, o Direito Penal não deve mostrar indiferença às necessidades de proteção. Neste contexto, questiona-se se o Direito Penal clássico, isto é, o Direito Penal produzido segundo bases Iluministas tipicamente liberal-burguesas do final século XIX conseguirá fornecer respostas úteis a um modelo social tão diferente daquele originalmente considerado. É necessário um arcabouço teórico próprio aos dias atuais, sem desconsiderar o avanço no campo dos direitos humanos. Defende-se na presente dissertação ter o Direito Penal por escopo a proteção de bens jurídicos, desde que, evidentemente, estejam lastreados no princípio da dignidade humana que serve de inspiração a todos os ordenamentos materialmente democráticos na atualidade. Não se pode negar o relevante papel assumido pelo bem jurídico-penal individual como contenção do jus puniendi estatal, no entanto, tal instrumento teórico deve ser combinado a outro: o bem jurídico-penal transindividual. Como técnica dogmática visando à gestão dos riscos por meio do Direito Penal destinado à proteção de bens jurídicos transindividuais adotar-se-á, geralmente, a utilização de tipos penais de perigo abstrato. Por fim, expõe este trabalho como pode ser empregado o bem jurídico-penal transindividual em zonas de difusão de riscos como a genética e o meio-ambiente. / The risk society theory was developed by Ulrich Beck in 1986, in his work entitled Risikogesellschaft - Auf dem Weg in eine andere Mordene. Beck proposes a new perspective for sociological research, according to which the classical parameter in the Social Sciences, based upon class conflict, should be overcome because it would be unable to clarify the complex relations inherent to modern (post-industrial) society in which the main feature is no longer the conflict between capital owners and the exploited, but actually trying to reduce or share in a fairer manner the social risks. The risk society theory was established in the context of technological progress (e.g. nuclear power, genetically modified food, etc). These new techniques made it virtually impossible to contain social risk, because it became diffuse, in other words, it affects an indetermined number of people. In this environment of increasing risk,social demands for protection through risk management instruments obtain a key role. Social feelings of unsafeness are based, mainly, upon the fact that human beings are no longer able to predict all the effects of the acts to which they are subject to on a daily basis. In the face of this new social frame, Law and especially Penal Law cannot show indifference to the need of protection. In this context, we question if the classical Penal Law which is the Penal Law produced according to the liberal bourgeois principles of the European enlightenment from the last quarter of the nineteenth century will be able to give helpful answers to a social framework so much different from the original one. A theoretical framework that fits the present day becomes necessary, while not disregarding the progress made in the field of human rights. In the present dissertation is advocated the standpoint that the objective of Penal Law is the protect legal interests, provided that, evidently, they are based on the principle of human dignity which is the inspiration to all materially democratic Law systems of the present day. The relevant role that individual penal legal interests play in containing the states ius puniendi is undeniable. However, this theoretical instrument has to be combined to another one: the transindividual penal legal interest. As a dogmatic tecnique that aims at risk management through Penal Law, usually abstract danger crimes will be adopted. Finally, it is presented in this work how the transindividual penal legal good can the employed in fields of diffusion of risk such as genetics and the environment.

A noção de tipo é intrínseca ao raciocínio humano, na medida que os seres humanos tendem a "classificar" os objetos segundo seu use e seu comportamento como parte do processo de resolução de problemas. Tal classificação dos objetos implica numa abstração das características irrelevantes dos mesmos,permitindo dessa maneira uma simplificação importante da complexidade do universo de discurso Por outro lado, certos problemas são altamente complexos e requerem um tratamento diferenciado.Esses problemas exigem, para sua resolução, um grande conhecimento do universo de discurso. O ponto critico nesta situação é que o domínio do problema não é exato como poderia ser um domínio matemático. Pelo contrario, ele inclui geralmente aspectos ambíguos e pouco formais que dificultam seu entendimento. Tal domínio a chamado de senso comum e é objeto de estudo de uma linha da computação, a Inteligência Artificial (IA). Para [KRA 87], entre outros, as soluc6es pare muitos problemas de IA dependern mais da capacidade de adquirir e manipular conhecimento do que de algoritmos sofisticados. Por este motivo, existem na IA muitos tipos de linguagens que tentam, de di verses maneiras,facilitar a representação de conhecirnentos sobre universos de discurso de problemas particulares. São as chamadas Linguagens de Representação de Conhecimento. A noção de tipo e implícita nas linguagens de representação de conhecimento, uma vez que tal noção é natural no raciocínio humano e esta intimamente ligada ao conceito de abstração. Este trabalho visa explicitar a noção de tipo subjacente ao núcleo definido da linguagem RECON-II. Para isto, foi realizado um estudo semântico prévio para identificar os tipos semânticos da linguagem. A partir da noção semântica dos tipos foi possível definir a correspondente sintática e finalmente, descrever um Sistema de Tipos para RECON-II. Um Sistema de Tipos consiste numa Linguagem de Tipos (tipos básicos + construtores de tipos) e num Sistema de Dedução que relaciona as expresses da linguagem objeto (linguagem de programação com as expresses da linguagem de tipos. Para a primeira etapa realizada neste trabalho, a determinação da semântica da linguagem, foi utilizado o método algébrico. Nele toda expressão RECON-II é um termo de uma assinatura Z, de modo quo cada assinatura Z determina um conjunto de expressos RECON-UL Mas, por outro lado, uma assinatura também determina um conjunto de álgebras. Dessas álgebras-Z só um subconjunto significativo para as expressões RECON-II. As álgebras-Z significativas são aquelas que satisfazem a assinatura-Z mais um conjunto E de axiomas. A assinatura-Z junto como o conjunto E de axiomas constituem o quo se denomina Tipo Abstrato de Dados, T=CZ, E), e as álgebras-Z significativas são os chamados modelos-Z do tipo T. Assim, uma expressão RECON-II a e um elemento da álgebra de termos quo g uma Álgebra gerada a partir do E. Essa álgebra, 44 4-) conjunto das expressi5es_: RECON-II significativas, e o modelo inicial de tais expressões WOG 781 Dado um tipo abstrato T existe um único modelo para T, ou uma classe de modelos, não isomórficos, denominada MCT>. No segundo caso, asses modelos constituem uma "quasi" ordem parcial com modelo inicial e terminal. A existência e unicidade do modelo inicial para qualquer tipo T foi demonstrada por [GOG 77] Com Σ = (S, F). a (Ws )para 9 S, e o conjunto dos termos de "sort." e. Na RECON-II, são os termos de uma categoria sintática determinada. As categorias sintáticas principais são : Conceitos, Relações, Funções e Redes. Um tipo semântico para s E S é um subconjunto M(T) S M(T) quo satisfaz os axiomas E exigidos de (WΣ) s, constituindo o tipo abstrato T .s.(por exemplo TConceitos, TRedes, etc.) Por último foi definido o Sistema de Tipos, que consiste numa estrutura sintática adequada para os tipos semânticos de cada expressão-RECON e, para cada expressão de tipo, um conjunto de regras de inferências que permuta, a partir de uma expressão-RECON inferir seu tipo mais geral. / The notion of type is intrinsic to human reasoning, since human beings tend to classify objects according their use and behaviour as part of the problem solving process. By classifying objects, their irrevelant characteristics are abstrated; in this way, the complexity of the universe of discourse is much reduced. On the other hand, certain problems are higly complex and require a differentiated treatament. In order to solve these problems, a great knowledge of de universe of discourse is needed. The critical proint in this situation is that the domain of the problem isn't as precise as a matliematic domain. On the contrary, it generally, includes ambiguous and not very formal aspects wich make its uderstanding difficult.. Such a domains is known as common sense and this is the object of studies of one line of Computer Science, Artificial Intelligence CAI). For [KRA 871, among others, the solutions for many AI problems depend on the ability for acquiring and manipulating knowledge rather than on sophisticated algorithm. For this reason, there are in AI many type of languages that attemps in different ways, to represent the UD of a particular problem. These languagesare known as Knowledge Representation Languages. The notion of type is implicit in Knowledge Representation Languages, since it is natural in human reasoning and closely rrelated to the concept of abstraction. This work intends to make the notion of type intrinsic to the RECON-II's kernel language, explicity. In order to do this, a preliminary semantic stidy was carriedaut to identify the semantic types of the languages. From the semantic notion of the types it was possible to define the sintactic counterpart and finally to describe a Type System for RECON- II. A Type System conssit of a type language (basic types + types constructors) end a deduction system that relattes expressions in the language object (programming language) to the expressions in the type language. In the first step of this work, language semantic determination, the algebric method was used. In it every RECON-II expression is one term of a signature 2, so Chet every signature 2 determines a RECON-II expressions set. On the other hand, a signature also determines a set of algebras. Out of these 2-algebras only one subset is significant to the RECON-II expressions. The significant 2-algebras are those t.het satisfy the 2-signature and a' set E of axioms. Together the 2-siganture and the set E of axioms, constitute what is called Abstract Data Type T = (2, E) and the significant E-algebras are the so-called Z-models of type T. Therefore a RECON-II expressions a is an element, of the wich is an algebra generated from E. This 2- 211)1`.9 is the set. of Sl !.171-11. RECON-II expressions, and is the initia; model of such expressions CLOG 78]. Given an abstract type T there is one single model for T or one class of nonisomorphic models denominated M(T). In the second cas,4, these models constitute a "quasi" partial order with an initial and terminal model. the exixstence nad uniqueness of the inititia1 model for any type T was shown at. CLOG 773. With r = <SS, F ) , (W ) for s S. is the set of terms of e sort. In RECON-II, those are •he term of determinate sintactic category. The main -sintactic categories are Concepts, Relations, Functions and Nets. A semantic type for s E S is s subset MCI') S MCT> that satisfies the axioms E required from C.W_), constituting the 8 2- abstract type T (for instance Tconcepts, Tnets, etc.). 8 Finally, the type systems was defined, consisting a syntatic structure suitable for the semantic types of each RECON-II expressions and for every type expressions, a set of inference rules wich allows infering its more general type from a RECON-II expressions.

Cette thèse étudie la vérification automatique de propriétés de sûreté de systèmes logico-numériques discrets ou hybrides. Ce sont des systèmes ayant des variables booléennes et numériques et des comportements discrets et continus. Notre approche est fondée sur l'analyse statique par interprétation abstraite. Nous adressons les problèmes suivants : les méthodes d'interprétation abstraite numériques exigent l'énumération des états booléens, et par conséquent, ils souffrent du probléme d'explosion d'espace d'états. En outre, il y a une perte de précision due à l'utilisation d'un opérateur d'élargissement afin de garantir la terminaison de l'analyse. Par ailleurs, nous voulons rendre les méthodes d'interprétation abstraite accessibles à des langages de simulation hybrides. Dans cette thèse, nous généralisons d'abord l'accélération abstraite, une méthode qui améliore la précision des invariants numériques inférés. Ensuite, nous montrons comment étendre l'accélération abstraite et l'itération de max-stratégies à des programmes logico-numériques, ce qui aide à améliorer le compromis entre l'efficacité et la précision. En ce qui concerne les systèmes hybrides, nous traduisons le langage de programmation synchrone et hybride Zelus vers les automates hybrides logico-numériques, et nous étendons les méthodes d'analyse logico-numérique aux systèmes hybrides. Enfin, nous avons mis en oeuvre les méthodes proposées dans un outil nommé ReaVer et nous fournissons des résultats expérimentaux. En conclusion, cette thèse propose une approche unifiée à la vérification de systèmes logico-numériques discrets et hybrides fondée sur l'interprétation abstraite qui est capable d'intégrer des méthodes d'interprétation abstraite numériques sophistiquées tout en améliorant le compromis entre l'efficacité et la précision. / This thesis studies the automatic verification of safety properties of logico-numerical discrete and hybrid systems. These systems have Boolean and numerical variables and exhibit discrete and continuous behavior. Our approach is based on static analysis using abstract interpretation. We address the following issues: Numerical abstract interpretation methods require the enumeration of the Boolean states, and hence, they suffer from the state space explosion problem. Moreover, there is a precision loss due to widening operators used to guarantee termination of the analysis. Furthermore, we want to make abstract interpretation-based analysis methods accessible to simulation languages for hybrid systems. In this thesis, we first generalize abstract acceleration, a method that improves the precision of the inferred numerical invariants. Then, we show how to extend abstract acceleration and max-strategy iteration to logico-numerical programs while improving the trade-off between efficiency and precision. Concerning hybrid systems, we translate the Zelus hybrid synchronous programming language to logico-numerical hybrid automata and extend logico-numerical analysis methods to hybrid systems. Finally, we implemented the proposed methods in ReaVer, a REActive System VERification tool, and provide experimental results. Concluding, this thesis proposes a unified approach to the verification of discrete and hybrid logico-numerical systems based on abstract interpretation, which is capable of integrating sophisticated numerical abstract interpretation methods while successfully trading precision for efficiency.