A reactive control system is a computer system reacting to certain stimuli emitted by its environment in order to maintain it in a desired state. Distributed reactive control systems are generally composed of several processes, running in parallel on one or more computers, communicating with one another to perform the required control task. By their very nature, distributed reactive control systems are hard to design. Their distributed nature and/or the communication scheme used can introduce subtle unforeseen behaviours. When dealing with critical applications, such as plane control systems, or traffic light control systems, those unintended behaviours can have disastrous consequences. It is therefore essential, for the designer, to ensure that this does not happen. For that purpose, rigorous and systematic techniques can (and should) be applied as early as possible in the development process. In that spirit, this work aims at providing the designer with the necessary tools in order to facilitate the development and validation of such distributed reactive control systems. In particular, we show how using a dedicated language called dSL (Distributed Supervision language) can be used to ease the development process. We also study how validations techniques such as model-checking and testing can be applied in this context.

Temporal logics are a very popular family of logical languages, used to specify properties of abstracted systems. In the last few years, many extensions of temporal logics have been proposed, in order to address the need to express more than just abstract properties. In our work we study temporal logics extended by local constraints, which allow to express quantitative properties on data values from an arbitrary relational structure called the concrete domain. An example of concrete domain can be (Z, <, =), where the integers are considered as a relational structure over the binary order relation and the equality relation. Formulas of temporal logics with constraints are evaluated on data-words or data-trees, in which each node or position is labeled by a vector of data from the concrete domain. We call the constraints local because they can only compare values at a fixed distance inside such models. Several positive results regarding the satisfiability of LTL (linear temporal logic) with constraints over the integers have been established in the past years, while the corresponding results for branching time logics were only partial. In this work we prove that satisfiability of CTL* (computation tree logic) with constraints over the integers is decidable and also lift this result to ECTL*, a proper extension of CTL*. We also consider other classes of concrete domains, particularly ones that are \"tree-like\". We consider semi-linear orders, ordinal trees and trees of a fixed height, and prove decidability in this framework as well. At the same time we prove that our method cannot be applied in the case of the infinite binary tree or the infinitely branching infinite tree. We also look into extending the expressiveness of our logic adding non-local constraints, and find that this leads to undecidability of the satisfiability problem, even on very simple domains like (Z, <, =). We then find a way to restrict the power of the non-local constraints to regain decidability.

Temporal logics are a very popular family of logical languages, used to specify properties of abstracted systems. In the last few years, many extensions of temporal logics have been proposed, in order to address the need to express more than just abstract properties. In our work we study temporal logics extended by local constraints, which allow to express quantitative properties on data values from an arbitrary relational structure called the concrete domain. An example of concrete domain can be (Z, <, =), where the integers are considered as a relational structure over the binary order relation and the equality relation. Formulas of temporal logics with constraints are evaluated on data-words or data-trees, in which each node or position is labeled by a vector of data from the concrete domain. We call the constraints local because they can only compare values at a fixed distance inside such models. Several positive results regarding the satisfiability of LTL (linear temporal logic) with constraints over the integers have been established in the past years, while the corresponding results for branching time logics were only partial. In this work we prove that satisfiability of CTL* (computation tree logic) with constraints over the integers is decidable and also lift this result to ECTL*, a proper extension of CTL*. We also consider other classes of concrete domains, particularly ones that are \"tree-like\". We consider semi-linear orders, ordinal trees and trees of a fixed height, and prove decidability in this framework as well. At the same time we prove that our method cannot be applied in the case of the infinite binary tree or the infinitely branching infinite tree. We also look into extending the expressiveness of our logic adding non-local constraints, and find that this leads to undecidability of the satisfiability problem, even on very simple domains like (Z, <, =). We then find a way to restrict the power of the non-local constraints to regain decidability.

Multi-agent planning and control is an active and increasingly studied topic of research, with many practical applications, such as rescue missions, security, surveillance, and transportation. More specifically, cases that involve complex manipulator-endowed systems  deserve extra attention due to potential complex cooperative manipulation tasks and their interaction with the environment. This thesis addresses the problem of cooperative motion- and task-planning of multi-agent and multi-agent-object systems under complex specifications expressed as temporal logic formulas. We consider manipulator-endowed robotic agents that can coordinate in order to perform, among other tasks, cooperative object manipulation/transportation. Our approach is based on the integration of tools from the following areas: multi-agent systems, cooperative object manipulation, discrete abstraction design of multi-agent-object systems, and formal verification. More specifically, we divide the main problem into three different parts.The first part is devoted to the control design for the formation control of a team of rigid-bodies, motivated by its application to cooperative manipulation schemes. We propose decentralized control protocols such that desired position and orientation-based formation between neighboring agents is achieved. Moreover, inter-agent collisions and connectivity breaks are guaranteed to be avoided. In the second part, we design continuous control laws explicitly for the cooperative manipulation/transportation of an object by a team of robotic agents. Firstly, we propose robust decentralized controllers for the trajectory tracking of the object's center of mass.  Secondly, we design model predictive control-based controllers for the transportation of the object with collision and singularity constraints. In the third part, we design discrete representations of multi-agent continuous systems and synthesize hybrid controllers for the satisfaction of complex tasks expressed as temporal logic formulas. We achieve this by combining the results of the previous parts and by proposing appropriate trajectory tracking- and potential field-based continuous control laws for the transitions of the agents among the discrete states. We consider teams of unmanned aerial vehicles and mobile manipulators as well as multi-agent-object systems where the specifications of the objects are also taken into account.Numerical simulations and experimental results verify the claimed results. / <p>QC 20180219</p>

