We introduce a logical language for reasoning about quantized aggregate-combine graph neural networks with global readout (ACR-GNNs). We provide a logical characterization and use it to prove that verification tasks for quantized GNNs with readout are (co)NEXPTIME-complete. This result implies that the verification of quantized GNNs is computationally intractable, prompting substantial research efforts toward ensuring the safety of GNN-based systems. We also experimentally demonstrate that quantized ACR-GNN models are lightweight while maintaining good accuracy and generalization capabilities with respect to non-quantized models.

In this paper, we investigate verification of quantized Graph Neural Networks (GNNs), where some fixed-width arithmetic is used to represent numbers. We introduce the linear-constrained validity (LVP) problem for verifying GNNs properties, and provide an efficient translation from LVP instances into a logical language. We show that LVP is in PSPACE, for any reasonable activation functions. We provide a proof system. We also prove PSPACE-hardness, indicating that while reasoning about quantized GNNs is feasible, it remains generally computationally challenging.

The rise of AI-based and autonomous systems is raising concerns and apprehension due to potential negative repercussions arising from their behavior or decisions. These systems must be designed to comply with the human contexts in which they will operate. To this extent, Townsend et al. (2022) introduce the concept of SLEEC (social, legal, ethical, empathetic, or cultural) rules that aim to facilitate the formulation, verification, and enforcement of the rules AI-based and autonomous systems should obey. They lay out a methodology to elicit them and to let philosophers, lawyers, domain experts, and others to formulate them in natural language. To enable their effective use in AI systems, it is necessary to translate these rules systematically into a formal language that supports automated reasoning. In this study, we first conduct a linguistic analysis of the SLEEC rules pattern, which justifies the translation of SLEEC rules into classical logic. Then we investigate the computational complexity of reasoning about SLEEC rules and show how logical programming frameworks can be employed to implement SLEEC rules in practical scenarios. the result is a readily applicable strategy for implementing AI systems that conform to norms expressed as SLEEC rules.

The use of Dynamic Epistemic Logic (DEL) in multi-agent planning has led to a widely adopted action formalism that can handle nondeterminism, partial observability and arbitrary knowledge nesting. As such expressive power comes at the cost of undecidability, several decidable fragments have been isolated, mainly based on syntactic restrictions of the action formalism. In this paper, we pursue a novel semantic approach to achieve decidability. Namely, rather than imposing syntactical constraints, the semantic approach focuses on the axioms of the logic for epistemic planning. Specifically, we augment the logic of knowledge S5n and with an interaction axiom called (knowledge) commutativity, which controls the ability of agents to unboundedly reason on the knowledge of other agents. We then provide a threefold contribution. First, we show that the resulting epistemic planning problem is decidable. In doing so, we prove that our framework admits a finitary non-fixpoint characterization of common knowledge, which is of independent interest. Second, we study different generalizations of the commutativity axiom, with the goal of obtaining decidability for more expressive fragments of DEL. Finally, we show that two well-known epistemic planning systems based on action templates, when interpreted under the setting of knowledge, conform to the commutativity axiom, hence proving their decidability.

Perceptron operators have been introduced to knowledge representation languages such as description logics in order to define concepts by listing features with associated weights and by giving a threshold. Semantically, an individual then belongs to such a concept if the weighted sum of the listed features it belongs to reaches that threshold. Such operators have been subsequently applied to cognitively-motivated modelling scenarios and to building bridges between learning and reasoning. However, they suffer from the basic limitation that they cannot consider the weight or number of role fillers. This paper introduces an extension of the basic perceptron operator language to address this shortcoming, defining the language ALCP and answering some basic questions regarding the succinctness and complexity of the new language. Namely, we show firstly that in ALCP+, when weights are positive, the language is expressively equivalent to ALCQ, whilst it is strictly more expressive in the general case allowing also negative weights. Secondly, ALCP+ is shown to be strictly more succinct than ALCQ. Thirdly, capitalising on results concerning the logic ALCSCC, we show that despite the added expressivity, reasoning in ALCP remains EXPTIME-complete.

When considering two concepts in terms of extensional logic, their combination will often be trivial, returning an empty extension. Consider e.g. “a Fish Vehicle”, i.e., “a Vehicle which is also a Fish”. Still, people use sophisticated strategies to produce new, non-empty concepts. All these strategies involve the human ability to mend the conflicting attributes of the input concepts and to create new properties of the combination. We focus in particular on the case where a Head concept has superior ‘asymmetric’ control over steering the resulting combination (or hybridisation) with a Modifier concept. Specifically, we propose a dialogical model of the cognitive and logical mechanics of this asymmetric form of hybridisation. Its implementation is then evaluated using a combination of example ontologies.

