bluuebunny/crossref_metadata_2025 huggingface dataset:
Blending Grounding and Compilation for Efficient ASP Solving
Authors: Dodaro Carmine , Mazzotta Giuseppe , Ricca Francesco
Published: October 2024

Answer Set Programming (ASP) is a widely recognized formalism for Knowledge Representation and Reasoning. Traditional ASP systems, that employ the ground and solve architecture, are subject to the grounding bottleneck (i.e., variable-elimination can exhaust all computational resources).

Compilation-based approaches have recently demonstrated how grounding can be effectively bypassed by compiling rules into propagators that simulate them. However, compiling an entire ASP program is not always advantageous.

In this paper, we present both a program rewriting technique and an algorithm for the compilation of grounding that allow for unrestricted blending of grounding and compilation.

We implement these techniques in a hybrid ASP system that compares favourably with state-of-the-art ASP solvers on established benchmarks.
Weighted Merging Operators: Product, Utility-based Operators and Egalitarianism
Authors: Everaere Patricia , Konieczny Sébastien , Pino Pérez Ramón
Published: October 2024

We propose new operators for weighted propositional belief merging operators.

We introduce distance-based operators that use the product as aggregation function.

In social choice theory, the product, called the Nash welfare function, is known to be a more equitable social welfare function than the classical utilitarian welfare function (based on a sum).

We study which properties are satisfied by the obtained corresponding weighted merging operators.

In particular, we show that, unlike the Nash welfare function, distance-based operators using the product do not satisfy the Pigou-Dalton property.

Then, we introduce a new family of weighted merging operators, which we call utility-based weighted merging operators, where the utility is roughly the converse of a distance for distance-based operators.

For most well-known distance-based operators, it is easy to find the corresponding utility-based merging operators.

But an interesting result is that the utility-based weighted merging operator based on the product does not correspond to any standard distance-based weighted merging operator, and this operator satisfies the Pigou-Dalton property.
Heuristic Strategies for Accelerating Multi-Agent Epistemic Planning
Authors: Fang Biqing , Lin Fangzhen
Published: October 2024

Multi-agent epistemic planning (MEP) is about achieving an epistemic goal in a multi-agent environment using agents’ actions that have epistemic preconditions and effects. Recently, MEP has received interest from both the dynamic logic and planning communities, leading to the development of several innovative planners. One such state of the art planner is MEPK. In this paper, we propose two novel strategies to enhance the search methods within MEPK. Our first strategy, the enhancement strategy, dynamically updates the heuristic based on the search path to the first goal-reachable node, potentially reducing the number of nodes that need to be explored to find a solution. Our second, the belief lock strategy, prevents the planner from continuing to search a particular state that cannot progress to a goal state due to the possession by an agent of a certain belief. Our experiments on existing benchmarks show that the new strategies can indeed accelerate the problem solving. We also construct new harder instances and demonstrate that our strategies significantly improve the performance on these hard benchmarks. Overall, we consider our new planner a significant improvement over the existing one in terms of computational efficiency.
Boundedness for Unions of Conjunctive Regular Path Queries over Simple Regular Expressions
Authors: Figueira Diego , Krishna S , Mishra Om Swostik , Padmanabha Anantha
Published: October 2024

The problem of whether a recursive query can be rewritten as query without recursion is a fundamental reasoning task, known as the boundedness problem. Here we study the boundedness problem for Unions of Conjunctive Regular Path Queries (UCRPQs), a navigational query language extensively used in ontology and graph database querying. The boundedness problem for UCRPQs is known to be decidable, ExpSpace-complete. Here we focus our analysis on UCRPQs using simple regular expressions, which are of high practical relevance and enjoy a lower reasoning complexity. We show that the complexity for the boundedness problem for this UCRPQs fragment is Pi-p-2-complete, and that an equivalent bounded query can be produced in polynomial time whenever possible.

When the query turns out to be unbounded, we also study the task of finding an equivalent maximally bounded query, which we show to be feasible in Pi-p-2 . As a side result of independent interest stemming from our developments, we study a notion of succinct finite automata and prove that its membership problem is NP-complete.
Axiomatization of Approximate Exclusion
Authors: Häggblom Matilda
Published: October 2024

We define and axiomatize approximate exclusion atoms in the team semantic setting. A team is a set of assignments, which can be seen as a mathematical model of a uni-relational database. We say that an approximate exclusion atom is satisfied in a team if the corresponding usual exclusion atom is satisfied in a large enough subteam. We consider the implication problem for a set of approximate exclusion atoms and show that it is axiomatizable for consequences with a degree of approximation that is not too large. We prove the completeness theorem for usual exclusion atoms, currently missing from the literature, and generalize it to the approximate case. We also provide a polynomial time algorithm for the implication problems. The results can also be applied to exclusion dependencies in database theory.
Proper Linear-time Specifications of Environment Behaviors in Nondeterministic Planning and Reactive Synthesis
Authors: Aminof Benjamin , De Giacomo Giuseppe , Rubin Sasha , Zuleger Florian
Published: October 2024

