Cette thèse se concentre autour du problème de l'évaluation des requêtes. Étant donné une requête q et une base de données D, l'objectif est de calculer l'ensemble q(D) des nuplets résultant de l'évaluation de q sur D. Toutefois, l'ensemble q(D) peut être plus grand que la base de données elle-même car elle peut avoir une taille de la forme n^l où n est la taille de la base de données et l est l'arité de la requête. Calculer entièrement q(D) peut donc nécessiter plus que les ressources disponibles. L'objectif principal de cette thèse est une solution particulière à ce problème: une énumération de q(D) avec un délai constant. Intuitivement, cela signifie qu'il existe un algorithme avec deux phases: une phase de pré-traitement qui fonctionne en temps linéaire dans la taille de la base de données, suivie d'une phase d'énumération produisant un à un tous les éléments de q(D) avec un délai constant (indépendant de la taille de la base de données) entre deux éléments consécutifs. En outre, quatre autres problèmes sont considérés: le model-checking (où la requête q est un booléen), le comptage (où on veut calculer la taille |q(D)|), les tests (où on s'intéresse à un test efficace pour savoir si un uplet donné appartient au résultat de la requête) et la j-ième solution (où on veut accéder directement au j-ième élément de q(D)). Les résultats présentés dans cette thèse portent sur les problèmes ci-dessus concernant: - les requêtes du premier ordre sur les classes de structures de degré borné, - les requêtes du second ordre monadique sur les classes de structures de largeur d'arborescente bornée, - les requêtes du premier ordre sur les classes de structures avec expansion bornée.

Les objets électromagnétiques sont conçus en considérant des matériaux aux propriétés radio-électriques (permittivité, perméabilité) homogènes. Néanmoins, lors de leur réalisation les matériaux réels peuvent présenter des fluctuations de ces propriétés. Ce travail porte sur la mise au point d'outils capables d'estimer le champ diffusé produit par les fluctuations. Trois méthodes ont été mises au point : EMFORS, ABE et RECY pour la détermination du champ diffusé par des fluctuations de permittivité et de perméabilité. La modélisation de la contribution des fluctuations de perméabilité est une avancée significative. En effet, il n'existait pas d'outil traitant ce problème dans toute sa généralité pour estimer le champ diffusé par cette fluctuation. L'absence de magnétisme aux fréquences des ondes optiques en est la principale raison.La méthode RECY est une méthode qui permet d'estimer à l'aide du principe de réciprocité le champ diffusé dans un objet quelconque à partir de la simple connaissance du champ dans l'objet sans défaut et de la fluctuation. Cette méthode permet une fois le calcul du champ idéal effectué par une méthode quelconque (analytique ou numérique) de calculer le champ diffusé de n'importe quelle forme de fluctuation. Nous avons appliqué RECY à des structures comme un réseau simple, une structure industrielle et aux cristaux photoniques. / Electromagnetic objects are designed by considering homogeneous materials properties (permittivity, permeability). However, during their realization real materials may present fluctuations of their properties. This work focuses on the development of tools able to estimate scattered fields produced by fluctuations. Three methods have been developed: EMFORS, ABE and RECY for the determination of the scattered field by fluctuations of permittivity and permeability. Taking into account permeability fluctuations is a significant advance. Indeed, there was no tool to estimate the scattered field by such a fluctuation, due to the absence of magnetic properties at optical frequencies.The RECY method is a method which allows to estimate the field in an object using the principle of reciprocity from the knowledge of the field in the object without defect and of the fluctuation function. This method allows, once the ideal field calculated by any method (analytic or digital), to obtain the scattered field from any structure.We applied RECY for structures such as elementary gratings, an industrial structure and photonic crystals.

We examine how logical reasoning in the two-variable guarded fragment with counting quantifiers can be integrated with databases in the presence of certain integrity constraints, called path-functional dependencies. In more detail, we establish that the problems of satisfiability and finite satisfiability for the two-variable guarded fragment with counting quantifiers, a database, and binary path-functional dependencies are EXPTIME-complete; we also establish that the data complexity of these problems is NP-complete. We establish that query answering for the above fragment (with a database and binary path-functional dependencies) is 2-EXPTIME-complete with respect to arbitrary models, and provide a 2-EXPTIME upper bound for finite models. Finally, we establish that the data complexity of query answering is coNP-complete, both with respect to arbitrary and finite models.

Gramática de grafos é uma linguagem formal bastante adequada para sistemas cujos estados possuem uma topologia complexa (que envolvem vários tipos de elementos e diferentes tipos de relações entre eles) e cujo comportamento é essencialmente orientado pelos dados, isto é, eventos são disparados por configurações particulares do estado. Vários sistemas reativos são exemplos desta classe de aplicações, como protocolos para sistemas distribuídos e móveis, simulação de sistemas biológicos, entre outros. A verificação de gramática de grafos através da técnica de verificação de modelos já é utilizada por diversas abordagens. Embora esta técnica constitua um método de análise bastante importante, ela tem como desvantagem a necessidade de construir o espaço de estados completo do sistema, o que pode levar ao problema da explosão de estados. Bastante progresso tem sido feito para lidar com esta dificuldade, e diversas técnicas têm aumentado o tamanho dos sistemas que podem ser verificados. Outras abordagens propõem aproximar o espaço de estados, mas neste caso não é possível a verificação de propriedades arbitrárias. Além da verificação de modelos, a prova de teoremas constitui outra técnica consolidada para verificação formal. Nesta técnica tanto o sistema quanto suas propriedades são expressas em alguma lógica matemática. O processo de prova consiste em encontrar uma prova a partir dos axiomas e lemas intermediários do sistema. Cada técnica tem argumentos pró e contra o seu uso, mas é possível dizer que a verificação de modelos e a prova de teoremas são complementares. A maioria das abordagens utilizam verificadores de modelos para analisar propriedades de computações, isto é, sobre a seqüência de passos de um sistema. Propriedades sobre estados alcançáveis só são verificadas de forma restrita. O objetivo deste trabalho é prover uma abordagem para a prova de propriedades de grafos alcançáveis de uma gramática de grafos através da técnica de prova de teoremas. Propõe-se uma tradução (da abordagem Single-Pushout) de gramática de grafos para uma abordagem lógica e relacional, a qual permite a aplicação de indução matemática para análise de sistemas com espaço de estados infinito. Definiu-se gramática de grafos utilizando estruturas relacionais e aplicações de regras com linguagens lógicas. Inicialmente considerou-se o caso de grafos (tipados) simples, e então se estendeu a abordagem para grafos com atributos e gramáticas com condições negativas de aplicação. Além disso, baseado nesta abordagem, foram estabelecidos padrões para a definição, codificação e reuso de especificações de propriedades. O sistema de padrões tem o objetivo de auxiliar e simplificar a tarefa de especificar requisitos de forma precisa. Finalmente, propõe-se implementar definições relacionais de gramática de grafos em estruturas de event-B, de forma que seja possível utilizar os provadores disponíveis para event-B para demonstrar propriedades de gramática de grafos. / Graph grammars are a formal language well-suited to applications in which states have a complex topology (involving not only many types of elements, but also different types of relations between them) and in which behaviour is essentially data-driven, that is, events are triggered basically by particular configurations of the state. Many reactive systems are examples of this class of applications, such as protocols for distributed and mobile systems, simulation of biological systems, and many others. The verification of graph grammar models through model-checking is currently supported by various approaches. Although model-checking is an important analysis method, it has as disadvantage the need to build the complete state space, which can lead to the state explosion problem. Much progress has been made to deal with this difficulty, and many techniques have increased the size of the systems that may be verified. Other approaches propose to over- and/or under-approximate the state-space, but in this case it is not possible to check arbitrary properties. Besides model checking, theorem proving is another wellestablished approach for verification. Theorem proving is a technique where both the system and its desired properties are expressed as formulas in some mathematical logic. A logical description defines the system, establishing a set of axioms and inference rules. The process of verification consists of finding a proof of the required property from the axioms or intermediary lemmas of the system. Each verification technique has arguments for and against its use, but we can say that model-checking and theorem proving are complementary. Most of the existing approaches use model checkers to analyse properties of computations, that is, properties over the sequences of steps a system may engage in. Properties about reachable states are handled, if at all possible, only in very restricted ways. In this work, our main aim is to provide a means to prove properties of reachable graphs of graph grammar models using the theorem proving technique. We propose an encoding of (the Single-Pushout approach of) graph grammar specifications into a relational and logical approach which allows the application of the mathematical induction technique to analyse systems with infinite state-spaces. We have defined graph grammars using relational structures and used logical languages to model rule applications. We first consider the case of simple (typed) graphs, and then we extend the approach to the non-trivial case of attributed-graphs and grammars with negative application conditions. Besides that, based on this relational encoding, we establish patterns for the presentation, codification and reuse of property specifications. The pattern has the goal of helping and simplifying the task of stating precise requirements to be verified. Finally, we propose to implement relational definitions of graph grammars in event-B structures, such that it is possible to use the event-B provers to demonstrate properties of a graph grammar.

Statistical distributions also known as probability distributions are used to model a random experiment. Probability distributions consist of probability density functions (pdf) and cumulative density functions (cdf). Probability distributions are widely used in the area of engineering, actuarial science, computer science, biological science, physics, and other applicable areas of study. Statistics are used to draw conclusions about the population through probability models. Sample statistics such as the minimum, first quartile, median, third quartile, and maximum, referred to as the five-number summary, are examples of order statistics. The minimum and maximum observations are important in extreme value theory. This paper will focus on the probability distribution of the minimum observation, also known as the first order statistic, when the sample size is random.

Deux groupes sont dits élémentairement équivalents s'ils satisfont les mêmes énoncés du premier ordre dans le langage des groupes. Aux environs de l'année 1945, Tarski posa la question suivante, connue désormais comme le problème de Tarski : les groupes libres non abéliens sont-ils élémentairement équivalents ? Une réponse positive à cette fameuse question fut apportée plus d'un demi-siècle plus tard par Sela, et en parallèle par Kharlampovich et Myasnikov, comme le point d'orgue de deux volumineuses séries de travaux. Dans la foulée, Sela généralisa aux groupes hyperboliques sans torsion, dont les groupes libres sont des représentants emblématiques, les méthodes de nature géométrique qu'il avait précédemment introduites à l'occasion de son travail sur le problème de Tarski. Les résultats rassemblés ici s'inscrivent dans cette lignée, en s'en démarquant toutefois dans la mesure où ils traitent des théories du premier ordre des groupes hyperboliques en présence de torsion. Dans un premier chapitre, on démontre, entre autres, que tout groupe de type fini qui est élémentairement équivalent à un groupe hyperbolique est lui-même hyperbolique. On démontre ensuite que les groupes virtuellement libres sont presque homogènes, ce qui signifie que deux éléments qui sont indiscernables du point de vue de la logique du premier ordre sont dans la même orbite sous l'action du groupes des automorphismes du groupe ambiant, à une indétermination finie près. Enfin, on donne une classification complète des groupes virtuellement libres de type fini du point de l'équivalence élémentaire à deux quantificateurs. / Two groups are said to be elementarily equivalent if they satisfy the same first-order sentences in the language of groups, that is the same mathematical statements whose variables are only interpreted as elements of a group. Around 1945, Tarski asked the following question : are non-abelian free groups elementarily equivalent? An affirmative answer to this famous Tarski's problem was given in 2006 by Sela and independently by Kharlampovich and Myasnikov, as the culmination of two voluminous series of papers. Then, Sela gave a classification of all finitely generated groups that are elementarily equivalent to a given torsion-free hyperbolic group. The results contained in the present thesis fall into this context and deal with first-order theories of hyperbolic groups with torsion. In the first chapter, we prove that any finitely generated group that is elementarily equivalent to a hyperbolic group is itself a hyperbolic group. Then, we prove that virtually free groups are almost homogeneous, meaning that elements are almost determined up to automorphism by their type, i.e. the first-order formulas they satisfy. In the last chapter, we give a complete classification of finitely generated virtually free groups up to elementary equivalence with two quantifiers.

This paper analyzes relationships between the roles of descriptions and actions in large scale, open ended, geographically distributed, concurrent systems. Rather than attempt to deal with the complexities and ambiguities of currently implemented descriptive languages, we concentrate our analysis on what can be expressed in the underlying frameworks such as the lambda calculus and first order logic. By this means we conclude that descriptions and actions complement one another: neither being sufficient unto itself. This paper provides a basis to begin the analysis of the very subtle relationships that hold between descriptions and actions in Open Systems.

Time-dependent density functional theory calculations have been carried out to determine the complex first-order hyperpolarizability in the two-photon resonance region of the molecule IDS-Cab. Calculations show that three strongly absorbing states, in the ultraviolet region, are separated to the extent that no significant interference of the imaginary parts of the tensor elements of the first-order hyper-polarizability occurs. Consequently, and in contrast to experimental findings [27], no reduced imaginary parts of the first-order hyperpolarizability in the two-photon resonant region can be seen.

Specification for process oriented applications tends to use languages that suffer from infinite, intractable or unpredictably irregular state spaces that thwart exhaustive searches by verification heuristics. However, conceptual schemas based on FOL, offer techniques for both integrating and verifying specifications in finite spaces. It is therefore of interest to transform process based specifications into conceptual schemata. Process oriented languages have an additional drawback in that reliable inputs to the integration of diverse specifications can result in unreliable outputs. This problem can more easily be addressed in a logic representation in which static and dynamic properties can be examined separately. The first part of the text describes a translation method from the process based language SDL, to first order logic. The usefulness of the method for industrial application has been demonstrated in an implementation. The method devised is sufficiently general for application to other languages with similar characteristics. Main contributions consist of: formalising the mapping of state transitions to event driven rules in dynamic entity-relationship schemas; analysing the complexity of various approaches to decomposing transitions; a conceptual representation of the source language that distinguishes meta- and object models of the source language and domain respectively. The second part of the text formally describes a framework for the integration of schemata that allows the exploration of their properties in relation to each other and to a set of integration assertions. The main contributions are the formal framework; an extension to conflicts between agents in a temporal action logic; complexity estimates for various integration properties. / QC 20101004

Focus of interest in this article are the concepts of globalization and civic citizenship and the questions are; what is required to be a global citizen, and how to work with this in civic education. The concept of civic citizenship implies democracy. A citizen is an independent and (to some extent) educated decision maker and actor, not a mere subject loyal to the sovereign. So whenever speaking of a global citizen democracy is implied. But the world is not a democratic place as such. Most of it in fact is quite undemocratic. The question therefore is how it is possible to act as a citizen (as a democrat) in global space. The article argues that this will only be possibly if citizens are capable of dealing with complex societal problems and to understand their own role as citizens (democrats) in relation to these problems. The argument is firstly that problems and issues in global space are complex and can only be understood interdisciplinary. Therefore the ability to reflect problems interdisciplinary is crucial to the global citizen. The second argument is that the ability of self-reflection is necessary for citizens in their efforts to understand, maintain and develop their own (democratic) identity and (democratic) values and practices in relation to the complexity and unfamiliarity of the various non-democratic identities, values and practices in a global space. Therefore it is suggested that students in civic education need to develop competencies of reflection on interdisciplinarity and self-reflection-as-citizen as key tools for analyzing societal problems and to act democratically on them. And it is suggested that dealing with interdisciplinarity requires use of second order concepts and that self-reflection as citizens requires third order concepts