When people combine concepts these are often characterised as “hybrid”, “impossible”, or “humorous”. However, when simply considering them in terms of extensional logic, the novel concepts understood as a conjunctive concept will often lack meaning having an empty extension (consider “a tooth that is a chair”, “a pet flower”, etc.). Still, people use different strategies to produce new non-empty concepts: additive or integrative combination of features, alignment of features, instantiation, etc. All these strategies involve the ability to deal with conflicting attributes and the creation of new (combinations of) properties. We here consider in particular the case where a Head concept has superior ‘asymmetric’ control over steering the resulting concept combination (or hybridisation) with a Modifier concept. Specifically, we propose a dialogical approach to concept combination and discuss an implementation based on axiom weakening, which models the cognitive and logical mechanics of this asymmetric form of hybridisation.

Abstract To introduce agent-based technologies in real-world systems, one needs to acknowledge that the agents often have limited access to resources. They have to seek after resource objectives and compete for those resources. We introduce a class of resource games where resources and preferences are specified with the language of a resource-sensitive logic. The agents are endowed with a bag of resources and try to achieve a resource objective. For each agent, an action consists in making available a part of their endowed resources. All the resources made available can be used towards the agents’ objectives. We study three decision problems, the first of which is deciding whether an action profile is a Nash equilibrium: when all the agents have chosen an action, it is a Nash Equilibrium if no agent has an incentive to change their action unilaterally. When dealing with resources, interesting questions arise as to whether some equilibria can be eliminated or constructed by a central authority by redistributing the available resources among the agents. In our economies, division of property in divorce law exemplifies how a central authority can redistribute the resources of individuals and why they would desire to do so. We thus study two related decision problems: (i) rational elimination: given an action profile’s outcome, can the endowed resources be redistributed so that it is not the outcome of a Nash equilibrium? (ii) Rational construction: given an action profile’s outcome, can the endowed resources be redistributed so that it is the outcome of a Nash equilibrium? Among other results, we prove that all three problems are $\mathsf{PSPACE}$-complete when the resources are described in the very expressive language of the propositional multiplicative and additive linear logic. We also identify a new modest fragment of linear logic that we call MULT, suitable to represent multisets and reason about the inclusion and equality of bags of resources. We show that when the resources are described in MULT, the problem of deciding whether a profile is a Nash equilibrium is in $\textsf{PTIME}$.

Ontology engineering is a hard and error-prone task, in which small changes may lead to errors, or even produce an inconsistent ontology. As ontologies grow in size, the need for automated methods for repairing inconsistencies while preserving as much of the original knowledge as possible increases. Most previous approaches to this task are based on removing a few axioms from the ontology to regain consistency. We propose a new method based on weakening these axioms to make them less restrictive, employing the use of refinement operators. We introduce the theoretical framework for weakening DL ontologies, propose algorithms to repair ontologies based on the framework, and provide an analysis of the computational complexity. Through an empirical analysis made over real-life ontologies, we show that our approach preserves significantly more of the original knowledge of the ontology than removing axioms.

We propose a simple model of interaction for resource-conscious agents. The resources involved are expressed in fragments of Linear Logic. We investigate a few problems relevant to cooperative games, such as deciding whether a group of agents can form a coalition and act together in a way that satisfies all of them. In terms of solution concepts, we study the computational aspects of the core of a game. The main contributions are a formal link with the existing literature, and complexity results for several classes of models.

In this paper, we investigate the rational synthesis problem for concurrent game structure for a variety of objectives ranging from reachability to Muller condition. We propose a new algorithm that establishes the decidability of the non cooperative rational synthesis problem that relies solely on game theoretic technique as opposed to previous approaches that are logic based. Thanks to this approach, we construct a zero-sum turn-based game that can be adapted to each one of the afore mentioned objectives thus obtain new complexity results. In particular, we show that reachability, safety, Büchi, and co-Büchi conditions are PSpace-complete, Muller, Street, and Rabin are PSpace-hard and in ExpTime.