To help it achieve its goal, an agent exploits assumptions it has about the behavior of its environment. The common view in planning and reactive synthesis is that such assumptions are sets of traces. This trace-centric view has the advantage of having well-understood specification formalisms, such as linear-time temporal logic. An alternative view, that we have promoted as being conceptually superior, is strategy-centric: assumptions are non-empty sets of environment strategies. In this work we relate these views and show that the strategy-centric view is a refinement of the trace-centric view. We thus address the following fundamental question: when should a set of traces be considered an assumption that the agent has about the environment's behavior? Our answer is in terms of coverability: every trace in the set should be consistent with some environment strategy that enforces it. We call such sets ``proper environment specifications''. Typical examples are given by (the traces consistent with a given) planning domain, and fairness constraints, but not arbitrary trace constraints. We provide an algorithm that, given a specification in linear-time temporal logic (LTL) decides whether or not it is a proper environment specification. Furthermore, we show that every set of traces has a ``proper environment core'', which excludes traces that the agent can ignore when devising its plan. We provide an algorithm for computing a representation of the core of an LTL formula, and prove that the core of an LTL-definable property is itself LTL-definable.
Verification of General Games with Imperfect Information Using Strategy Logic
Authors: He Yifan , Mittelmann Munyque , Murano Aniello , Saffidine Abdallah , Thielscher Michael
Published: October 2024

The Game Description Language with Imperfect Information (GDL-II) is a lightweight formalism for representing the rules of arbitrary games, including those where players have private information. Its purpose is to build general game-playing systems, that is, automated players that can understand the rules of games and learn how to play them without human intervention. Epistemic Strategy Logic (SLK), on the other hand, is a rich logical framework for reasoning about multi-agent systems and the strategic behavior of agents with partial observability. To enable a general game-playing system to take advantage of this rich formalism for the automatic verification of properties of games, we present a formal translation from GDL-II to SLK models. We prove the correctness of this translation and show how crucial properties of general games, including playability and the existence of Nash equilibria, can be expressed as formulas in SLK. Finally, we demonstrate the application of an existing model-checking system for SLK to verify the properties of GDL-II games.
Operator-Based Semantics for Choice Programs: Is Choosing Losing?
Authors: Heyninck Jesse
Published: October 2024

Choice constructs are an important part of the language of logic programming, yet the study of their semantics has been a challenging task. So far, only two-valued semantics have been studied, and the different proposals for such semantics have not been compared in a principled way. In this paper, an operator-based framework allow for the definition and comparison of different semantics in a principled way is proposed.
Extending Description Logics with Generic Concepts – the Tale of Two Semantics
Authors: Hirschbrunn Joshua , Kazakov Yevgeny
Published: October 2024

Description Logic (DL) ontologies often need to model

similar properties for different concepts. Taking inspiration from

generic classes in object-oriented programming, we introduce

concept parameters to describe related concepts.

For example, LocalAnesthesia[Eye] and LocalAnesthesia[Knee]

can be used to describe the anesthesia of an eye or a knee,

respectively. The main benefit of generic concepts is to be able

to describe general properties, for example, that every local

anesthesia is done by applying an anesthetic drug.

We propose to use generic concepts, such as LocalAnesthesia[X]

to define such properties, where a concept variable X can

be replaced with suitable concepts. To capture the intended

meaning of generic concepts, we define two semantics for

this extension: the schema semantics, in which concept

variables represent arbitrary concepts from a specific language,

and the second-order semantics, in which variables represent

arbitrary subsets of the domain. Generally, the second-order

semantics gives more logical consequences, but the schema

semantics allows a reduction to the classical DL reasoning.

To combine the benefits of both semantics, we define a useful

extension of the DL EL, for which both semantics coincide,

and a further restriction in which the entailment problem is

decidable.
Incentive Design for Rational Agents
Authors: Hyland David , Mittelmann Munyque , Murano Aniello , Perelli Giuseppe , Wooldridge Michael
Published: October 2024

We introduce Incentive Design: a new class of problems for equilibrium verification in multi-agent systems. In our model, agents attempt to maximize their utility functions, which are expressed as formulae in LTL[F], a quantitative extension of Linear Temporal Logic with functions computable in polynomial time. We assume agents are rational, in the sense that they adopt strategies consistent with game theoretic solution concepts such as Nash equilibrium. For each solution concept we consider, we analyze the problems of verifying whether an incentive scheme achieves a societal objective and finding one that does so, whether it be social welfare or any other aggregate measure of collective well-being. We study both static and dynamic incentive schemes, showing that the latter are more powerful than the former. Finally, we solve the incentive verification and synthesis problems for all the solution concepts we consider, and analyze their complexity.
Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation
Authors: Izza Yacine , Huang Xuanxiang , Morgado Antonio , Planes Jordi , Ignatiev Alexey , Marques-Silva Joao
Published: October 2024

