The Parameterised Model Checking Problem asks whether an implementation Impl(t) satisfies a specification Spec(t) for all instantiations of parameter t. In general, t can determine numerous entities: the number of processes used in a network, the type of data, the capacities of buffers, etc. The main theme of this thesis is automation of uniform verification of a subclass of PMCP with the parameter of the first kind, using techniques based on counter abstraction. Counter abstraction works by counting how many, rather than which, node processes are in a given state: for nodes with k local states, an abstract state (c(1), ..., c(k)) models a global state where c(i) processes are in the i-th state. We then use a threshold function z to cap the values of each counter. If for some i, counter c(i) reaches its threshold, z(i) , then this is interpreted as there being z(i) or more nodes in the i-th state. The addition of thresholds makes abstract models independent of the instantiation of the parameter. We adapt standard counter abstraction techniques to concurrent reactive systems modelled using the CSP process algebra. We demonstrate how to produce abstract models of systems that do not use node identifiers (i.e. where all nodes are indistinguishable). Every such abstraction is, by construction, refined by all instantiations of the implementation. If the abstract model satisfies the specification, then a positive answer to the particular uniform verification problem can be deduced. We show that by adding node identifiers we make the uniform verification problem undecidable. We demonstrate a sound abstraction method that extends standard counter abstraction techniques to systems that make full use of node identifiers (in specifications and implementations). However, on its own, the method is not enough to give the answer to verification problems for all parameter instantiations. This issue has led us to the development of a type reduction theory, which, for a given verification problem, establishes a function phi that maps all (sufficiently large) instantiations T of the parameter to some fixed type T and allows us to deduce that if Spec(T) is refined by phi(Impl(T)), then Spec(T) is refined by Impl(T). We can then combine this with our extended counter abstraction techniques and conclude that if the abstract model satisfies Spec(T), then the answer to the uniform verification problem is positive. We develop a symbolic operational semantics for CSP processes that satisfy certain normality requirements and we provide a set of translation rules that allow us to concretise symbolic transition graphs. The type reduction theory relies heavily on these results. One of the main advantages of our symbolic operational semantics and the type reduction theory is their generality, which makes them applicable in other settings and allows the theory to be combined with abstraction methods other than those used in this thesis. Finally, we present TomCAT, a tool that automates the construction of counter abstraction models and we demonstrate how our results apply in practice.

Model checking is an automatic formal verification technique for establishing correctness of systems. It has been widely used in industry for analysing and verifying complex safety-critical systems in application domains such as avionics, medicine and computer security, where manual testing is infeasible and even minor errors could have dire consequences. In our increasingly parallelised world, concurrency has become pivotal and seamlessly woven within programming paradigms, however, extremely challenging when it comes to modelling and establishing correctness of intended behaviour. Tools for model checking concurrent systems face severe limitations due to scalability problems arising from the need to examine all possible interleavings (schedules) of executions of parallel components. Moreover, concurrency poses additional challenges to model checking, giving rise to phenomena such as nondeterminism, deadlock, livelock, etc. In this thesis we focus on adapting and developing novel model-checking techniques for concurrent systems in the setting of the process algebra CSP and its primary model checker FDR. CSP allows for a compact modelling and precise analysis of event-based concurrency, grounded on synchronous message passing as a fundamental mechanism of inter-component communication. In particular, we investigate techniques based on symbolic model checking, static analysis and abstraction, all of them exploiting the compositionality inherent in CSP and targeting to increase the scale of systems that can be tractably analysed. Firstly, we investigate symbolic model-checking techniques based on Boolean satisfiability (SAT), which we adapt for the traces model of CSP. We tailor bounded model checking (BMC), that can be used for bug detection, and temporal k-induction, which aims at establishing inductiveness of properties and is capable of both bug finding and establishing the correctness of systems. Secondly, we propose a static analysis framework for establishing livelock freedom of CSP processes, with lessons for other concurrent formalisms. As opposed to traditional exhaustive state-space exploration, our framework employs a system of rules on the syntax of a process to calculate a sound approximation of its fair/co-fair sets of events. The rules either safely classify a process as livelock-free or report inconclusiveness, thereby trading accuracy for speed. Finally, we develop a series of abstraction/refinement schemes for the traces, stable-failures and failures-divergences models of CSP and embed them into a fully automated and compositional CEGAR framework. For each of those techniques we present an implementation and an experimental evaluation on a set of CSP benchmarks.