We discuss steps towards a formalisation of the principles of an agentive naïve proto-physics, designed to match a level of abstraction that reflects the pre-linguistic conceptualisations and elementary notions of agency, as they develop during early human cognitive development. To this end, we present an agentive extension of the multi-dimensional image schema logic ISL based on variants of STIT theory, thus replacing the temporal dimension of ISL with an action-agnostic theory of agency. To begin grasping the notion of ‘animate agent’, we apply the newly defined logic to model the image schematic notion of ‘self movement’ as a means to distinguish the agentive capabilities of a mouse from those of a ball. Finally, we outline the prospects for employing the theory in cognitive robotics.

Axiom weakening is a novel technique that allows for fine-grained repair of inconsistent ontologies. In a multi-agent setting, integrating ontologies corresponding to multiple agents may lead to inconsistencies. Such inconsistencies can be resolved after the integrated ontology has been built, or their generation can be prevented during ontology generation. We implement and compare these two approaches. First, we study how to repair an inconsistent ontology resulting from a voting-based aggregation of views of heterogeneous agents. Second, we prevent the generation of inconsistencies by letting the agents engage in a turn-based rational protocol about the axioms to be added to the integrated ontology. We instantiate the two approaches using real-world ontologies and compare them by measuring the levels of satisfaction of the agents w.r.t. the ontology obtained by the two procedures.

We study a fragment of Intuitionistic Linear Logic combined with non-normal modal operators. Focusing on the minimal modal logic, we provide a Gentzen-style sequent calculus as well as a semantics in terms of Kripke resource models. We show that the proof theory is sound and complete with respect to the class of minimal Kripke resource models. We also show that the sequent calculus allows cut elimination. We put the logical framework to use by instantiating it as a logic of agency. In particular, we apply it to reason about the resource-sensitive use of artefacts.

We show that logic has more to offer to ontologists than standard first order and modal operators. We first describe some operators of linear logic which we believe are particularly suitable for ontological modeling, and suggest how to interpret them within an ontological framework. After showing how they can coexist with those of classical logic, we analyze three notions of artifact from the literature to conclude that these linear operators allow for reducing the ontological commitment needed for their formalization, and even simplify their logical formulation.

Artefacts (physical and institutional) are ubiquitous of our social environment. We live in a tight network of socio-technical systems, which are systems where agents interact with created objects. There is an increasing need for rigorous methods to model, specify, and reason about socio-technical systems in general, and about artefacts and their functions in particular. We propose a formal theory that serves at the conceptualization of artefacts and their manipulations: design, implementation, existence, use, and persistence.

The logics of “bringing-it-about” have been part of a prominent tradition for the formalization of individual and institutional agency. They are the logics to talk about what states of affairs an acting entity brings about while abstracting away from the means of action. Elgesem’s proposal analyzes the agency of individual agents as the goal-directed manifestation of an individual ability. It has become an authoritative modern reference. The first contribution of this paper is to extend Elgesem’s logic of individual agency and ability to coalitions. We present a general theory and later propose several possible specializations. As a second contribution, we offer algorithms to reason with the logics of bringing-it-about and we analyze their computational complexity.

We study a version of Propositional Dynamic Logic (PDL) that we call Dynamic Logic of Propositional Assignments (DL-PA). The atomic programs of DL-PA are assignments of propositional variables to true or to false. We show that DL-PA behaves better than PDL, having e.g. compactness and eliminability of the Kleene star. We establish tight complexity results: both satisfiability and model checking are EXPTIME-complete.

International audience

We introduce a logic designed to support reasoning about social choice functions. The logic includes operators to capture strategic ability, and operators to capture agent preferences. We give a correspondence between formulae in the logic and properties of social choice functions, and show that the logic is expressively complete with respect to social choice functions, i.e., that every social choice function can be characterised as a formula of the logic. We show the decidability of the logic and give a complete axiomatization. To demonstrate the value of the logic, we show in particular how it can be applied to the problem of determining whether a social choice function is strategy-proof.

In this paper we show how coalition logic can be reduced to the fusion of a normal modal STIT logic for agency and a standard normal temporal logic for discrete time, and how this multi-modal system can be suitably extended with an epistemic modality. Both systems are complete, and we provide a new axiomatization for the STIT-fragment. The epistemic extension enables us to express that agents see to something under uncertainty about the present state or uncertainty about which action is being taken. In accordance with established terminology in the planning community, we call this version of STIT the 'conformant STIT'. The conformant STIT enables us to express that agents are able to perform a uniform strategy. As a final word of recommendation for this paper we want to point out that its subject is at the junction of four academic fields, viz. modal logic, philosophy, game-theory and AI-planning.

International audience