The uses of machine learning (ML) have snowballed in recent years. In many cases, ML models are highly complex, and their operation is beyond the understanding of human decision-makers. Nevertheless, some uses of ML models involve high-stakes and safety-critical applications. Explainable artificial intelligence (XAI) aims to help human decision-makers in understanding the operation of such complex ML models, thus eliciting trust in their operation. Unfortunately, the majority of past XAI work is based on informal approaches, that offer no guarantees of rigor. Unsurprisingly, there exists comprehensive experimental and theoretical evidence confirming that informal methods of XAI can provide human-decision makers with erroneous information. Logic-based XAI represents a rigorous approach to explainability; it is model-based and offers the strongest guarantees of rigor of computed explanations.

However, a well-known drawback of logic-based XAI is the complexity of logic reasoning, especially for highly complex ML models. Recent work proposed distance-restricted explanations, i.e. explanations that are rigorous provided the distance to a given input is small enough. Distance-restricted explainability is tightly related with adversarial robustness, and it has been shown to scale for moderately complex ML models, but the number of inputs still represents a key limiting factor. This paper investigates novel algorithms for scaling up the performance of logic-based explainers when computing and enumerating ML model explanations with a large number of inputs.
Unique Characterisability and Learnability of Temporal Queries Mediated by an Ontology
Authors: Jung Jean Christoph , Ryzhikov Vladislav , Wolter Frank , Zakharyaschev Michael
Published: October 2024

Algorithms for learning database queries from examples and unique characterisations of queries by examples are prominent starting points for developing automated support for query explanation and construction. We investigate how far recent results and techniques on learning and unique characterisations of atemporal queries mediated by an ontology can be extended to temporal data and queries. Based on a systematic review of the relevant approaches in the atemporal case, we obtain general transfer results identifying conditions under which temporal queries composed of atemporal ones are (polynomially) learnable and uniquely characterisable.
Leveraging Decision-DNNF Compilation for Enumerating Disjoint Partial Models
Authors: Lagniez Jean-Marie , Lonca Emmanuel
Published: October 2024

The All-Solution Satisfiability Problem (AllSAT) extends SAT by requiring the identification of all possible solutions for a propositional formula. In practice, enumerating all complete models is often infeasible, making the identification of partial models essential for generating a concise representation of the solution set. Deterministic Decomposable Negation Normal Form (d-DNNF) serves as a language for representation known to offer polynomial-time algorithms for model enumeration. Specifically, when a propositional formula is encoded in d-DNNF, it enables iterative model enumeration with polynomial delay between models. However, despite the existence of theoretical algorithms for this purpose, no available implementations are currently accessible. Furthermore, these theoretical approaches are nearly impractical as they solely yield complete models. We introduce a novel algorithm that maintains a polynomial delay between partial models while significantly enhancing efficiency compared to baseline approaches. Furthermore, through experimental validation, we demonstrate the superiority of compiling a CNF formula Σ into a d-DNNF formula Σ′ and subsequently enumerating models of Σ′ over existing state-of-the-art methodologies for CNF partial model enumeration.
Complexity Results and Algorithms for Preferential Argumentative Reasoning in ASPIC+
Authors: Lehtonen Tuomo , Odekerken Daphne , Wallner Johannes P. , Järvisalo Matti
Published: October 2024

We provide complexity results and algorithms for reasoning in the central structured argumentation formalism of ASPIC+. Considering ASPIC+ accommodated with preferences under the last-link principle, the results are made possible by rephrasing several argumentation semantics---admissible, complete, stable, preferred and grounded---in terms of defeasible elements of an ASPIC+ theory for both democratic and elitist last-link lifting. Via the rephrasing, we establish that acceptance is polynomial-time computable under grounded semantics, and complete for either NP, coNP, or Pi_P^2, depending on the reasoning mode and semantics. We also detail answer set programming encodings for deciding acceptance for the NP/coNP-complete reasoning tasks, and empirically show that it scales significantly better than first translating ASPIC+ reasoning tasks to abstract argumentation. Finally, we show that, in contrast to the last-link principle, it is NP-hard to compute the grounded extension under the weakest-link principle.
Abstraction in Assumption-based Argumentation
Authors: Apostolakis Iosif , Saribatur Zeynep G. , Wallner Johannes P.
Published: October 2024