Cette thèse porte sur la vérification des automates temporisés, un modèle bien établi pour les systèmes temps-réels. La thèse est constituée de trois parties. La première est dédiée à la déterminisation des automates temporisés, problème qui n'a pas de solution en général. Nous proposons une méthode approchée (sur-approximation, sous-approximation, mélange des deux) fondée sur la construction d'un jeu de sûreté. Cette méthode améliore les approches existantes en combinant leurs avantages respectifs. Nous appliquons ensuite cette méthode de déterminisation à la génération automatique de tests de conformité. Dans la seconde partie, nous prenons en compte des aspects quantitatifs des systèmes temps-réel grâce à une notion de fréquence des états acceptants dans une exécution d'un automate temporisé. Plus précisément, la fréquence d'une exécution est la proportion de temps passée dans les états acceptants. Nous intéressons alors à l'ensemble des fréquences des exécutions d'un automate temporisé pour étudier, par exemple, le vide de langages seuils. Nous montrons ainsi que les bornes de l'ensemble des fréquences sont calculables pour deux classes d'automates temporisés. D'une part, les bornes peuvent être calculées en espace logarithmique par une procédure non-déterministe dans les automates temporisés à une horloge. D'autre part, elles peuvent être calculées en espace polynomial dans les automates temporisés à plusieurs horloges ne contenant pas de cycles forçant la convergence d'horloges. Finalement, nous étudions le problème de l'accessibilité des états acceptants dans des réseaux d'automates temporisés qui communiquent via des files FIFO. Nous considérons tout d'abord des automates temporisés à temps discret, et caractérisons les topologies de réseaux pour lesquelles l'accessibilité est décidable. Cette caractérisation est ensuite étendue aux automates temporisés à temps continu. / This thesis is about verification of timed automata, a well-established model for real time systems. The document is structured in three parts. The first part is dedicated to the determinization of timed automata, a problem which has no solution in general. We propose an approximate (over-approximation/under-approximation/mix) method based on the construction of a safety game. This method improves both existing approaches by combining their respective advantages. Then, we apply this determinization approach to the generation of conformance tests. In the second part, we take into account quantitative aspects of real time systems thanks to a notion of frequency of accepting states along executions of timed automata. More precisely, the frequency of a run is the proportion of time elapsed in accepting states. Then, we study the set of frequencies of runs of a timed automaton in order to decide, for example, the emptiness of threshold languages. We thus prove that the bounds of the set of frequencies are computable for two classes of timed automata. On the one hand, we prove that bounds are computable in logarithmic space by a non-deterministic procedure in one-clock timed automata. On the other hand, they can be computed in polynomial space in timed automata with several clocks, but having no cycle that forces the convergence between clocks. Finally, we study the reachability problem in networks of timed automata communicating through FIFO channels. We first consider dicrete timed automata, and characterize topologies of networks for which reachability is decidable. Then, this characterization is extended to dense-time automata.

Nesse trabalho, a incidência da prisão para além de seus limites físicos e institucionais é problematizada a partir da exploração e confrontação de dois contextos sociais distintos: a Catalunha e São Paulo. Os vasos comunicantes que conectam a prisão a outros territórios sociais, bem como as experiências de diversos agentes que fazem a mediação entre o mundo prisional e a sociedade mais ampla, são questões abordadas através de uma perspectiva analítico-descritiva, visando evidenciar a produção de um multifacetado campo social estruturado ao redor e através das instituições prisionais. Explorando diferentes trajetórias que se conformam nesse campo é possível problematizar algumas das circunstâncias do processo de massificação do encarceramento, assim como outras importantes alterações recentes no dispositivo carcerário contemporâneo. / This work intends to problematize the impacts of prison beyond its physical and institutional limits. Such aim is achieved through exploration and confrontation of two different social contexts: Catalonia and São Paulo. The communicating vessels, which connect jail to other social territories, and the experience of several agents, that provide mediation between prison and the rest of society, are questions treated through an analytical-descriptive perspective, intending to show up the production of a multifaceted social field that is structured around and through prison institutions. Exploring different paths in this field, it is possible to problematize some circumstances of mass imprisonment process, as well as recent changes in the penal contemporary mechanism.

