La théorie néo institutionnelle permet de penser les outils de gestion dans la société et dans l'interaction avec les acteurs des organisations. Ce travail montre la complexité des instruments de gestion et les envisage tour à tour comme : des éléments symboliques neutres à l'activité de l'organisation adoptés par souci de légitimité et diffusés par des mécanismes isomorphiques, des objets rhétoriques porteurs de langage et de catégorisations et transformés par les acteurs organisationnels, des artefacts transportant des logiques institutionnelles multiples naissant dans le champ organisationnel. Cette thèse pose l'existence d'un nouveau rôle pour les outils de gestion, celui de régulateur des contradictions entre logiques institutionnelles. Sur le plan empirique, avec une méthodologie qualitative mêlant approches longitudinales multi niveaux et recherche intervention, les logiques institutionnelles du champ de la finance solidaire en France et de deux organisations de capital-risque solidaire sont analysées. Les outils de gestion de ces deux organisations sont étudiés. Les outils créés avec le chercheur, les pactes d'actionnaires et les chartes, véhiculent les logiques institutionnelles des fonds. Le changement des pactes d'actionnaire et les comités d'investissement permettent de révéler que les outils de gestion gèrent les tensions entre logiques institutionnelle en les éliminant, les compartimentant ou les intégrant. Les résultats de cette étude permettent de discuter le degré d'incompatibilité entre les logiques en fonction de leur perméabilité, des métiers représentés dans les organisations et des pratiques considérées. Ils autorisent également une formalisation des liens entre outils de gestion et logiques institutionnelles ainsi qu'entre logiques institutionnelles présentes dans l'organisation et rôle des outils de gestion. Enfin, un process socio technique d'hybridation de logiques institutionnelles est proposé. / Institutional theory describes management artifacts as embedded in the society and in interactions with organizational actors. This work is aiming to grasp the complexity of management apparatus and analyzes it as: first, symbolical element neutral for the organizational activity, adopted for legitimacy and diffused by isomorphic mechanisms; then, rhetorical objects generating languages and categorizations, transformed by actors; finally, as artifacts carrying multiple institutional logics. This thesis postulates that management artifacts can also regulate contradictions between institutional logics. A qualitative methodology combining longitudinal multi-level approaches and research action, is revealing the institutional logics of the organizational field of interdependent finance and of two interdependent venture capital funds. The management apparatus of these funds is studied. New management tools created during the research action, charters and shareholders' agreements are carrying venture organizations' institutional logics. A change in a shareholders' agreement and the management system of the investment decision-making process in a venture fund, named investment committees, divulge that management apparatus handle tensions between institutional logics by eliminating one of them, compartmenting or integrating them. The results of this study acknowledge different degrees in the contradictions between institutional logics related to their permeability, the professions represented in the organization, the practices looked at. They contribute also to formalize links between management artifacts and institutional logics. We lastly propose a model combining two processes that explicate how multiple logics can blend and how tensions can be handled.