Approaches to computational argumentation provide foundational ways to reason argumentatively within Artificial Intelligence (AI). The underlying formal approaches can oftentimes be classified into structured argumentation and abstract argumentation. The former prescribe rigorous workflows, starting from knowledge bases to finding arguments in favour and against claims under scrutiny, and drawing conclusions. Abstract argumentation provides formal semantics operating on arguments whose internal structure is hidden and only relations are kept for reasoning, resulting in so-called argumentation frameworks (AFs). In this work, we apply a form of existential abstraction on the prominent structured approach of assumption-based argumentation (ABA), leading to an interactive way of simplifying argumentation scenarios by abstracting irrelevant details, towards supporting explainability. Existential abstraction was shown to be promising in many areas of AI, including a recent work on AFs. We lift this approach to the structured level---which is, as we show, both not direct from AFs and can benefit from utilization of the internal structure of arguments. Among our contributions, we introduce existential abstraction on ABA via clustering assumptions, develop semantics on clustered ABA frameworks for reasoning on such clusterings, show differences to the level of AFs, and provide a prototype interactive tool that obtains faithful clusterings that do not lead to any spurious reasoning.
Adding Circumscription to Decidable Fragments of First-Order Logic: A Complexity Rollercoaster
Authors: Lutz Carsten , Manière Quentin
Published: October 2024

We study extensions of expressive decidable fragments of first-order logic with circumscription, considering in particular the two-variable fragment FO^2, its extension C^2 with counting quantifiers, and the guarded fragment GF. We prove that if only unary predicates are minimized (or fixed) during circumscription, then decidability of logical consequence is preserved. For FO^2 the complexity increases from NExp to NExp^NP-complete, for GF it (remarkably!) increases from 2Exp to Tower-complete, and for C^2 it remains open. We also consider querying circumscribed knowledge bases whose ontology is a GF sentence, showing that the problem is decidable for unions of conjunctive queries, Tower-complete in combined complexity, and elementary in data complexity. Already for atomic queries and ontologies that are sets of guarded existential rules, however, for every k > 0 there is an ontology and query that are k-Exp-hard in data complexity.
Description Logics with Abstraction and Refinement: From ALC to EL
Authors: Lutz Carsten , Schulze Lukas
Published: October 2024

We study extensions of description logics from the widely used EL family with operators that make it possible to speak about different levels of abstraction. We analyze the computational complexity of reasoning and show that often, this complexity is significantly lower than in the corresponding extension of the more expressive description logic ALC. By slightly varying the semantics, we also obtain a case that admits reasoning in polynomial time.
SHACL Validation under the Well-founded Semantics
Authors: Okulmus Cem , Šimkus Mantas
Published: October 2024

W3C has recently introduced SHACL as a new standard for writing integrity constraints on graph-structured data (specifically, on RDF graphs). Unfortunately, the standard defines the semantics of non-recursive constraints only, leaving the case of recursive constraints open. This has spurred recent research efforts into finding a suitable, mathematically crisp semantics for constraints with cyclic dependencies. In this paper, we argue that recursive SHACL can be naturally equipped with a semantics inspired in the well-founded semantics for recursive logic programs with default negation. This semantics is not only intuitive, but it is also computationally tractable, unlike the previous proposals. The semantics is tolerant to constraint violations that are outside the realm of the so-called validation targets, which is a feature that is highly relevant in practice. In addition to defining the well-founded semantics using a notion of unfounded sets, we draw a connection to the classic definition of the well-founded semantics in logic programming: we provide a simple (yet inefficient) translation of recursive SHACL under the well-founded semantics into propositional logic programs under the well-founded semantics. This translation also provides a basis for a highly optimized SHACL validation engine, which we also present in this paper. Our system performs graph validation by producing a optimized logic program that can be evaluated using the DLV deductive database engine. The system has pay-as-you-go behavior: for validation with non-recursive constraints, the system avoids using a deductive database and instead only uses SPARQL queries over a RDF triplestore.
Explaining Decisions in ML Models: A Parameterized Complexity Analysis
Authors: Ordyniak Sebastian , Paesani Giacomo , Rychlicki Mateusz , Szeider Stefan
Published: October 2024

This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the prevalent black-box perception, our study focuses on models with transparent internal mechanisms. We address two principal types of explanation problems: abductive and contrastive, both in their local and global variants. Our analysis encompasses diverse ML models, including Decision Trees, Decision Sets, Decision Lists, Ordered Binary Decision Diagrams, Random Forests, and Boolean Circuits, and ensembles thereof, each offering unique explanatory challenges. This research fills a significant gap in explainable AI (XAI) by providing a foundational understanding of the complexities of generating explanations for these models. This work provides insights vital for further research in the domain of XAI, contributing to the broader discourse on the necessity of transparency and accountability in AI systems.
Advancing Algorithmic Approaches to Probabilistic Argumentation under the Constellation Approach
Authors: Popescu Andrei , Wallner Johannes P.
Published: October 2024

