This thesis presents a new approach to local decision-making in multi-agent systems with varying amounts of communication. Here, local decision-making refers to action choices which are made in a decentralized fashion by individual agents based on the information which is locally available to them. The work described here is set within the multi-agent decision process framework. Unreliable, faulty or stochastic communication patterns present a challenge to these settings which usually rely on precomputed, centralised solutions to control individual action choices. Various approximate algorithms for local decision-making are developed for scenarios with and without sequentiality. The construction of these techniques is based strongly on methods of Bayesian inference. Their performance is tested on synthetic benchmark scenarios and compared to that of a more conservative approach which guarantees coordinated action choices as well as a completely decentralized solution. In addition, the method is applied to a surveillance task based on real-world data. These simulation results show that the algorithms presented here can outperform more traditional approaches in many settings and provide a means for flexible, scalable decision-making in systems with varying information exchange between agents.

Any model of access control has two fundamental aims: to ensure that resources are protected from inappropriate access and to ensure that access by authorised users is appropriate. Traditionally, approaches to access control have fallen into one of two categories: discretionary access control (DAC) or mandatory access control (MAC). More recently, role-based access control (RBAC) has offered the potential for a more manageable and flexible alternative. Typically, though, whichever model is adopted, any changes in the access control policy will have to be brought about via the intervention of a trusted administrator. In an ever-more connected world, with a drive towards autonomic computing, it is inevitable that a need for systems that support automatic policy updates in response to changes in the environment or user actions will emerge. Indeed, data management guidelines and legislation are often written at such a high level of abstraction that there is almost an implicit assumption that policies should react to contextual changes. Furthermore, as access control policies become more complicated, there is a clear need to express and reason about such entities at a higher level of abstraction for any meaningful analysis to be tractable, especially when consideration of complex state is involved. This thesis describes research conducted in formalising an approach to access control, termed evolving access control (EAC), that can support the automatic evolution of policies based on observed changes in the environment as dictated by high-level requirements embodied in a metapolicy. The contribution of this research is a formal, conceptual model of EAC which supports the construction, analysis and deployment of metapolicies and policies. The formal EAC model provides a framework to construct and describe metapolicies and to reason about how they manage the evolution of policies. Additionally, the model is used to analyse metapolicies for desirable properties, and to verify that policies adhere to the high-level requirements of the metapolicy. Furthermore, the model also allows the translation of verified policies to machine-readable representations, which can then be deployed in a system that supports fine-grained, dynamic access control.

No description available.

Although death due to lethal cardiac arrhythmias is the leading cause of mortality in Western Society, many of the fundamental mechanisms underlying their onset, maintenance and termination, still remain poorly understood. In recent years, experimental techniques such as optical mapping have provided useful high-resolution recordings of cardiac electrical dynamics during complex arrhythmias and defibrillation episodes, which have been combined with detailed computer simulations to further our understanding of these phenomena. However, mechanistic enquiry is severely restricted as the optical mapping technique suffers from a number of distortion effects which compromise the fidelity of the experimental measurements, presenting difficulties in the comparison of experimental data with computational simulations. This Thesis presents a thorough investigation into the distortion effects encountered in optical mapping experiments, guided by the development of a coherent series of computational models. The models presented successfully characterise the specific mechanisms of fluorescent signal distortion due to photon scattering. Photon transport in cardiac tissue is modelled using both continuous (reaction-diffusion) and discrete stochastic (Monte Carlo) approaches to simulate the effects of photon scattering within the myocardium upon the recorded fluorescent signal, which include differing levels of detail and associated computational complexity. Specifically, these models are used to investigate the important role played by the complex ventricular structural anatomy, as well as the specifics of the experimental set-up itself. In addition, a tightly coupled electromechanical model of a contracting cardiac fibre is developed which provides an important first-step towards the development of a model to quantitatively assess the distortion observed when recording from a freely contracting cardiac preparation. Simulation of these distortion effects using the models allows discrimination to be made between those parts of the experimental signal which are due to underlying tissue electrophysiology and those due to artifact, facilitating a more accurate interpretation of experimentally-obtained data. The models presented succeed in two main respects. Firstly, they provide a ‘post-processing’ tool which can be added on to computational simulations of electrical activation, allowing for a more accurate and faithful comparison between simulations and experiments, helping to validate predictions made by electrical models. Secondly, they provide a higher degree of mechanistic insight into the fundemental ways in which optical signals are distorted, showing how this distortion can be maximised or controlled. The understanding and quantification of the fundemental mechanisms of optical mapping signal distortion, provided by this Thesis, therefore fulfils an important role in the study of arrhythmia mechanisms.