Cette thèse se situe dans le domaine des modèles de l’argumentation en intelligence artificielle. Ces modèles constituent des outils très populaires pour l’étude de raisonnements en présence d’incohérences dans les bases de connaissances et lors de la négociation entre agents et la prise de décision. Un modèle argumentatif est un processus interactionnel principalement basé sur la construction d’arguments et de contre-arguments, l’étude des relations entre ces différents arguments et la mise en place de critères permettant de déterminer le statut de chaque argument afin de sélectionner les arguments (les plus) acceptables.Dans ce cadre, ce travail a porté sur l’étude d’un système particulier : le système d’argumentation déductif. Un argument est alors entendu comme un couple prémisses-conclusion tel que la conclusion soit une formule qui puisse être déduite des prémisses. Nous y avons traité plusieurs questions. Tout d’abord, partant du constat que le raisonnement par l’absurde est valide en logique propositionnelle classique, nous proposons une méthode de génération d’arguments en faveur d’une proposition donnée. Cette approche s’étend au calcul des undercuts canoniques, arguments identifiés comme représentant tous les contre-arguments. Contrairement aux autres approches proposées dans la littérature, notre technique est complète au sens où elle permet de générer, modulo une possible explosion combinatoire, tous les arguments relatifs à une formule logique quelconque. Ensuite, nous avons proposé un cadre d’argumentation en logique conditionnelle. Les logiques conditionnelles sont souvent considérées comme étant tout particulièrement adaptées à la formalisation de raisonnements de nature hypothétique. Leur connecteur conditionnel est en effet souvent plus proche de l’intuition que l’on peut avoir de l’implication que ne l’est l’implication matérielle de la logique propositionnelle classique. Ceci nous permet de proposer un concept de contrariété conditionnelle qui couvre à la fois les situations de conflits logiques fondés sur l’incohérence et une forme particulière de conflit qui ne se traduit pas naturellement par un conflit basé sur l’incohérence : quand un agent affirme une règle de type Si alors, une seconde règle qui peut en être déduite et qui impose la satisfaction de prémisses supplémentaires peut apparaître conflictuelle. Nous étudions alors sur cette base les principaux éléments d’une théorie de l’argumentation dans une logique conditionnelle. Enfin, le dernier point étudié dans ce travail concerne le raisonnement au sujet de ressources consommables, dans un cadre où les formules logiques sont elles mêmes consommées dans le processus déductif. Nous proposons une logique, simple et proche du langage et des principes de la logique propositionnelle classique, permettant le raisonnement à partir de ressources consommables et de quantité bornée. Nous y revisitons également les principaux éléments d’une théorie logique de l’argumentation. / This thesis focus on the field of argumentation models in artificial intelligence. These models form very popular tools to study reasoning under inconsistency in knowledge bases, negotiation between agents, and also in decision making. An argumentative model is an interactional process mainly based on the construction of arguments and counter-arguments, then studying the relations between these arguments, and finally the introduction of some criteria to identifying the status of each argument in order to select the (most) acceptable of them.In this context, this work was dealt with the study of a particular system: the deductive argumentation framework. An argument is then understood as a pair premises-conclusion such that conclusion is a logical formula entailed by premises, a non-ordered collection of logical formulas. We have addressed several issues. First of all, on the basis that reductio ad absurdum is valid in classical propositional logic, we propose a method to compute arguments for a given statement. This approach is extended to generate canonical undercuts, arguments identified as the representative of all counter-arguments. Contrary to the other approaches proposed in the literature, our technique is complete in the sense that all arguments relative to the statement at hand are generated and so are all relevant counter-arguments. Secondly, we proposed a logic based argumentation in conditional logic. Conditional logic is often regarded as an appealing setting for the formalization of hypothetical reasoning. Their conditional connective is often regarded as a very suitable connective to encode many implicative reasoning patterns real-life and attempts to avoid some pitfalls of material implication of propositional logic. This allows us to put in light and encompass a concept of conditional contrariety thats covers both usual inconsistency-based conflict and a specific form of conflict that often occurs in real-life argumentation: i.e., when an agent asserts an If then rule, it can be argued that the satisfaction of additional conditions are required for the conclusion of a rule to hold. Then, in that case we study the main foundational concepts of an argumentation theory in conditional logic. Finally, the last point investigated in this work concerns the reasoning about bounded resources, within a framework in which logical formulas are themselves consumed in the deductive process. First, a simple variant of Boolean logic is introduced, allowing us to reason about consuming resources. Then, the main concepts of logic-based argumentation are revisited in this framework.

With the growing popularity of the Web Ontology Language (OWL) as a logic-based ontology language, as well as advancements in the language itself, the need for more sophisticated and up-to-date ontology engineering services increases as well. While, for instance, there is active focus on new reasoners and optimisations, other services fall short of advancing at the same rate (it suffices to compare the number of freely-available reasoners with ontology editors). In particular, very little is understood about how ontologies evolve over time, and how reasoners’ performance varies as the input changes. Given the evolving nature of ontologies, detecting and presenting changes (via a so-called diff) between them is an essential engineering service, especially for version control systems or to support change analysis. In this thesis we address the diff problem for description logic (DL) based ontologies, specifically OWL 2 DL ontologies based on the SROIQ DL. The outcomes are novel algorithms employing both syntactic and semantic techniques to, firstly, detect axiom changes, and what terms had their meaning affected between ontologies, secondly, categorise their impact (for example, determining that an axiom is a stronger version of another), and finally, align changes appropriately, i.e., align source and target of axiom changes (so the stronger axiom with the weaker one, from our example), and axioms with the terms they affect. Subsequently, we present a theory of reasoner performance heterogeneity, based on field observations related to reasoner performance variability phenomena. Our hypothesis is that there exist two kinds of performance behaviour: an ontology/reasoner combination can be performance-homogeneous or performance-heterogeneous. Finally, we verify that performance-heterogeneous reasoner/ontology combinations contain small, performance-degrading sets of axioms, which we call hot spots. We devise a performance hot spot finding technique, and show that hot spots provide a promising basis for engineering efficient reasoners.