Reasoning with defeasible and conflicting knowledge in an argumentative form is a key research field in computational argumentation. Reasoning under various forms of uncertainty is both a key feature and a challenging barrier for automated argumentative reasoning. It was shown that argumentative reasoning using probabilities faces in general high computational complexity, in particular for the so-called constellation approach. In this paper, we develop an algorithmic approach to overcome this obstacle. We refine existing complexity results and show that two main reasoning tasks, that of computing the probability of a given set being an extension and an argument being acceptable, diverge in their complexity: the former is #P-complete and the latter is #-dot-NP-complete when considering their underlying counting problems. We present an algorithm for the complex task of computing the probability of a set of arguments being a complete extension by using dynamic programming operating on tree-decompositions. An experimental evaluation shows promise of our approach.
A Uniform Language to Explain Decision Trees
Authors: Arenas Marcelo , Barceló Pablo , Bustamante Diego , Caraball Jose , Subercaseaux Bernardo
Published: October 2024

The formal XAI community has studied a plethora of interpretability queries aiming to understand the classifications made by decision trees. However, a more uniform understanding of what questions we can hope to answer about these models, traditionally deemed to be easily interpretable, has remained elusive. In an initial attempt to understand uniform languages for interpretability, Arenas et al. proposed FOIL, a logic for explaining black-box ML models, and showed that it can express a variety of interpretability queries. However, we show that FOIL is limited in two important senses: (i) it is not expressive enough to capture some crucial queries, and (ii) its model agnostic nature results in a high computational complexity for decision trees.

In this paper, we carefully craft two fragments of first-order logic that allow for efficiently interpreting decision trees: Q-DT-FOIL and its optimization variant OPT-DT-FOIL. We show that our proposed logics can express not only a variety of interpretability queries considered by previous literature, but also elegantly allows users to specify different objectives the sought explanations should optimize for. Using finite model-theoretic techniques, we show that the different ingredients of Q-DT-FOIL are necessary for its expressiveness, and yet that queries in Q-DT-FOIL can be evaluated with a polynomial number of queries to a SAT solver, as well as their optimization versions in OPT-DT-FOIL. Besides our theoretical results, we provide a SAT-based implementation of the evaluation for OPT-DT-FOIL that is performant on industry-size decision trees.
The Realizability of Revision and Contraction Operators in Epistemic Spaces
Authors: Sauerwald Kai , Thimm Matthias
Published: October 2024

This paper studies the realizability of belief revision and belief contraction operators in epistemic spaces. We observe that AGM revision and AGM contraction operators for epistemic spaces are only realizable in precisely determined epistemic spaces. We define the class of linear change operators, which are a special kind of maxichoice operators. When AGM revision, respectively, AGM contraction, is realizable, linear change operators are a canonical realization.
Expressive Power of Definite Descriptions in Modal Logics
Authors: Wałęga Przemysław Andrzej
Published: October 2024

Motivated by applications in knowledge representation and reasoning, modal and description logics have been recently extended with definite description operators. Such operators provide us with a tool for referring to a particular element of a model by stating a property satisfied only by this element. This mechanism resembles the way we refer to objects in natural language, which makes it an attractive component of ontology and query languages. In this paper, we aim to provide a tool for analysing the expressive power of logics with definite descriptions. In particular, we introduce an adequate bisimulation notion for the basic modal logic extended with definite descriptions. We exploit the introduced bisimulation to relate expressive power of definite descriptions to other operators and we develop an algorithm for computing the maximal bisimulation between a pair of models. Furthermore, we consider a simplified setting, where expressions used in definite descriptions do not mention modal operators. We show how this restriction impacts our results.
Explaining Reasoning Results for OWL Ontologies with Evee
Authors: Alrabbaa Christian , Borgwardt Stefan , Friese Tom , Hirsch Anke , Knieriemen Nina , Koopmann Patrick , Kovtunova Alisa , Krüger Antonio , Popovič Alexej , Siahaan Ida
Published: October 2024

One of the advantages of formalizing domain knowledge in OWL ontologies is that one can use reasoning systems to infer implicit information automatically. However, it is not always straightforward to understand why certain entailments are inferred, and others are not. The popular ontology editor Protégé offers two explanation services to deal with this issue: justifications for OWL 2 DL ontologies, and proofs generated by the reasoner ELK for lightweight OWL 2 EL ontologies. Since justifications are often insufficient for explaining inferences, there is thus only little tool support for more comprehensive explanations in expressive ontology languages, and there is no tool support at all to explain why something was not derived. In this paper, we present Evee, a Java library and a collection of plug-ins for Protégé that offers advanced explanation services for both inferred and missing entailments. Evee explains inferred entailments using proofs in description logics up to ALCH. Missing entailments can be explained using counterexamples and abduction. We evaluated the effectiveness and the interface design of our plug-ins with description logic experts, ontology engineers, and students in two user studies. In these experiments, we were able to not only validate the tool but also gather feedback and insights to improve the existing designs.
ASP Chef: Draw and Expand
Authors: Alviano Mario , Rodriguez Reiners Luis Angel
Published: October 2024