With sensor technology gaining maturity and becoming ubiquitous, we are experiencing an unprecedented wealth of sensor data. In most sensing scenarios, the measurements generated by sensor networks are noisy and usually annotated with some measure of uncertainty. The problem we address in this thesis is how to estimate the accuracy of the sensor systems based on the probabilistic measurements they provide. This problem is increasingly common in many settings, such as multiple sensing services are competing for the same group of users, detecting faults in large scale networks, or establishing trustworthiness of different individuals in social sensing. It is also challenging in many ways, for instance, the ground truth of the monitored states is absent, the users often lack a clear view of the implementation details of the sensor systems, and the reported accuracy can be misleading. To address theses challenges, in this thesis we formulate the problem of estimating the accuracy of sensor systems in a general manner that applies to a broad spectrum of sensing scenarios. We then propose an accuracy estimation framework that breaks the problem into layers, which can be implemented in different ways. We present a novel inference-based accuracy estimation approach, which assesses the accuracy of sensor systems by comparing the reported measurements with the states inferred with the probabilistic measurements from all systems and available prior knowledge. We also propose a new learning-based approach for accuracy estimation, which employs novel parameter learning techniques. The learned parameters are either used to improve estimating the accuracy of sensor measurements, or to derive the accuracy of sensor systems directly in certain cases. We perform a systematic experimental evaluation on two datasets collected from real-world sensor deployments, where an array of different approaches are juxtaposed and compared extensively. We discuss how they trade accuracy for computation cost, and how this trade-off largely depends on the knowledge of the sensing scenarios. We also show that the proposed approaches outperform the competing ones in estimating accuracy and ranking the sensor systems.

This thesis investigates permutation pattern classes in a language theoretic context. Specifically we explored the regularity of sets of permutations under the rank encoding. We found that the subsets of plus- and minus-(in)decomposable permutations of a regular pattern class under the rank encoding are also regular languages under that encoding. Further we investigated the sets of permutations, which in their block-decomposition have the same simple permutation, and again we found that these sets of permutations are regular languages under the rank encoding. This natural progression from plus- and minus-decomposable to simple decomposable permutations led us further to the set of simple permutations under the rank encoding, which we have also shown to be regular under the rank encoding. This regular language enables us to find the set of simple permutations of any class, independent of whether the class is regular under the rank encoding. Furthermore the regularity of the languages of some types of classes is discussed. Under the rank encoding we show that in general the skew-sum of classes, separable classes and wreath classes are not regular languages; but that the direct-sum of classes, and with some restrictions on the cardinality of the input classes the skew-sum and wreath sum of classes in fact are regular under this encoding. Other encodings such as the insertion encoding and the geometric grid encoding are discussed and in the case of the geometric grid encoding alternative and constructive ways of retrieving the basis of a geometric grid class are suggested. The aforementioned results of the rank encoding have been implemented, amongst other previously shown results, and tested. The program is available and accessible to everyone. We show that the implementation for finding the block-decomposition of a permutation has cubic time complexity with respect to the length of the permutation. The code for constructing the automaton that accepts the language of all plus-indecomposable permutations of a regular class under the rank encoding has quadratic time complexity with respect to the alphabet of the language. The procedure to find the automaton that accepts the language of minus-decomposable permutations has complexity O(k⁵) and we show that the implementation of the automaton to find the language of simple permutations under the rank encoding has time complexity O(k⁵ 2ᵏ), where k is the size of the alphabet. Further we show benchmark testing on previous important results involving the rank encoding on classes and their bases.