La thèse aborde le problème de la dissémination des informations liées au produit tout au long de son cycle de vie, par l’exploitation du concept de matière communicante. L’objectif général est de stocker dans la matière communicante ses caractéristiques initiales mais aussi l’évolution de ses propriétés durant son usage, en évitant de les perdre lors par exemple d’une transformation ou d’une destruction d’une partie du matériau. Dans le cadre de cette thèse, ce principe est appliqué dans le domaine des préfabriqués en béton, où des nœuds de réseaux de capteurs sans fil sont intégrés dans le béton. Ces nœuds sont alors utilisés pour stocker des informations relatives au cycle de vie du préfabriqué et à sa surveillance sur la phase d’usage. Un nouveau protocole de communication, nommé USEE, a été proposé et permet de diffuser uniformément les informations dans la matière en considérant qu’elles n’ont pas toutes la même importance. Le protocole USEE évite notamment la saturation rapide des mémoires des nœuds de façon à pouvoir stocker un maximum d’informations différentes. Ensuite, un protocole de lecture, intitulé RaWPG, a été développé. Il est adapté à la récupération d’informations uniformément réparties et consomme peu d’énergie. Ces deux protocoles ont été implémentés dans le simulateur réseau Castalia/OMNeT++ et ont permis de montrer leur intérêt par rapport au contexte applicatif mais aussi par rapport à d’autres protocoles similaires de la littérature / A new Internet of Things area is coming with communicating materials, which are able to provide diverse functionalities to users all along the product lifecycle. As example, it can track its own evolution which leads to gather helpful information. This new paradigm is fulfilled via the integration of specific electronic components into the product material. In this thesis, ultra-small wireless sensor nodes are used for concrete precast field. Indeed, storage of lifecycle information and data dissemination in communicating materials are very important issues. Therefore, this thesis provides a new protocol (USEE) for storing data by a systematic dissemination through the integrated sensor nodes. It guarantees that information could be retrieved in each piece of the concrete by intelligently managing data replication among each neighborhood of the sensor network. The protocol considers in the same set uniformity storage in the whole network, the data importance level, and the resource constraints of sensor nodes. Then, another new data retrieval protocol (RaWPG) is developed to extract the stored information. Castalia/OMNeT++ simulator is used to evaluate the performances of the proposed protocols

Nesse trabalho, a incidência da prisão para além de seus limites físicos e institucionais é problematizada a partir da exploração e confrontação de dois contextos sociais distintos: a Catalunha e São Paulo. Os vasos comunicantes que conectam a prisão a outros territórios sociais, bem como as experiências de diversos agentes que fazem a mediação entre o mundo prisional e a sociedade mais ampla, são questões abordadas através de uma perspectiva analítico-descritiva, visando evidenciar a produção de um multifacetado campo social estruturado ao redor e através das instituições prisionais. Explorando diferentes trajetórias que se conformam nesse campo é possível problematizar algumas das circunstâncias do processo de massificação do encarceramento, assim como outras importantes alterações recentes no dispositivo carcerário contemporâneo. / This work intends to problematize the impacts of prison beyond its physical and institutional limits. Such aim is achieved through exploration and confrontation of two different social contexts: Catalonia and São Paulo. The communicating vessels, which connect jail to other social territories, and the experience of several agents, that provide mediation between prison and the rest of society, are questions treated through an analytical-descriptive perspective, intending to show up the production of a multifaceted social field that is structured around and through prison institutions. Exploring different paths in this field, it is possible to problematize some circumstances of mass imprisonment process, as well as recent changes in the penal contemporary mechanism.

First-line supervisors in U.S. retail organizations are unable to resolve nearly 34% of typical daily customer problems for their organizations. The purpose of this single case study was to explore the strategies retail supermarket managers have used to improve 1st line supervisor problem solving abilities within a retail supermarket company in Winston-Salem, North Carolina. The conceptual framework for this study was the skills-based leadership model. Data were collected from semistructured interviews with 4 retail store manager participants with a successful record of improving first-line supervisor problem solving abilities. Additionally, the review of company documents including training guides, training checklists, job descriptions, annual goal setting templates, and company website postings supplemented the semistructured interviews. Data analysis entailed coding, conceptualizing concepts and ideas, identifying themes, and member-checking to ensure the trustworthiness of interpretations. Based on the methodological triangulation of the data collected, 4 themes emerged after the data analysis: (a) the importance of communicating expectations with first-line supervisors, (b) coaching first-line supervisors on performance, (c) first-line supervisor learning and development, and (d) measuring first-line supervisor performance. Findings from this study may contribute to social change by providing insights and strategies that retail store managers can use to improve 1st-line supervisor problem-solving abilities. Improvement in problem-solving abilities may improve employees' lives, communities, and organizational performance.