ASP Chef is a versatile tool built upon the principles of Answer Set Programming (ASP), offering a unique approach to problem-solving through the concept of ASP recipes.

In this paper, we explore two key components of ASP Chef:

the Graph ingredient and one of its extension mechanisms for registering new ingredients.

The Graph ingredient serves as a fundamental feature within ASP Chef, allowing users to interpret instances of a designed predicate to construct graphs from the data.

Through this capability, ASP Chef facilitates the visualization and analysis of complex relationships and structures inherent in various domains.

Furthermore, ASP Chef offers a flexible extension mechanism that empowers users to register new recipes as custom ingredients.

These custom ingredients, defined by sequences of mappings from interpretations to interpretations, can be stored locally within the local storage of the browser.

This enables users to expand the capabilities of ASP Chef to suit their specific needs and use cases, fostering a collaborative environment where users can share and reuse custom ingredients seamlessly.

Notably, the addition of new ingredients does not impose requirements on the utilization of recipes that employ them, underscoring the modular and interoperable design of ASP Chef.
dPASP: A Probabilistic Logic Programming Environment For Neurosymbolic Learning and Reasoning
Authors: Geh Renato Lui , Gonçalves Jonas , Silveira Igor C. , Mauá Denis D. , Cozman Fabio G.
Published: October 2024

We present dPASP, a novel declarative probabilistic logic programming framework that allows for the specification of discrete probabilistic models by neural predicates, relational logic constraints, and interval-valued probabilistic choices. This expressive combination facilitates the construction of models that combine low-level perception (images, texts, etc) and common-sense reasoning, thus providing an excellent tool for neurosymbolic reasoning. To support all such features, we discuss several semantics for probabilistic logic programs that allow one to express nondeterminism, non-monotonic reasoning, contradiction, and (vague) probabilistic knowledge. We also discuss how gradient-based learning can be performed with neural predicates and probabilistic choices under selected semantics. To showcase the possibilities offered by the framework, we present case studies that exploit different semantics and constructs.
Deontic Reasoning Based on Inconsistency Measures
Authors: Arieli Ofer , van Berkel Kees , Raddaoui Badran , Strasser Christian
Published: October 2024

Conflicts are inherent to normative systems. In this paper, we explore a novel approach to normative reasoning by quantifying the amount of conflicts within normative systems. We refine the idea from classical logic, according to which a formula is a consequence of a knowledge base in case its negation renders the knowledge base inconsistent. In our approach, whether a formula is a logical consequence depends, for instance, on its negation's marginal contribution to the inconsistency of the given knowledge base. Accordingly, various inconsistency measures and corresponding (nonmonotonic and paraconsistent) normative entailment relations are analyzed relative to a number of logical properties. To illustrate our approach, we adopt Input/Output logic, a renowned formalism in deontic logic, specifically designed for defeasible normative reasoning. As an application, the resulting entailment relations provide recommendations to agents for minimizing norm conflicts, and may be incorporated in a number of implementations (like the Tweety libraries and the LogiKey framework) by involving inconsistency measurements in normative reasoning.
Nemo: Your Friendly and Versatile Rule Reasoning Toolkit
Authors: Ivliev Alex , Gerlach Lukas , Meusel Simon , Steinberg Jakob , Krötzsch Markus
Published: October 2024

We present Nemo, a toolkit for rule-based reasoning and data processing that emphasises robustness and ease of use. Nemo’s core is a scalable and efficient main-memory reasoner that supports an expressive extension of Datalog with support for datatypes, existential rules, aggregates, and (stratified) negation. Built around this core is a versatile system of libraries and applications for interfacing with several data formats and programming languages, use as a progressive web application, and IDE integration. In this system description, we present this toolkit and discuss relevant application areas in rule-based knowledge representation, knowledge graph processing, and reasoner prototyping. Our evaluation on a range of tasks from these areas demonstrates Nemo’s robust performance in comparison to state-of-the-art rule engines.
Non-Rigid Designators in Modal and Temporal Free Description Logics
Authors: Artale Alessandro , Kontchakov Roman , Mazzullo Andrea , Wolter Frank
Published: October 2024

Definite descriptions, such as ‘the General Chair of KR 2024’, are a semantically transparent device for object identification in knowledge representation. In first-order modal logic, definite descriptions have been widely investigated for their non-rigidity, which allows them to designate different objects (or none at all) at different states. We propose expressive modal description logics with non-rigid definite descriptions and names, and investigate decidability and complexity of the satisfiability problem. We first systematically link satisfiability for the one-variable fragment of first-order modal logic with counting to our modal description logics. Then, we prove a promising NEXPTIME-completeness result for concept satisfiability for the fundamental epistemic multi-agent logic S5n and its neighbours, and show that some expressive logics that are undecidable with constant domain become decidable (but Ackermann-hard) with expanding domains. Finally, we conduct a fine-grained analysis of decidability of temporal logics.
LAD-based Feature Selection for Optimal Decision Trees and Other Classifiers
Authors: Ing David , Jabbour Said , Sais Lakhdar , Delorme Fabien
Published: October 2024

