No description available.

In the last two decades, qualitative spatial representation and reasoning, and in particular spatial logics, have been the subject of an increased interest from the Artificial Intelligence community. By a spatial logic, we understand a formal language whose variables range over subsets of a fixed topological space, called regions, and whose non-logical primitives have fixed geometric meanings. A spatial logic for reasoning about regions in a Euclidean space is called a Euclidean spatial logic. We consider first-order and quantifier-free Euclidean spatial logics with primitives for topological relations and operations, the property of convexity and the ternary relation of being closer-than. We mainly focus on the computational properties of such logics, but we also obtain interesting model-theoretic results. We provide a systematic overview of the computational properties of firstorder Euclidean spatial logics and fill in some of the gaps left by the literature. We establish upper complexity bounds for the (undecidable) theories of logics based on Euclidean spaces of dimension greater than one, which yields tight complexity bounds for all but two of these theories. In contrast with these undecidability results, we show that the topological theories based on one-dimensional Euclidean space are decidable, but non-elementary. We also study the computational properties of quantifier-free Euclidean spatial logics, and in particular those able to express the property of connectedness. It is known that when variables range over regions in the Euclidean plane, one can find formulas in these languages satisfiable only by regions with infinitely many connected components. Using this result, we show that the corresponding logics are undecidable. Further, we show that there exist formulas that are satisfiable in higher-dimensional Euclidean space, but only by regions with infinitely many connected components. We finish by outlining how the insights gained from this result were used (by another author) to show the undecidability of certain quantifier-free Euclidean spatial logics in higher dimensions.

No description available.

No description available.

Dans cette thèse, l’étude de plusieurs modèles de systèmes magnétiques frustrés a été couverte. Leur racine commune est le modèle de la glace de spin, qui se transforme en modèle de la glace sur réseau kagome (kagome ice) et réseau en damier (square ice) à deux dimensions, et la chaîne d’Ising à une dimension. Ces modèles ont été particulièrement étudiés dans le contexte de transitions de phases avec un ordre magnétique induit par les contraintes du système : en effet, selon la perturbation envisagée, les contraintes topologiques sous-jacentes peuvent provoquer une transition de Kasteleyn dans le kagome ice, ou une transition de type vitreuse dans la square ice, due à l’émergence d’un ordre ferromagnétique dans une chaîne d’Ising induit seulement par des effets de taille fini. Dans tous les cas, une étude détaillée par simulations numériques de type Monte Carlo ont été comparées à des résultats théoriques pour déterminer les propriétés de ces transitions. Les contraintes topologiques du kagome ice ont requis le développement d’un algorithme de vers permettant aux simulations de ne pas quitter l’ensemble des états fondamentaux. Une revue poussée de la thermodynamique et de la réponse de la diffraction de neutrons sur kagome ice sous un champ magnétique planaire arbitraire, nous ont amené à une compréhension plus profonde de la transition de Kasteleyn, et à un modèle numérique capable de prédire les figures de diffraction de neutrons de matériau de kagome ice dans n’importe quelles conditions expérimentales. Sous certaines conditions, ce modèle a révélé des propriétés thermodynamiques quantifiées et devrait fournir un terreau fertile pour de futurs travaux sur les conséquences des contraintes et transitions de phases topologiques. Une étude combinée du square ice et de la chaîne d’Ising a mise en lumière l’apparition d’un ordre sur réseau potentiellement découplé de l’ordre ferromagnétique sous-jacent, et particulièrement pertinent pour les réseaux magnétiques artificiels obtenus par lithographie. / In this thesis a series of model frustrated magnets have been investigated. Their common parent is the spin ice model, which is transformed into the kagome ice and square ice models in two-dimensions, and an Ising spin chain model in one-dimension. These models have been examined with particular interest in the spin ordering transitions induced by constraints on the system: a topological constraint leads, under appropriate conditions, to the Kasteleyn transition in kagome ice and a lattice freezing transition is observed in square ice which is due to a ferromagnetic ordering transition in an Ising chain induced solely by finite size effects. In all cases detailed Monte Carlo computational simulations have been carried out and compared with theoretical expressions to determine the characteristics of these transitions. In order to correctly simulate the kagome ice model a loop update algorithm has been developed which is compatible with the topological constraints in the system and permits the simulation to remain strictly on the groundstate manifold within the appropriate topological sector of the phase space. A thorough survey of the thermodynamic and neutron scattering response of the kagome ice model influenced by an arbitrary in-plane field has led to a deeper understanding of the Kasteleyn transition, and a computational model that can predict neutron scattering patterns for kagome ice materials under any experimental conditions. This model has also been shown to exhibit quantised thermodynamic properties under appropriate conditions and should provide a fertile testing ground for future work on the consequences of topological constraints and topological phase transitions. A combined investigation into the square ice and Ising chain models has revealed ordering behaviour within the lattice that may be decoupled from underlying ferro- magnetic ordering and is particularly relevant to magnetic nanoarrays.