Orientador: Roberto de Almeida Prado / Banca: Marcos Tadeu de Oliveira Pimenta / Banca: Gastão de Almeida Braga / Resumo: O presente trabalho tem como objetivo principal estudar a densidade de estados para o modelo de Anderson discreto multidimensional. Tal modelo constitui uma família de operadores de Schrödinger aleatórios e ergódicos. Primeiramente estudamos propriedades espectrais, ergódicas e determinamos explicitamente o espectro do modelo de Anderson, o qual é um conjunto não aleatório q.t.p.. Abordamos também condições de fronteira simples, de Neumann e de Dirichlet para tais operadores atuando no espaço l2 restrito a cubos finitos. Em seguida discutimos a medida densidade de estados com duas abordagens diferentes e a sua conexão com o espectro do modelo de Anderson, mais geralmente com o espectro de um operador ergódico. Além disso, estudamos o fenômeno chamado Lifshitz tails para o modelo de Anderson discreto, que descreve o comportamento assintótico da densidade integrada de estados próximo ao ínfimo (ou supremo) do espectro. Por fim estudamos a subarmonicidade do expoente de Lyapunov, a fórmula de Thouless e a log- Hölder continuidade da densidade integrada de estados. / Abstract: The present work have as main objective to study the density of states for the discrete multidimensional Anderson model. Such model constitutes a family of ergodic and random Schrödinger operators. First we study ergodic and spectral properties, and explicitly determine the spectrum of the Anderson model, which is a non-random set almost surely. We also deal with simple boundary conditions, Neumann and Dirichlet for such operators acting in the space l 2 restricted to finite cubes. Later we discuss the density of state measure with two different approaches and the connection between the spectrum of an ergodic operator and this measure. In addition, we study the phenomenon called Lifshitz tails for the discrete Anderson model, which describes the asymptotic behavior of the integrated density of states near the infimum (or supreme) of the spectrum. Finally we study the subharmonicity of the Lyapunov exponent, Thouless formula and log-Hölder continuity of the integrated density of states. / Mestre

In this dissertation, we present three results related to combinatorial algorithms in graph theory and scheduling, both of which are important subjects in the area of discrete mathematics and theoretical computer science. In graph theory, a graph is a set of vertices and edges, where each edge is a pair of vertices. A coloring of a graph is a function that assigns each vertex a color such that no two adjacent vertices share the same color. The first two results are related to coloring graphs belonging to specific classes. In scheduling problems, we are interested in how to efficiently schedule a set of jobs on machines. The last result is related to a scheduling problem in an environment where there is uncertainty on the number of machines. The first result of this thesis is a polynomial time algorithm that determines if an input graph containing no induced seven-vertex path is 3-colorable. This affirmatively answers a question posed by Randerath, Schiermeyer and Tewes in 2002. Our algorithm also solves the list-coloring version of the 3-coloring problem, where every vertex is assigned a list of colors that is a subset of {1, 2, 3}, and gives an explicit coloring if one exists. This is joint work with Flavia Bonomo, Maria Chundnovsky, Peter Maceli, Oliver Schaudt, and Maya Stein. A graph is H-free if it has no induced subgraph isomorphic to H. In the second part of this thesis, we characterize all graphs $H$ for which there are only finitely many minimal non-three-colorable H-free graphs. This solves a problem posed by Golovach et al. We also characterize all graphs H for which there are only finitely many H-free minimal obstructions for list 3-colorability. This is joint work with Maria Chudnovsky, Jan Goedgebeur and Oliver Schaudt. The last result of this thesis deals with a scheduling problem addressing the uncertainty regarding the machines. We study a scheduling environment in which jobs first need to be grouped into some sets before the number of machines is known, and then the sets need to be scheduled on machines without being separated. In order to evaluate algorithms in such an environment, we introduce the idea of an alpha-robust algorithm, one which is guaranteed to return a schedule on any number m of machines that is within an alpha factor of the optimal schedule on m machines, where the optimum is not subject to the restriction that the sets cannot be separated. Under such environment, we give a (5/3+epsilon)-robust algorithm for scheduling on parallel machines to minimize makespan, and show a lower bound of 4/3. For the special case when the jobs are infinitesimal, we give a 1.233-robust algorithm with an asymptotic lower bound of 1.207. This is joint work with Clifford Stein.