The curse of dimensionality presents a significant challenge in data mining, pattern recognition, computer vision, and machine learning applications. Feature selection is a primary approach to address this challenge. It aims to eliminate irrelevant and redundant features while preserving the relevant ones to reduce computation time, improve prediction performance, and enhance the understanding of data. In this paper, we introduce a new feature selection (FS) technique based on the Logical Analysis of Data (LAD), a pattern learning framework that combines optimization, Boolean functions, and combinatorial theory. One of its main objectives is to generate minimal support sets of features (subsets of features) that discriminate between different groups of data. To generate such subsets, we first reduce the complexity of the LAD optimization task by transforming it into the problem of enumerating minimal hitting sets in a hypergraph, for which efficient implementations exist. Those feature subsets are then ranked based on a scoring method before selecting the highest quality one. Moreover, we explore the relationship between optimal Decision Trees (DTs) and LAD-based FS, introducing new optimality criteria, namely DTs involving a minimum number of features. Finally, we conduct comparative evaluations of LAD-based approach against several state-of-the-art (SOTA) FS methods on benchmark datasets, including two-class binary datasets and numerical datasets with two and multiple classes. Experiments reveal that our approach is competitive with SOTA methods, selecting high-quality feature subsets that maintain or enhance the performance of DTs and other classifiers like SVM, KNN, and Naive Bayes.
On the Expressivity of Recurrent Neural Cascades with Identity
Authors: Knorozova Nadezda Alexandrovna , Ronca Alessandro
Published: October 2024

Recurrent Neural Cascades (RNC) are the class of recurrent neural networks with no cyclic dependencies among recurrent neurons. Their subclass RNC+ with positive recurrent weights has been shown to be closely connected to the star-free regular languages, which are the expressivity of many well-established temporal logics. The existing expressivity results show that the regular languages captured by RNC+ are the star-free ones, and they leave open the possibility that RNC+ may capture languages beyond regular. We exclude this possibility for languages that include an identity element, i.e., an input that can occur an arbitrary number of times without affecting the output. Namely, in the presence of an identity element, we show that the languages captured by RNC+ are exactly the star-free regular languages. Identity elements are ubiquitous in temporal patterns, and hence our results apply to a large number of applications. The implications of our results go beyond expressivity. At their core, we establish a close structural correspondence between RNC+ and semiautomata cascades, showing that every neuron can be equivalently captured by a three-state semiautomaton. A notable consequence of this result is that RNC+ are no more succinct than cascades of three-state semiautomata.
Contestable AI Needs Computational Argumentation
Authors: Leofante Francesco , Ayoobi Hamed , Dejl Adam , Freedman Gabriel , Gorur Deniz , Jiang Junqi , Paulino-Passos Guilherme , Rago Antonio , Rapberger Anna , Russo Fabrizio , Yin Xiang , Zhang Dekai , Toni Francesca
Published: October 2024

AI has become pervasive in recent years, but state-of-the-art approaches predominantly neglect the need for AI systems to be contestable. Instead, contestability is advocated by AI guidelines (e.g. by the OECD) and regulation of automated decision-making (e.g. GDPR). In this position paper we explore how contestability can be achieved computationally in and for AI. We argue that contestable AI requires dynamic (human-machine and/or machine-machine) explainability and decision-making processes, whereby machines can

1. interact with humans and/or other machines to progressively explain their outputs and/or their reasoning as well as assess grounds for contestation provided by these humans and/or other machines, and 2. revise their decision-making processes to redress any issues successfully raised during contestation. Given that much of the current AI landscape is tailored to static AIs, the need to accommodate contestability will require a radical rethinking, that, we argue, computational argumentation is ideally suited to support.
Learning Robust Reward Machines from Noisy Labels
Authors: Parać Roko , Nodari Lorenzo , Ardon Leo , Furelos-Blanco Daniel , Cerutti Federico , Russo Alessandra
Published: October 2024

This paper presents PROB-IRM, an approach that learns

robust reward machines (RMs) for reinforcement learning

(RL) agents from noisy execution traces. The key aspect

of RM-driven RL is the exploitation of a finite-state ma-

chine that decomposes the agent’s task into different sub-

tasks. PROB-IRM uses a state-of-the-art inductive logic pro-

gramming framework robust to noisy examples to learn RMs

from noisy traces using the Bayesian posterior degree of be-