In this thesis, research efforts are dedicated towards the development of practical adaptable techniques to be used in Smart Homes and Buildings, with the aim to improve energy management and conservation, while enhancing the learning capabilities of Programmable Communicating Thermostats (PCT) – “transforming” them into smart adaptable devices, i.e., “Smart Thermostats”. An Adaptable Hybrid Intelligent System utilizing Wireless Sensor Network (WSN) and Artificial Intelligence (AI) techniques is presented, based on which, a novel Adaptive Learning System (ALS) model utilizing WSN, a rule-based system and Adaptive Resonance Theory (ART) concepts is proposed. The main goal of the ALS is to adapt to the occupant’s pattern and/or schedule changes by providing comfort, while not ignoring the energy conservation aspect. The proposed ALS analytical model is a technique which enables PCTs to learn and adapt to user input pattern changes and/or other parameters of interest. A new algorithm for finding the global maximum in a predefined interval within a two dimensional space is proposed. The proposed algorithm is a synergy of reward/punish concepts from the reinforcement learning (RL) and agent-based technique, for use in small-scale embedded systems with limited memory and/or processing power, such as the wireless sensor/actuator nodes. An application is implemented to observe the algorithm at work and to demonstrate its main features. It was observed that the “RL and Agent-based Search”, versus the “RL only” technique, yielded better performance results with respect to the number of iterations and function evaluations needed to find the global maximum. Furthermore, a “House Simulator” is developed as a tool to simulate house heating/cooling systems and to assist in the practical implementation of the ALS model under different scenarios. The main building blocks of the simulator are the “House Simulator”, the “Smart Thermostat”, and a placeholder for the “Adaptive Learning Models”. As a result, a novel adaptive learning algorithm, “Observe, Learn and Adapt” (OLA) is proposed and demonstrated, reflecting the main features of the ALS model. Its evaluation is achieved with the aid of the “House Simulator”. OLA, with the use of sensors and the application of the ALS model learning technique, captures the essence of an actual PCT reflecting a smart and adaptable device. The experimental performance results indicate adaptability and potential energy savings of the single in comparison to the zone controlled scenarios with the OLA capabilities being enabled.

In this thesis, research efforts are dedicated towards the development of practical adaptable techniques to be used in Smart Homes and Buildings, with the aim to improve energy management and conservation, while enhancing the learning capabilities of Programmable Communicating Thermostats (PCT) – “transforming” them into smart adaptable devices, i.e., “Smart Thermostats”. An Adaptable Hybrid Intelligent System utilizing Wireless Sensor Network (WSN) and Artificial Intelligence (AI) techniques is presented, based on which, a novel Adaptive Learning System (ALS) model utilizing WSN, a rule-based system and Adaptive Resonance Theory (ART) concepts is proposed. The main goal of the ALS is to adapt to the occupant’s pattern and/or schedule changes by providing comfort, while not ignoring the energy conservation aspect. The proposed ALS analytical model is a technique which enables PCTs to learn and adapt to user input pattern changes and/or other parameters of interest. A new algorithm for finding the global maximum in a predefined interval within a two dimensional space is proposed. The proposed algorithm is a synergy of reward/punish concepts from the reinforcement learning (RL) and agent-based technique, for use in small-scale embedded systems with limited memory and/or processing power, such as the wireless sensor/actuator nodes. An application is implemented to observe the algorithm at work and to demonstrate its main features. It was observed that the “RL and Agent-based Search”, versus the “RL only” technique, yielded better performance results with respect to the number of iterations and function evaluations needed to find the global maximum. Furthermore, a “House Simulator” is developed as a tool to simulate house heating/cooling systems and to assist in the practical implementation of the ALS model under different scenarios. The main building blocks of the simulator are the “House Simulator”, the “Smart Thermostat”, and a placeholder for the “Adaptive Learning Models”. As a result, a novel adaptive learning algorithm, “Observe, Learn and Adapt” (OLA) is proposed and demonstrated, reflecting the main features of the ALS model. Its evaluation is achieved with the aid of the “House Simulator”. OLA, with the use of sensors and the application of the ALS model learning technique, captures the essence of an actual PCT reflecting a smart and adaptable device. The experimental performance results indicate adaptability and potential energy savings of the single in comparison to the zone controlled scenarios with the OLA capabilities being enabled.

No description available.