The role-based paradigm has been introduced for the design of adaptive and context sensitive software systems. Naturally, a system built on top of the paradigm is expected to thrive in dynamic environments. In consequence, reasoning services over temporal aspect are essential in such a system. To represent context-dependent domains, various extensions of Description Logics (DLs) with context are introduced and studied. We focus on the family of Contextualized Description Logics (ConDLs) that have been shown capable to represent role-based modelling languages while retaining decidability. However, reasoning problems over dynamic settings under the logics are rather unexplored.

Model checking is a well-established method for automatic system verification. Besides the extensively studied qualitative case, there is also an increasing interest in the quantitative analysis of system properties. Many important quantities can be formalised as the accumulated values of weight functions. These measures include resource usage such as energy consumption, or performance metrics such as the cost-utility ratio or reliability guarantees. Different kinds of accumulation like summation, averaging and ratios are necessary to cover the diverse spectrum of quantities. This work provides a general framework for the formalisation and verification of system models and property specifications with accumulative values. On the modelling side, we rely on weighted extensions of well-known modelling formalisms. Besides weighted transition systems, we investigate weighted probabilistic models such as Markov chains and Markov decision processes (MDPs). The weights in this sense are functions, mapping each state or transition in the model to a value, e.g., a rational vector. For the specification side, we provide a language in the form of an extension of temporal logic with new modalities that impose restrictions on the accumulated weight along path fragments. These fragments are regular and can be characterised by finite automata, so called monitors. Specifically, we extend linear temporal logic (LTL) and (probabilistic) computation tree logic (CTL) with such constraints. The framework allows variation to weaker formalisms, like non-negative or integral weight functions and bounded accumulation. We study the border of decidability of the model-checking problem for different combinations of these restrictions and give complexity results and algorithms for the decidable fragment. An implementation of the model-checking algorithms on top of the popular probabilistic model checker PRISM is provided. We also investigate several optimization techniques that can be applied to a broad range of formula patterns. The practical behaviour of the implementation and its optimization methods is put to the test by a set of scaling experiments for each model type.:1. Introduction 1.1. Goal of the Thesis 1.2. Main Contributions 1.3. Related Work 1.4. Outline 1.5. Resources 2. Preliminaries 2.1. Modeling Formalisms 2.2. Finite Automata 2.3. Propositional Logic 2.4. Temporal Logics 2.4.1. Linear Temporal Logic 2.4.2. Computation Tree Logic 2.5. Model-Checking Problems 2.5.1. Markov Decision Processes 2.5.2. Markov Chains 2.5.3. Transition Systems 2.5.4. Calculate Probabilities 3. Specifications with Weight Accumulation 3.1. Weight Constraints 3.1.1. Syntax of Weight Constraints 3.1.2. Weighted Models 3.1.3. Interpretation of Weight Constraints 3.1.4. Properties of Weight Constraints 3.2. Monitor Automata 3.2.1. Automata Classes 3.2.2. Observing WMDP Paths 3.3. Variants 3.3.1. Weight Ratios 3.3.2. Other Linear Accumulation Operators 3.3.3. Other Weight Combinations 3.3.4. Filtered Semantics 4. Linear Temporal Logic with Accumulation 4.1. Syntax and Semantics of AccLTL 4.1.1. Syntax of AccLTL 4.1.2. Semantics of AccLTL 4.1.3. Past Variant 4.1.4. Transformation of Weight Functions 4.1.5. Examples for AccLTL Formulae 4.2. Decidability Results for Accumulation LTL 4.2.1. Encoding the Post Correspondence Problem 4.2.2. Reduction of the AccLTL Model-Checking Problem 4.3. Complexity Results for Bounded Accumulation LTL 4.3.1. Transformation to Unweighted MDP and LTL 4.3.2. Reduction to LTL Model-Checking Problems 4.3.3. Algorithm 4.4. Decidability Results for Conic Accumulation LTL and RMDPs 4.4.1. Transformation to Unweighted MDP and LTL 4.4.2. Simple Weight Constraints 4.4.3. 1-dimensional Weight Constraints 4.5. NP-hard and coNP-hard Formulae for WTS and WMCs 4.5.1. Formulae for WTS 4.5.2. Formulae for WMC 4.6. Efficiently Decidable Patterns 4.7. Summary 5. Computation Tree Logic with Accumulation 5.1. Syntax and Semantics 5.1.1. Syntax and Semantics of AccCTL 5.1.2. Syntax and Semantics of AccPCTL 5.2. Decidability Results for Accumulation (P)CTL 5.3. Complexity Results for Bounded Accumulation (P)CTL 5.3.1. Weighted Markov Decision Processes 5.3.2. Weighted Markov Chains 5.3.3. Weighted Transition Systems 5.4. Decidability Results for Conic Accumulation (P)CTL and RMDPs 5.5. Summary 6. Implementation and Experiments 6.1. Implementation Details 6.1.1. Formula Expression 6.1.2. Model Construction 6.2. Optimizations 6.2.1. Single Track Method 6.2.2. Rewriting Without Until 6.2.3. Monitor Filtering 6.2.4. Detection of Optimization Methods 6.3. Scaling Experiments 6.3.1. Scaling Dimensions 6.3.2. Setting 6.3.3. Model Description 6.3.4. Input Size 6.3.5. Optimization Effects 6.3.6. Filtering 7. Conclusions 7.1. Summary 7.2. Outlook and Future Work A. Bibliography B. Material for the experiments B.1. Environment for the Experiments B.1.1. Container Image B.1.2. Model Definitions