Interroger des bases de connaissances avec des requêtes conjonctives a été une préoccupation majeure de la recherche récente en logique de description. Une question importante qui se pose dans ce contexte est la gestion de données incohérentes avec l'ontologie. En effet, une théorie logique incohérente impliquant toute formule sous la sémantique classique, l'utilisation de sémantiques tolérantes aux incohérences est nécessaire pour obtenir des réponses pertinentes. Le but de cette thèse est de développer des méthodes pour gérer des bases de connaissances incohérentes en utilisant trois sémantiques naturelles (AR, IAR et brave) proposées dans la littérature et qui reposent sur la notion de réparation, définie comme un sous-ensemble maximal des données cohérent avec l'ontologie. Nous utilisons ces trois sémantiques conjointement pour identifier les réponses associées à différents niveaux de confiance. En plus de développer des algorithmes efficaces pour interroger des bases de connaissances DL-Lite incohérentes, nous abordons trois problèmes : (i) l'explication des résultats des requêtes, pour aider l'utilisateur à comprendre pourquoi une réponse est (ou n'est pas) obtenue sous une des trois sémantiques, (ii) la réparation des données guidée par les requêtes, pour améliorer la qualité des données en capitalisant sur les retours des utilisateurs sur les résultats de la requête, et (iii) la définition de variantes des sémantiques à l'aide de réparations préférées pour prendre en compte la fiabilité des données. Pour chacune de ces trois questions, nous développons un cadre formel, analysons la complexité des problèmes de raisonnement associés, et proposons et mettons en œuvre des algorithmes, qui sont étudiés empiriquement sur un jeu de bases de connaissance DL-Lite incohérentes que nous avons construit. Nos résultats indiquent que même si les problèmes à traiter sont théoriquement durs, ils peuvent souvent être résolus efficacement dans la pratique en utilisant des approximations et des fonctionnalités des SAT solveurs modernes. / The problem of querying description logic knowledge bases using database-style queries (in particular, conjunctive queries) has been a major focus of recent description logic research. An important issue that arises in this context is how to handle the case in which the data is inconsistent with the ontology. Indeed, since in classical logic an inconsistent logical theory implies every formula, inconsistency-tolerant semantics are needed to obtain meaningful answers. This thesis aims to develop methods for dealing with inconsistent description logic knowledge bases using three natural semantics (AR, IAR, and brave) previously proposed in the literature and that rely on the notion of a repair, which is an inclusion-maximal subset of the data consistent with the ontology. In our framework, these three semantics are used conjointly to identify answers with different levels of confidence. In addition to developing efficient algorithms for query answering over inconsistent DL-Lite knowledge bases, we address three problems that should support the adoption of this framework: (i) query result explanation, to help the user to understand why a given answer was (not) obtained under one of the three semantics, (ii) query-driven repairing, to exploit user feedback about errors or omissions in the query results to improve the data quality, and (iii) preferred repair semantics, to take into account the reliability of the data. For each of these three topics, we developed a formal framework, analyzed the complexity of the relevant reasoning problems, and proposed and implemented algorithms, which we empirically studied over an inconsistent DL-Lite benchmark we built. Our results indicate that even if the problems related to dealing with inconsistent DL-Lite knowledge bases are theoretically hard, they can often be solved efficiently in practice by using tractable approximations and features of modern SAT solvers.

Dans un contexte de transformation du travail et d’augmentation de la précarité, cette thèse aide à comprendre comment de nouvelles formes de travail émergent, se développent et parviennent à répondre aux besoins et aspirations sociales en matière de travail. Cette étude s’intéresse plus particulièrement aux dynamiques d’innovation sociale qui s’appuient sur les principes de l’économie sociale et solidaire. Elle repose sur une analyse néo-institutionnaliste, processuelle et multi-niveau des Coopératives d’Activité et d’Emploi, une forme organisationnelle hybride alliant les logiques institutionnelles de l’entrepreneuriat, du salariat et de la coopération. Elle a permis (1) de mieux comprendre les interactions entre l’innovation sociale et son contexte ; (2) de mettre en lumière une nouvelle forme de stratégie agissant sur les logiques institutionnelles pour gérer les tensions inhérentes à la forme organisationnelle hybride ; et (3) d’expliquer comment une organisation hybride peut permettre aux personnes de (re)donner du sens au travail. / In a context of labor transformation and increased work precariousness, this thesis explains how new forms of work emerge, develop and respond to social needs and professional aspirations.The study focuses especially on social innovation based on the principles of the social economy.It uses a new institutionalist, processual, multi-level analysis of the Business and Employment Cooperative, a hybrid organizational form that combines the institutional logics of entrepreneurship, employment and cooperation. It (1) deepens understanding of the interactions between social innovation and its context; (2) highlights a new strategy at institutional logic level that can overcome the tensions inherent in hybrid organizational forms; and (3) explains how hybrid organizations can enable people to (re)find meaning in their work.

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.