Orientador: Aluir Porfírio Dal Poz / Coorientador: José Roberto Nogueira / Banca: Messias Meneguette Júnior / Banca: Evandro Luis Linhari Rodrigues / Resumo: Este trabalho propõe um método de extração de contornos de telhados convexos de edifícios a partir de dados de um Modelo Digital de Superfície normalizado (MDSn). A modelagem do contorno se dará através do modelo de snake balloon, onde um funcional de energia dependente de muitas variáveis será otimizado através do algoritmo de Programação Dinâmica (PD). O MDSn se mostra atrativo na aplicação de extração de contornos de telhados de edifícios, pois permite separar as regiões de edifícios da maioria das outras regiões, principalmente as mais baixas. O modelo de snake balloon pode ser interpretado como uma curva poligonal fechada que se deforma sob a ação de forças internas e externas agindo sobre o modelo. O método proposto neste trabalho utiliza algumas características apresentadas pelo MDSn para desenvolver uma estratégia de solução do problema de otimização. Uma dessas características está ligada ao fato de que os contornos de telhados de edifícios no MDSn estão associados com grandes desníveis e os pontos representativos do contorno apresentam-se sobre o edifício. Assim, para dar início ao processo de extração, bastaria colocar um único ponto semente sobre o telhado. Tal ponto se expandiria, tornando-se uma curva poligonal fechada. Até que a curva encontre o limite do telhado são necessárias várias etapas... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: This work proposes a method for building convex-roof contours extraction from data of a normalized Digital Surface Model (nDSM). The contour modeling will be made by the snake balloon model, where an energy functional depending on many variables will be optimized through the Dynamic Programming algorithm (DP). The nDSM proves to be attractive in the application of building roof contour extraction, as it allows separating buildings regions from mostly other regions, especially the lowest ones. The snake balloon model can be interpreted as an polygonal closed curve that deforms under the action of internal and external forces acting on the model. The method proposed in this work uses some of the features presented by nDSM in order to develop a strategy to solve an optimization problem. One of these characteristics is related to the fact that building roof contours in a nDSM are associated with large elevation differences and representative points of the contour are presented over the building. So, to start the extraction process, it would be enough to place a single seed point on the roof. The point would expand and become a polygonal closed curve. Until the curve find the edge of the roof, several expansion stages are required... (Complete abstract click electronic access below) / Mestre

Orientador: Ronan Antonio dos Reis / Banca: Marcelo Messias / Banca: Carlos José Braga Barros / Resumo: O objetivo principal deste trabalho é estudar os conjuntos controláveis por cadeias para ações de semigrupos em fibrados. O trabalho está organizado da seguinte maneira: No capítulo 1, apresentamos algumas preliminares necessárias para o desenvolvimento deste trabalho. No capítulo 2, estudamos alguns tópicos da Teoria Geométrica de Controle, tais como, sistemas de controle, semigrupo e o grupo do sistema, acessibilidade, controlabilidade e controlabilidade aproximada para sistemas de controle. Estudamos também certas regiões do espaço de fase, ditas conjuntos controláveis para sistemas de controle, em que o sistema de controle é aproximadamente controlável. E, na sequência, estudamos os conjuntos controláveis por cadeias para sistemas de controle. Posteriormente, no capítulo 3, estudamos os conjuntos controláveis para ações de semigrupos, bem como, algumas de suas propriedades, tais como, dois conjuntos controláveis para a ação de um semigrupo, são iguais ou são disjuntos. Vimos também o conceito de conjunto de transitividade de um conjunto controlável, e algumas propriedades, tais como, é um conjunto aberto e denso no qual o semigrupo age transitivamente . Em seguida, estudamos os conjuntos controláveis por cadeias para ações de semigrupos em espaços métricos, em que mostramos alguns resultados, como por exemplo, o que caracteriza os conjuntos controláveis por cadeias como interseções de conjuntos controláveis para certos semigrupos. E, por fim, no último capítulo, estudamos o comportamento dos conjuntos controláveis por cadeias nos fibrados principais e nos seus fibrados associados, em que vimos alguns resultados, como por exemplo ... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The main objective of this work is to study the chain control sets for semigroups actions. The paper is organized as follows: First, in chapter 1, we presented some preliminaries necessary for the development of this work. Then, in chapter 2, we studied some topics of the Geometric Control Theory, such as, control sets, semigroup and system group, accessibility, controllability and approximate controllability for control sets. We also studied certain regions of phase space, called controllable system for control sets, where the control sets are approximately controllable. And, in the sequence, we studied the controllable sets by chains for control systems. Subsequently, in chapter 3, we studied the controllable sets for semigroups actions, also some of their properties, such as, two controllable sets for semigroup actions, are the same or are disjoint. We also saw the concept of transitivity set of a controllable set, and some properties, such as, is an open and dense set in which the semigroup acts transitively. After that, we studied the controllable sets by chains for semigroups actions in metric spaces, in which we show some results, for example, what characterizes ... (Complete abstract click electronic access below) / Mestre