Ontology-mediated query answering is a popular paradigm for enriching answers to user queries with background knowledge. For querying the absence of information, however, there exist only few ontology-based approaches. Moreover, these proposals conflate the closed-domain and closed-world assumption, and therefore are not suited to deal with the anonymous objects that are common in ontological reasoning. Many real-world applications, like processing electronic health records (EHRs), also contain a temporal dimension, and require efficient reasoning algorithms. Moreover, since medical data is not recorded on a regular basis, reasoners must deal with sparse data with potentially large temporal gaps. Our contribution consists of three main parts: Firstly, we introduce a new closed-world semantics for answering conjunctive queries with negation over ontologies formulated in the description logic ELH⊥, which is based on the minimal universal model. We propose a rewriting strategy for dealing with negated query atoms, which shows that query answering is possible in polynomial time in data complexity. Secondly, we introduce a new temporal variant of ELH⊥ that features a convexity operator. We extend this minimal-world semantics for answering metric temporal conjunctive queries with negation over the logic and obtain similar rewritability and complexity results. Thirdly, apart from the theoretical results, we evaluate minimal-world semantics in practice by selecting patients, based their EHRs, that match given criteria.

Le développement de nouveaux formalismes logiques est au cœur de nombreuses problématiques de méthodes formelles. Ces formalismes doivent répondre à la fois à des impératifs de modélisation (ils doivent permettre de décrire certains systèmes) et de calcul (ils doivent fournir des méthodes de calcul correctes et complètes). Dans ce contexte, nous nous intéressons aux logiques de ressources, en particulier les logiques BI et BBI qui traitent du partage et de la séparation de ressources et qui ont conduit aux diverses logiques de séparation dont les applications à la vérification de programmes se sont développées fortement ces dernières années. Nous proposons dans cette thèse d’étudier, à partir des logiques BI et BBI, des logiques de séparation modales et épistémiques en se focalisant sur leurs capacités de modélisation et leur expressivité mais aussi les nouveaux calculs de preuve pour ces logiques. Une première étude a porté sur la modélisation de propriétés dynamiques de ressources au travers d’une nouvelle logique LTBI, qui est une logique de séparation temporelle, fondée sur la logique BI et des modalités temporelles. Cette logique offre notamment des perspectives intéressantes de modélisation temporelle branchante, permettant par exemple de caractériser les processus multi-thread. Une étude complémentaire a porté sur la modélisation de l’accès par des agents à des propriétés sous conditions de posséder certaines ressources, au travers d’une nouvelle logique ERL, qui est une logique de séparation épistémique, fondée sur la logique BBI et des modalités épistémiques. Cette logique permet de nombreuses modélisations de systèmes de contrôle d’accès. En vue d’étendre l’expressivité de telles logiques de séparation, comme la logique BBI et ses variantes, une étude sur l’internalisation des symboles de ressources dans la syntaxe de la logique a été développée au travers des nouvelles logiques HRL et HBBI (version hybride de BBI). L’internalisation permet à la fois d’étendre l’expressivité des logiques et d’axiomatiser la logique BBI et certaines de ses variantes. Outre la conception de ces logiques, l’étude de leur sémantique et aussi de leurs capacités de modélisation, une partie de cette thèse a été consacrée à la définition de calculs de preuve, ici de tableaux, pour ces nouvelles logiques ainsi qu’à leurs preuves de correction et de complétude / The design of new logical formalisms is at the heart of several problems in formal methods. Those formalisms must respond to requirements both concerning modelling (they must be able to describe certain systems) and computing (they must provide complete and sound calculus methods). In this context, we look at resource logics, and in particular BI and BBI logics, that deal with the separation and sharing of resources and have led to several separation logics whose applications to software verification have been widely developped recently. We propose in this thesis, starting from BI and BBI logics, to study some modal and epistemic separation logics by focusing on their modelling capacities and their expresiveness, as well as on the new proof calculi for those logics. A first study deals with the modelling of dynamic resource properties through new logic LTBI, which is a temporal separation logic, based on BI logic and temporal modalities. This logic notably offers interesting perspectives in temporal branching modelling, allowing for instance to characterize multi-thread processes. A complementary study concerns the modelling of access by agents to properties under the conditions of posessing some resources, through a new logic ERL, which is an epistemic separation logic, based on BBI logic and epistemic modalities. This logic allows many modellings of access control systems. In order to extend the expressivity of such separation logics, like BBI logic and its variants, a study on the internalization of resources symbols in the logic’s syntax has been developed through the new logics HRL and HBBI (hybrid version of BBI). Internalization allows both the extension of the expressivity of logics and the axiomatisation of BBI logic and some of its variants. In addition to the conception of those logics, the study of their semantics and their modelling capacities, a part of this thesis is dedicated to the definition of proof calculs, here tableaux calculus, for those new logics, as well as their proof of soundness and completeness