We introduce a family of logics extending the lightweight Description Logic EL, that allows us to define concepts in an approximate way. The main idea is to use a graded membership function m, which for each individual and concept yields a number in the interval [0,1] expressing the degree to which the individual belongs to the concept. Threshold concepts C~t for ~ in {<,<=,>,>=} then collect all the individuals that belong to C with degree ~t. We further study this framework in two particular directions. First, we define a specific graded membership function deg and investigate the complexity of reasoning in the resulting Description Logic tEL(deg) w.r.t. both the empty terminology and acyclic TBoxes. Second, we show how to turn concept similarity measures into membership degree functions. It turns out that under certain conditions such functions are well-defined, and therefore induce a wide range of threshold logics. Last, we present preliminary results on the computational complexity landscape of reasoning in such a big family of threshold logics.

Mathematical logic and automata theory are two scientific disciplines with a close relationship that is not only fundamental for many theoretical results but also forms the basis of a coherent methodology for the verification and synthesis of computing systems. This connection goes back to a much longer history in the 1960s, through the fundamental work of Büchi-Elgot-Trakhtenbrot, which shows the expressive equivalence of automata and logical systems such as monadic second-order logic on finite and infinite words. This allowed the handling of specifications (where global system properties are stated), and implementations (which involve the definition of the local steps in order to satisfy the global goals laid out in the specifications) in a single framework. This connection has been extended to and well-investigated for many other structures such as trees, finite pictures, timed words and data words. For many computer science applications, however, quantitative phenomena need to be modelled, as well. Examples are vagueness and uncertainty of a statement, length of time periods, spatial information, and resource consumption. Weighted automata, introduced by Schützenberger, are prominent models for quantitative aspects of systems. The framework of weighted monadic second-order logic over words was first introduced by Droste and Gastin. They gave a characterization of quantitative behavior of weighted finite automata, as semantics of monadic second-order sentences within their logic. Meanwhile, the idea of weighted logics was also applied to devices recognizing more general structures such as weighted tree automata, weighted automata on infinite words or traces. The main goal of this thesis is to give logical characterizations for weighted automata models on pictures and data words as well as for Büchi-tiling systems in the spirit of the classical Büchi-Elgot theorem. As the second goal, we deal with synchronizing problem for data words. Below, we briefly summarize the contents of this thesis. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures. Picture languages have been intensively investigated by several research groups. In Chapter 1, we define weighted two-dimensional on-line tessellation automata (W2OTA) taking weights from a new weight structure called picture valuation monoid. This new weighted picture automaton model can be used to model several applications, e.g. the average density of a picture. Such aspects could not be modelled by semiring weighted picture automaton model. The behavior of this automaton model is a picture series mapping pictures over an alphabet to elements of a picture valuation monoid. As one of our main results, we prove a Nivat theorem for W2OTA. It shows that recognizable picture series can be obtained precisely as projections of particularly simple unambiguously recognizable series restricted to unambiguous recognizable picture languages. In addition, we introduce a weighted monadic second-order logic (WMSO) which can model average density of pictures. As the other main result, we show that W2OTA and a suitable fragment of our weighted MSO logic are expressively equivalent. In Chapter 2, we generalize the notion of finite pictures to +ω-pictures, i.e., pictures which have finite number of rows and infinite number of columns. We extend conventional tiling systems with a Büchi acceptance condition in order to define the class of Büchi-tiling recognizable +ω-picture languages. The class of recognizable +ω-picture languages is indeed, a natural generalization of ω-regular languages. We show that the class of all Büchi-tiling recognizable +ω-picture languages has the similar closure properties as the class of tiling recognizable languages of finite pictures: it is closed under projection, union, and intersection, but not under complementation. While for languages of finite pictures, tiling recognizability and EMSO-definability coincide, the situation is quite different for languages of +ω-pictures. In this setting, the notion of tiling recognizability does not even cover the language of all +ω -pictures over Σ = {a, b} in which the letter a occurs at least once – a picture language that can easily be defined in first-order logic. As a consequence, EMSO is too strong for being captured by the class of tiling recognizable +ω-picture languages. On the other hand, EMSO is too weak for being captured by the class of all Büchi-tiling recognizable +ω-picture languages. To obtain a logical characterization of this class, we introduce the logic EMSO∞, which extends EMSO with existential quantification of infinite sets. Additionally, using combinatorial arguments, we show that the Büchi characterization theorem for ω-regular languges does not carry over to the Büchi-tiling recognizable +ω-picture languages. In Chapter 3, we consider the connection between weighted register automata and weighted logic on data words. Data words are sequences of pairs where the first element is taken from a finite alphabet (as in classical words) and the second element is taken from an infinite data domain. Register automata, introduced by Francez and Kaminski, provide a widely studied model for reasoning on data words. These automata can be considered as classical nondeterministic finite automata equipped with a finite set of registers which are used to store data in order to compare them with some data in the future. In this chapter, for quantitative reasoning on data words, we introduce weighted register automata over commutative data semirings equipped with a collection of binary data functions in the spirit of the classical theory of weighted automata. Whereas in the models of register automata known from the literature data are usually compared with respect to equality or a linear order, here we allow data comparison by means of an arbitrary collection of binary data relations. This approach permits easily to incorporate timed automata and weighted timed automata into our framework. Motivated by the seminal Büchi-Elgot-Trakhtenbrot theorem about the expressive equivalence of finite automata and monadic second-order (MSO) logic and by the weighted MSO logic of Droste and Gastin, we introduce weighted MSO logic on data words and give a logical characterization of weighted register automata. In Chapter 4, we study the concept of synchronizing data words in register automata. The synchronizing problem for data words asks whether there exists a data word that sends all states of the register automaton to a single state. The class of register automata that we consider here has a decidable non-emptiness problem, and the subclass of nondeterministic register automata with a single register has a decidable non-universality problem. We provide the complexity bounds of the synchronizing problem in the family of deterministic register automata with k registers (k-DRA), and in the family of nondeterministic register automata with single register (1-NRA), and in general undecidability of the problem in the family of k-NRA. To this end, we prove that, for k-DRA, inputting data words with only 2k + 1 distinct data values, from the infinite data domain, is sufficient to synchronize. Then, we show that the synchronizing problem for k-DRA is in general PSPACE-complete, and it is in NLOGSPACE for 1-DRA. For nondeterministic register automata (NRA), we show that Ackermann(n) distinct data, where n is the number of states of the register automaton, might be necessary to synchronize. Then, by means of a construction, proving that the synchronizing problem and the non-universality problem in 1-NRA are interreducible, we show the Ackermann-completeness of the problem for 1-NRA. However, for k-NRA, in general, we prove that this problem is undecidable due to the unbounded length of synchronizing data words.