liefs, thus ensuring robustness against inconsistencies. Piv-

otal for the results is the interleaving between RM learning

and policy learning: a new RM is learned whenever the RL

agent generates a trace that is believed not to be accepted by

the current RM. To speed up the training of the RL agent,

PROB-IRM employs a probabilistic formulation of reward

shaping that uses the posterior Bayesian beliefs derived from

the traces. Our experimental analysis shows that PROB-IRM

can learn (potentially imperfect) RMs from noisy traces and

exploit them to train an RL agent to solve its tasks success-

fully. Despite the complexity of learning the RM from noisy

traces, agents trained with PROB-IRM perform comparably

to agents provided with handcrafted RMs.
Logical Distillation of Graph Neural Networks
Authors: Pluska Alexander , Welke Pascal , Gärtner Thomas , Malhotra Sagar
Published: October 2024

We present a logic based interpretable model for learning on graphs and an algorithm to distill this model from a Graph Neural Network (GNN). Recent results have shown connections between the expressivity of GNNs and the two-variable fragment of first-order logic with counting quantifiers (C2). We introduce a decision-tree based model which leverages an extension of C2 to distill interpretable logical classifiers from GNNs. We test our approach on multiple GNN architectures. The distilled models are interpretable, succinct, and attain similar accuracy to the underlying GNN. Furthermore, when the ground truth is expressible in C2, our approach outperforms the GNN.
Advancing Interactive Explainable AI via Belief Change Theory
Authors: Rago Antonio , Martinez Maria Vanina
Published: October 2024

As AI models become ever more complex and intertwined in humans’ daily lives, greater levels of interactivity of explainable AI (XAI) methods are needed. In this paper, we propose the use of belief change theory as a formal foundation for operators that model the incorporation of new information, i.e. user feedback in interactive XAI, to logical representations of data-driven classifiers. We argue that this type of formalisation provides a framework and a methodology to develop interactive explanations in a principled manner, providing warranted behaviour and favouring transparency and accountability of such interactions. Concretely, we first define a novel, logic-based formalism to represent explanatory information shared between humans and machines. We then consider real world scenarios for interactive XAI, with different prioritisations of new and existing knowledge, where our formalism may be instantiated. Finally, we analyse a core set of belief change postulates, discussing their suitability for our real world settings and pointing to particular challenges that may require the relaxation or reinterpretation of some of the theoretical assumptions underlying existing operators.
Automated Reasoning in Systems Biology: A Necessity for Precision Medicine
Authors: Zuidberg Dos Martires Pedro , Derkinderen Vincent , De Raedt Luc , Krantz Marcus
Published: October 2024

Recent developments in AI have reinvigorated pursuits to advance the (life) sciences using AI techniques, thereby creating a renewed opportunity to bridge different fields and find synergies. Headlines for AI and the life sciences have been dominated by data-driven techniques, for instance, to solve protein folding with next to no expert knowledge. In contrast to this, we argue for the necessity of a formal representation of expert knowledge -- either to develop explicit scientific theories or to compensate for the lack of data. Specifically, we argue that the fields of knowledge representation (KR) and systems biology (SysBio) exhibit important overlaps that have been largely ignored so far. This, in turn, means that relevant scientific questions are ready to be answered using the right domain knowledge (SysBio), encoded in the right way (SysBio/KR), and by combining it with modern automated reasoning tools (KR). Hence, the formal representation of domain knowledge is a natural meeting place for SysBio and KR. On the one hand, we argue that such an interdisciplinary approach will advance the field SysBio by exposing it to industrial-grade reasoning tools and thereby allowing novel scientific questions to be tackled. On the other hand, we see ample opportunities to move the state-of-the-art in KR by tailoring KR methods to the field of SysBio, which comes with challenging problem characteristics, e.g., scale, partial knowledge, noise, or sub-symbolic data. We stipulate that this proposed interdisciplinary research is necessary to attain a prominent long-term goal in the health sciences: precision medicine.
Oil price fluctuations and their relationship to government spending in Iraq for the period 2004-2022
Authors: Rawaa Mohammed Zabbar Al-Anzi  , Abdul Razzaq Hamad Hussein
Published: October 2024

The study aimed to know the fluctuations in global oil prices and their relationship to government spending in Iraq for the period 2004-2022, and to know their positive and negative effects and repercussions on the country’s general budget. The study was based on a set of hypotheses, the most important of which is: There is a positive correlation between fluctuations in global oil prices and government spending in Iraq. The descriptive analytical method was used in order to reach the results, the most important of which were the growth rates of total government spending, as they also varied greatly between rising at times and falling at other times throughout the study period. There is a complete direct relationship, which is demonstrated by the identical time path for the two series, which means that crude oil prices, whether average global prices, Basra Light oil prices, or others, are the influential and decisive factor in the volume of oil revenues.