A reactive control system is a computer system reacting to certain stimuli emitted by its environment in order to maintain it in a desired state. Distributed reactive control systems are generally composed of several processes, running in parallel on one or more computers, communicating with one another to perform the required control task. By their very nature, distributed reactive control systems are hard to design. Their distributed nature and/or the communication scheme used can introduce subtle unforeseen behaviours. When dealing with critical applications, such as plane control systems, or traffic light control systems, those unintended behaviours can have disastrous consequences. It is therefore essential, for the designer, to ensure that this does not happen. For that purpose, rigorous and systematic techniques can (and should) be applied as early as possible in the development process. In that spirit, this work aims at providing the designer with the necessary tools in order to facilitate the development and validation of such distributed reactive control systems. In particular, we show how using a dedicated language called dSL (Distributed Supervision language) can be used to ease the development process. We also study how validations techniques such as model-checking and testing can be applied in this context. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Information and communication systems enter an increasing number of areas of daily lives. Our reliance and dependence on the functioning of such systems is rapidly growing together with the costs and the impact of system failures. At the same time the complexity of hardware and software systems extends to new limits as modern hardware architectures become more and more parallel, dynamic and heterogenous. These trends demand for a closer integration of formal methods and system engineering to show the correctness of complex systems within the design phase of large projects. The goal of this thesis is to introduce a formal holistic approach for modeling, analysis and synthesis of parallel systems that potentially addresses complex system behavior at any layer of the hardware/software stack. Due to the complexity of modern hardware and software systems, we aim to have a hierarchical modeling framework that allows to specify the behavior of a parallel system at various levels of abstraction and that facilitates designing complex systems in an iterative refinement procedure, in which more detailed behavior is added successively to the system description. In this context, the major challenge is to provide modeling formalisms that are expressive enough to address all of the above issues and are at the same time amenable to the application of formal methods for proving that the system behavior conforms to its specification. In particular, we are interested in specification formalisms that allow to apply formal verification techniques such that the underlying model checking problems are still decidable within reasonable time and space bounds. The presented work relies on an exogenous modeling approach that allows a clear separation of coordination and computation and provides an operational semantic model where formal methods such as model checking are well suited and applicable. The channel-based exogenous coordination language Reo is used as modeling formalism as it supports hierarchical modeling in an iterative top-down refinement procedure. It facilitates reusability, exchangeability, and heterogeneity of components and forms the basis to apply formal verification methods. At the same time Reo has a clear formal semantics based on automata, which serve as foundation to apply formal methods such as model checking. In this thesis new modeling languages are presented that allow specifying complex systems in terms of Reo and automata models which yield the basis for a holistic approach on modeling, verification and synthesis of parallel systems. The second main contribution of this thesis are tailored branching-time and alternating time temporal logics as well as corresponding model checking algorithms. The thesis includes results on the theoretical complexity of the underlying model checking problems as well as practical results. For the latter the presented approach has been implemented in the symbolic verification tool set Vereofy. The implementation within Vereofy and evaluation of the branching-time and alternating-time model checker is the third main contribution of this thesis.