In the context of the Semantic Web, ontologies based on Description Logics are gaining more and more importance for knowledge representation on a large scale. While the need arises for high quality ontologies with large background knowledge to enable powerful machine reasoning, the acquisition of such knowledge is only advancing slowly, because of the lack of appropriate tools. Concept learning algorithms have made a great leap forward and can help to speed up knowledge acquisition in the form of induced concept descriptions. This work investigated whether concept learning algorithms have reached a level on which they can produce results that can be used in an ontology engineering process. Two learning algorithms (YinYang and DL-Learner) are investigated in detail and tested with benchmarks. A method that enables concept learning on large knowledge bases on a SPARQL endpoint is presented and the quality of learned concepts is evaluated in a real use case. A proposal is made to increase the complexity of learned concept descriptions by circumventing the Open World Assumption of Description Logics.

We investigate weighted asynchronous cellular automata with weights in valuation monoids. These automata form a distributed extension of weighted finite automata and allow us to model concurrency. Valuation monoids are abstract weight structures that include semirings and (non-distributive) bounded lattices but also offer the possibility to model average behaviors. We prove that weighted asynchronous cellular automata and weighted finite automata which satisfy an I-diamond property are equally expressive. Depending on the properties of the valuation monoid, we characterize this expressiveness by certain syntactically restricted fragments of weighted MSO logics. Finally, we define the quantitative model-checking problem for distributed systems and show how it can be reduced to the corresponding problem for sequential systems.