bluuebunny/crossref_metadata_2025 huggingface dataset:
Omega-Completeness of the Logic of Here-and-There and Strong Equivalence of Logic Programs
Authors: Fandinno Jorge , Lifschitz Vladimir
Published: July 2023

Theory of strongly equivalent transformations is an essential part of the methodology of representing knowledge in answer set programming. Strong equivalence of two programs can be sometimes characterized as the possibility of deriving the rules of each program from the rules of the other in some deductive system. This paper describes a system with this property for the language mini-GRINGO. The key to the proof is an ω-completeness theorem for the many-sorted logic of here-and-there.
Logic-based Composition of Business Process Models
Authors: Fionda Valeria , Ielo Antonio , Ricca Francesco
Published: July 2023

Process Mining is a family of techniques that exploit data collected from process execution to analyze and improve process efficiency, quality, and security. Over the years, many modeling languages have been proposed for process model specification, with different expressiveness, features, and computational properties.

We propose a new logic-based declarative formalism, called Constraint Formulae, to compose process specifications, expressed in heterogeneous process modeling languages, without altering their original semantics. We formalize common process mining tasks for Constraint Formulae, study their computational properties, and provide an implementation in Answer Set Programming.
Reasoning about Probability via Continuous Functions
Authors: Flaminio Tommaso , Preto Sandro , Ugolini Sara
Published: July 2023

For functional representation in an algebraizable logic we mean a representation of the algebras of formulas of the logic by means of (possibly real-valued) functions.

Functional representations have shown to be a key tool for the study of non-classical logics, since they allow to regard formulas as functions and, by means of them, to approach the study of typical proof theoretical properties of the logics by means of their functional semantics. In the realm of (algebraizable) fuzzy logics, possibly the most well-known result in this respect is McNaughton theorem that shows formulas of the infinite-valued Lukasiewicz calculus to correspond, up to logical equivalence, to real valued continuous and piecewise linear functions. The functional representation for many-valued logics has been very recently shown in a paper by the second author to have an impact outside the purely logical realm and, in particular, they can be applied to study properties of artificial neural networks.

In this contribution, we will provide a functional representation for the probability modal logic FP(L) that builds on Lukasiewicz calculus by adding to it a unary operator P that reads “it is probable that”. While the logic FP(L) is not algebraizable, at least not in the usual sense due to Blok and Pigozzi, we still can provide a functional representation result for its modal formulas. In order to do so, we adapt the usual universal algebraic methods to this peculiar setting, and moreover we make use of some techniques developed in a recent paper by two of the authors where a class of purely algebraic models for FP(L) based on de Finetti's coherence criterion have been introduced and studied.

Our contribution will present two ways of providing a functional representation of the algebras of formulas of the modal logic FP(L): a local one, that relies on de Finetti's coherence argument; and a global one that, instead, relies on probability distributions on a finite domain.
Succinctness and Complexity of ALC with Counting Perceptrons
Authors: Galliani Pietro , Kutz Oliver , Troquard Nicolas
Published: July 2023

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.
Diagnosis for Post Concept Drift Decision Trees Repair
Authors: Almog Shaked , Kalech Meir
Published: July 2023

Decision trees are commonly used in machine learning since they are accurate and robust classifiers. After a decision tree is built, the data can change over time, causing the classification performance to decrease. This data distribution change is a known challenge in machine learning, referred to as concept drift. Once a concept drift has been detected, usually by experiencing a decrease in the model's performance, it can be handled by training a new model.

However, this method does not explain the drift harming the performance but only handles the drift's effects.

The main contribution of this paper presents a novel two-step approach called APPETITE, which applies diagnosis techniques to identify the feature that has drifted and then adjusts the model accordingly. For the diagnosis step, we present two algorithms. We experimented on 73 known datasets from the literature and semi-synthesized drifts in their features. Both algorithms are better at handling concept drift than training a new model based on the samples after the drift. Combining the two algorithms can provide an explanation of the drift and is a competitive model against a new model trained on the entire data from before and after the drift.
Do Repeat Yourself: Understanding Sufficient Conditions for Restricted Chase Non-Termination
Authors: Gerlach Lukas , Carral David
Published: July 2023

The disjunctive restricted chase is a sound and complete procedure for solving boolean conjunctive query entailment over knowledge bases of disjunctive existential rules. Alas, this procedure does not always terminate and checking if it does is undecidable. However, we can use acyclicity notions (sufficient conditions that imply termination) to effectively apply the chase in many real-world cases. To know if these conditions are as general as possible, we can use cyclicity notions (sufficient conditions that imply non-termination). In this paper, we discuss some issues with previously existing cyclicity notions, propose some novel notions for non-termination by dismantling the original idea, and empirically verify the generality of the new criteria.
Group Responsibility for Exceeding Risk Threshold
Authors: Gladyshev Maksim , Alechina Natasha , Dastani Mehdi , Doder Dragan
Published: July 2023

The need for tools and techniques to formally analyze and trace the responsibility for unsafe outcomes to decision-making actors is urgent. Existing formal approaches assume that the unsafe outcomes for which actors can be held responsible are actually realized. This paper considers a broader notion of responsibility where unsafe outcomes are not necessarily realized, but their probabilities are unacceptably high. We present a logic combining strategic, probabilistic and temporal primitives designed to express concepts such as the risk of an undesirable outcome and being responsible for exceeding a risk threshold. We demonstrate that the proposed logic is complete and decidable.
Pushing the Boundaries of Tractable Multiperspective Reasoning: A Deduction Calculus for Standpoint EL+
Authors: Gómez Álvarez Lucía , Rudolph Sebastian , Strass Hannes
Published: July 2023

Standpoint EL is a multi-modal extension of the popular description logic EL that allows for the integrated representation of domain knowledge relative to diverse standpoints or perspectives. Advantageously, its satisfiability problem has recently been shown to be in PTime, making it a promising framework for large-scale knowledge integration.

In this paper, we show that we can further push the expressivity of this formalism, arriving at an extended logic, called Standpoint EL+, which allows for axiom negation, role chain axioms, self-loops, and other features, while maintaining tractability. This is achieved by designing a satisfiability-checking deduction calculus, which at the same time addresses the need for practical algorithms. We demonstrate the feasibility of our calculus by presenting a prototypical Datalog implementation of its deduction rules.
The Impact of Structure in Answer Set Counting: Fighting Cycles and its Limits
Authors: Hecher Markus , Kiesel Rafael
Published: July 2023

Answer Set Programming is a widely used paradigm in knowledge representation and reasoning, which strongly relates to the satisfiability (SAT) of propositional formulas. While in the area of SAT the last couple of years brought significant advances and different techniques for solving hard counting-based problems (e.g., #SAT, weighted counting, projected counting) that require more effort than deciding satisfiability, ASP still falls short. Intuitively, one explanation for this lies in the structure of a program, that – compared to SAT – was shown to yield strong evidence for being slightly less useful during solving. Indeed, for the well-known structural measure treewidth that plays an important role in counting-based variants of SAT, ASP is expected to be at least slightly harder than SAT. The underlying source of this hardness increase lies in cyclic dependencies in the positive dependency graph. In this work, we consider which strategies are appropriate to tackle counting-based problems for ASP depending on cycle lengths. To this end, we present different encodings to counting-based variants of SAT that thereby directly utilize recent advances. For small cycle lengths, we demonstrate a novel strategy based on feedback vertex sets. While medium cycle lengths still leave room for future improvements, surprisingly, in case of cycles that are significantly larger than the structural dependencies (treewidth), we can even obtain a polynomial algorithm.
Revising Typical Beliefs: One Revision to Rule Them All
Authors: Heyninck Jesse , Casini Giovanni , Meyer Thomas , Straccia Umberto
Published: July 2023

Propositional Typicality Logic (PTL) extends propositional logic with a connective • expressing the most typical (alias normal or conventional) situations in which a given sentence holds. As such, it generalises e.g.~preferential logics that formalise reasoning with conditionals such as ``birds typically fly''. In this paper, we study revision of sets of PTL-sentences. We first show why it is necessary to extend the PTL-language with a possibility operator, and then define the revision of PTL-sentences syntactically and characterise it semantically. We show that this allows us to represent a wide variety of existing revision methods, such as propositional revision and revision of epistemic states. Furthermore, we provide several examples showing why our approach is innovative. In more detail, we study revision of a set of conditionals under preferential closure, and the addition and contraction of possible worlds from an epistemic state.
Knowledge Compilation and More with SharpSAT-TD
Authors: Kiesel Rafael , Eiter Thomas
Published: July 2023

SharpSAT-TD is a recently published exact model counter that performed exceptionally well in the recent editions of the Model Counting Competition (https://mccompetition.org/). Notably, it additionally features *weighted* model counting capabilities over any semiring. In this work, we show how to exploit this fact to use SharpSAT-TD as a knowledge compiler to the class of sd-DNNF circuits. Our experimental evaluation shows that the efficiency of SharpSAT-TD for (weighted) model counting transfers to knowledge compilation, since it outperforms other state of the art knowledge compilers on standard benchmark sets. Additionally, we generalized SharpSAT-TD's preprocessing to support arbitrary semirings and consider the utility of auxiliary variables in this setting.
Definitions and (Uniform) Interpolants in First-Order Modal Logic
Authors: Kurucz Agi , Wolter Frank , Zakharyaschev Michael
Published: July 2023

We first consider two decidable fragments of quantified modal logic S5: the one-variable fragment and its extension S5ALC that combines S5 and the description logic ALC with the universal role. As neither of them enjoys Craig interpolation or projective Beth definability, the existence of interpolants and explicit definitions of predicates---which is crucial in many knowledge engineering tasks---does not directly reduce to entailment. Our concern therefore is the computational complexity of deciding whether (uniform) interpolants and definitions exist for given input formulas, signatures and ontologies. We prove that interpolant and definition existence in the one-variable fragment of quantified modal logic S5 and in S5ALC is decidable in coN2ExpTime, being 2ExpTime-hard, while uniform interpolant existence is undecidable. Then we show that interpolant and definition existence in the one-variable fragment of quantified modal logic K is nonelementary decidable, while uniform interpolant existence is undecidable.
Query Rewriting with Disjunctive Existential Rules and Mappings
Authors: Leclère Michel , Mugnier Marie-Laure , Pérution-Kihli Guillaume
Published: July 2023

We consider the issue of answering unions of conjunctive queries (UCQs) with disjunctive existential rules and mappings. While this issue has already been well studied from a chase perspective, query rewriting within UCQs has hardly been addressed yet. We first propose a sound and complete query rewriting operator, which has the advantage of establishing a tight relationship between a chase step and a rewriting step. The associated breadth-first query rewriting algorithm outputs a minimal UCQ-rewriting when one exists. Second, we show that for any ``truly disjunctive'' nonrecursive rule, there exists a conjunctive query that has no UCQ-rewriting. It follows that the notion of finite unification sets (fus), which denotes sets of existential rules such that any UCQ admits a UCQ-rewriting, seems to have little relevance in this setting. Finally, turning our attention to mappings, we show that the problem of determining whether a UCQ admits a UCQ-rewriting through a disjunctive mapping is undecidable. We conclude with a number of open problems.
Complexity of Inconsistency-Tolerant Query Answering in Datalog+/– under Preferred Repairs
Authors: Lukasiewicz Thomas , Malizia Enrico , Molinaro Cristian
Published: July 2023

Inconsistency-tolerant semantics have been proposed to provide meaningful ontological query answers even in the presence of inconsistencies. Several such semantics rely on the notion of a repair, which is a "maximal" consistent subset of the database, where different maximality criteria might be adopted depending on the application at hand. Previous work in the context of Datalog+/- has considered only the subset and cardinality maximality criteria.

We take here a step further and study inconsistency-tolerant semantics under maximality criteria based on weights and priority levels. We provide a thorough complexity analysis for a wide range of existential rule languages and for several complexity measures.
Querying Circumscribed Description Logic Knowledge Bases
Authors: Lutz Carsten , Manière Quentin , Nolte Robin
Published: July 2023

Circumscription is one of the main approaches for defining non-monotonic description logics (DLs) and the decidability and complexity of traditional reasoning tasks, such as satisfiability of circumscribed DL knowledge bases (KBs) are well understood. For evaluating conjunctive queries (CQs) and unions thereof (UCQs), in contrast, not even decidability had been established. In this paper, we prove decidability of (U)CQ evaluation on circumscribed DL KBs and obtain a rather complete picture of both the combined complexity and the data complexity, for DLs ranging from ALCHIO via EL to various versions of DL-Lite. We also study the much simpler atomic queries (AQs).
Description Logics with Abstraction and Refinement
Authors: Lutz Carsten , Schulze Lukas
Published: July 2023

Ontologies often require knowledge representation on multiple levels of abstraction, but description logics (DLs) are not well-equipped for supporting this. We propose an extension of DLs in which abstraction levels are first-class citizens and which provides explicit operators for the abstraction and refinement of concepts and roles across multiple abstraction levels, based on conjunctive queries. We prove that reasoning in the resulting family of DLs is decidable while several seemingly harmless variations turn out to be undecidable. We also pinpoint the precise complexity of our logics and several relevant fragments.
ORLA: Learning Explainable Argumentation Models
Authors: Otero Cándido , Craandijk Dennis , Bex Floris
Published: July 2023

This paper presents ORLA (Online Reinforcement Learning Argumentation), a new approach for learning explainable symbolic argumentation models through direct exploration of the world. ORLA takes a set of expert arguments that promote some action in the world, and uses reinforcement learning to determine which of those arguments are the most effective for performing a task by maximizing a performance score. Thus, ORLA learns a preference ranking over the expert arguments such that the resulting value-based argumentation framework (VAF) can be used as a reasoning engine to select actions for performing the task. Although model-extraction methods exist that extract a VAF by mimicking the behavior of some non-symbolic model (e.g., a neural network), these extracted models are only approximations to their non-symbolic counterparts, which may result in both a performance loss and non-faithful explanations. Conversely, ORLA learns a VAF through direct interaction with the world (online learning), thus producing faithful explanations without sacrificing performance. This paper uses the Keepaway world as a case study and shows that models trained using ORLA not only perform better than those extracted from non-symbolic models but are also more robust. Moreover, ORLA is evaluated as a strategy discovery tool, finding a better solution than the expert strategy proposed by a related study.
A Belief Model for Conflicting and Uncertain Evidence: Connecting Dempster-Shafer Theory and the Topology of Evidence
Authors: Pinto Prieto Daira , de Haan Ronald , Özgün Aybüke
Published: July 2023

One problem to solve in the context of information fusion, decision-making, and other artificial intelligence challenges is to compute justified beliefs based on evidence. In real-life examples, this evidence may be inconsistent, incomplete, or uncertain, making the problem of evidence fusion highly non-trivial. In this paper, we propose a new model for measuring degrees of beliefs based on possibly inconsistent, incomplete, and uncertain evidence, by combining tools from Dempster-Shafer Theory and Topological Models of Evidence. Our belief model is more general than the aforementioned approaches in two important ways: (1) it can reproduce them when appropriate constraints are imposed, and, more notably, (2) it is flexible enough to compute beliefs according to various standards that represent agents' evidential demands. The latter novelty allows the users of our model to employ it to compute an agent's (possibly) distinct degrees of belief, based on the same evidence, in situations when, e.g, the agent prioritizes avoiding false negatives and when it prioritizes avoiding false positives. Finally, we show that computing degree of belief with this model is #P-complete in general.
Interactive Explanations by Conflict Resolution via Argumentative Exchanges
Authors: Rago Antonio , Li Hengzhi , Toni Francesca
Published: July 2023

As the field of explainable AI (XAI) is maturing, calls for interactive explanations for (the outputs of) AI models are growing, but the state-of-the-art predominantly focuses on static explanations. In this paper, we focus instead on interactive explanations framed as conflict resolution between agents (i.e. AI models and/or humans) by leveraging on computational argumentation. Specifically, we define Argumentative eXchanges (AXs) for dynamically sharing, in multi-agent systems, information harboured in individual agents’ quantitative bipolar argumentation frameworks towards resolving conflicts amongst the agents. We then deploy AXs in the XAI setting in which a machine and a human interact about the machine’s predictions. We identify and assess several theoretical properties characterising AXs that are suitable for XAI. Finally, we instantiate AXs for XAI by defining various agent behaviours, e.g. capturing counterfactual patterns of reasoning in machines and highlighting the effects of cognitive biases in humans. We show experimentally (in a simulated environment) the comparative advantages of these behaviours in terms of conflict resolution, and show that the strongest argument may not always be the most effective.
Simple Contrapositive Assumption-Based Argumentation with Partially-Ordered Preferences
Authors: Arieli Ofer , Heyninck Jesse
Published: July 2023

We show that assumption-based argumentation frameworks, based on contrapositive logics and partially-ordered preference functions, provide a solid platform for argumentation-based reasoning. Two useful properties of the preference functions are identified (selectivity and max-lower-boundedness), and extended forms of attacks relations are supported (exists-attacks and forall-attacks), which assure several desirable properties and a variety of reasoning modes.
Foundations for Projecting Away the Irrelevant in ASP Programs
Authors: Saribatur Zeynep G. , Woltran Stefan
Published: July 2023

Simplification of logic programs under the answer-set semantics has been studied from the very beginning of the field. One natural simplification is the removal of atoms that are deemed irrelevant. While equivalence-preserving rewritings are well understood and incorporated in state-of-the-art systems, more careful rewritings in the realm of strong or uniform equivalence have received considerably less attention. This might be due to the fact that these equivalence notions rely on comparisons with respect to context programs that remain the same for both the original and the simplified program. In this work, we pursue the idea that the atoms considered irrelevant are disregarded accordingly in the context programs of the simplification, and propose novel equivalence notions for this purpose. We provide necessary and sufficient conditions for these kinds of simplifiability of programs, and show that such simplifications, if possible, can actually be achieved by just projecting the atoms from the programs themselves. We furthermore provide complexity results for the problems of deciding simplifiability and equivalence testing.
Explainable Representations for Relation Prediction in Knowledge Graphs
Authors: Sousa Rita T. , Silva Sara , Pesquita Catia
Published: July 2023

Knowledge graphs represent real-world entities and their relations in a semantically-rich structure supported by ontologies. Exploring this data with machine learning methods often relies on knowledge graph embeddings, which produce latent representations of entities that preserve structural and local graph neighbourhood properties, but sacrifice explainability. However, in tasks such as link or relation prediction, understanding which specific features better explain a relation is crucial to support complex or critical applications.

We propose SEEK, a novel approach for explainable representations to support relation prediction in knowledge graphs. It is based on identifying relevant shared semantic aspects (i.e., subgraphs) between entities and learning representations for each subgraph, producing a multi-faceted and explainable representation.

We evaluate SEEK on two real-world highly complex relation prediction tasks: protein-protein interaction prediction and gene-disease association prediction.

Our extensive analysis using established benchmarks demonstrates that SEEK achieves comparable or even superior performance to standard learning representation methods while identifying both sufficient and necessary explanations based on shared semantic aspects.
Learning General Policies with Policy Gradient Methods
Authors: Ståhlberg Simon , Bonet Blai , Geffner Hector
Published: July 2023

While reinforcement learning methods have delivered remarkable results in a number of settings, generalization, i.e., the ability to produce policies that generalize in a reliable and systematic way, has remained a challenge. The problem of generalization has been addressed formally in classical planning where provable correct policies that generalize over all instances of a given domain have been learned using combinatorial methods. The aim of this work is to bring these two research threads together to illuminate the conditions under which (deep) reinforcement learning approaches, and in particular, policy optimization methods, can be used to learn policies that generalize like combinatorial methods do. We draw on lessons learned from previous combinatorial and deep learning approaches, and extend them in a convenient way. From the former, we model policies as state transition classifiers, as (ground) actions are not general and change from instance to instance. From the latter, we use graph neural networks (GNNs) adapted to deal with relational structures for representing value functions over planning states, and in our case, policies. With these ingredients in place, we find that actor-critic methods can be used to learn policies that generalize almost as well as those obtained using combinatorial approaches while avoiding the scalability bottleneck and the use of feature pools. Moreover, the limitations of the DRL methods on the benchmarks considered have little to do with deep learning or reinforcement learning algorithms, and result from the well-understood expressive limitations of GNNs, and the tradeoff between optimality and generalization (general policies cannot be optimal in some domains). Both of these limitations are addressed without changing the basic DRL methods by adding derived predicates and an alternative cost structure to optimize.
Grounding LTLf Specifications in Image Sequences
Authors: Umili Elena , Capobianco Roberto , De Giacomo Giuseppe
Published: July 2023

A critical challenge in neuro-symbolic (NeSy) approaches is to handle the symbol grounding problem without direct supervision. That is mapping high-dimensional raw data into an interpretation over a finite set of abstract concepts with a known meaning, without using labels. In this work, we ground symbols into sequences of images by exploiting symbolic logical knowledge in the form of Linear Temporal Logic over finite traces (LTLf) formulas, and sequence-level labels expressing if a sequence of images is compliant or not with the given formula. Our approach is based on translating the LTLf formula into an equivalent deterministic finite automaton (DFA) and interpreting the latter in fuzzy logic. Experiments show that our system outperforms recurrent neural networks in sequence classification and can reach high image classification accuracy without being trained with any single-image label.
Computing All Facts Entailed By An LTL Specification
Authors: Wałęga Przemysław Andrzej , Zawidzki Michał , Haase Christoph
Published: July 2023

We study the problem of efficiently computing all (usually infinitely many) facts which are entailed by a specification written in linear temporal logic (LTL)-a standard formalism for specifying and verifying properties of computations in reactive systems. This problem can be seen as a generalisation of the standard entailment checking, but whose output provides a much wider understanding of the system’s behaviour. We show that in full LTL the problem can be solved in doubly exponential time, whereas for Horn fragments of LTL, which can be seen as temporal logic programs, the problem can be solved in exponential or only quadratic time, depending on the allowed temporal operators in the input formula. Moreover, we show that all these bounds are optimal. We also implement and experimentally compare two techniques for solving the problem: an automata-based algorithm for full LTL and a materialisation-based algorithm for Horn fragments. The obtained results suggest practical usefulness of our approach.
A Singly Exponential Transformation of LTL[X, F] into Pure Past LTL
Authors: Artale Alessandro , Geatti Luca , Gigante Nicola , Mazzullo Andrea , Montanari Angelo
Published: July 2023

Confronting the past can be hard. This is true even in Linear Temporal Logic (LTL), interpreted on either infinite or finite traces, when faced with the problem of transforming a temporally future formula into an equivalent one that contains past temporal modalities only. To our knowledge, the best among the available pastification procedures for full LTL, as well as for expressive enough fragments of it (that is, containing at least one temporal modality other than tomorrow), are triply exponential in the size of the input. In this paper, we focus on the fragment of LTL that features the tomorrow and eventually modalities, and provide a singly exponential pastification algorithm for it. The transformation is based on a normalisation procedure that requires a non-trivial complexity analysis, and on the subsequent generation of a pure past formula from suitably-defined dependency tree structures. Moreover, leveraging its purely syntactic nature, we present an implementation of our procedure in a temporal satisfiability checking tool that deals with both future and past modalities.
Strategic Abilities of Forgetful Agents in Stochastic Environments
Authors: Belardinelli Francesco , Jamroga Wojciech , Mittelmann Munyque , Murano Aniello
Published: July 2023

In this paper, we investigate the probabilistic variants of the strategy logics ATL and ATL* under imperfect information. Specifically, we present novel decidability and complexity results when both the model transitions and the strategies played by agents are stochastic. That is, the semantics of the logics are based on multi-agent, stochastic transition systems with imperfect information, which combine two sources of uncertainty, namely, the partial observability agents have on the environment, and the likelihood of transitions to occur from a system state. Since the model checking problem is undecidable in general in this setting, we restrict our attention to agents with memoryless (positional) strategies. The resulting setting captures the situation in which agents have qualitative uncertainty of the local state and quantitative

uncertainty about the occurrence of future events. We illustrate the

usefulness of this setting with meaningful examples.
From Qualitative Choice Logic to Abstract Argumentation
Authors: Bernreiter Michael , König Matthias
Published: July 2023

Qualitative Choice Logic (QCL) extends classical propositional formulas by a connective called ordered disjunction that is used to express preferences.

We translate QCL theories to Argumentation Frameworks with Collective Attacks (SETAFs), and show that the preferred models of the original theory directly correspond to the semi-stable extensions of the target framework.

This further allows us to decide the problem of preferred model entailment for QCL via SETAFs.
Combining Global and Local Merges in Logic-based Entity Resolution
Authors: Bienvenu Meghyn , Cima Gianluca , Gutiérrez-Basulto Víctor , Ibáñez-García Yazmín
Published: July 2023

In the recently proposed LACE framework for collective entity resolution, logical rules and constraints are used to identify pairs of entity references (e.g. author or paper ids) that denote the same entity. This identification is global: all occurrences of those entity references (possibly across multiple database tuples) are deemed equal and can be merged. By contrast, a local form of merge is often more natural when identifying pairs of data values, e.g. some occurrences of 'J. Smith' may be equated with 'Joe Smith', while others should merge with 'Jane Smith'. This motivates us to extend LACE with local merges of values and explore the computational properties of the resulting formalism.
Finest Syntax Splittings of Ranking Functions and Total Preorders on Worlds
Authors: Haldimann Jonas Philipp , Beierle Christoph
Published: July 2023

The notion of syntax splitting was initially introduced by Parikh for belief sets, and one key observation is that every belief set has a unique finest syntax splitting, i.e., a syntax splitting that refines every other syntax splitting of that belief set. Later, the notion of syntax splitting was extended to ranking functions and total preorders on worlds (TPOs), which are two common models for belief states in the context of iterated belief revision. In this paper, we prove that ranking functions also have unique finest syntax splittings, i.e., every ranking function has a syntax splitting that refines all other syntax splittings of that ranking function. Using this, we can show that the syntax splittings of a ranking function κ are exactly the coarsenings of the finest splitting of κ. For TPOs we show that, in contrast to ranking functions, the coarsening of a syntax splitting of a TPO ⪯ is not necessarily a syntax splitting of ⪯. Despite that we can prove that every TPO has a unique finest syntax splitting that refines all other syntax splittings of that TPO.
Counterfactual Explanations and Model Multiplicity: a Relational Verification View
Authors: Leofante Francesco , Botoeva Elena , Rajani Vineet
Published: July 2023

We study the interplay between counterfactual explanations and model multiplicity in the context of neural network classifiers. We show that current explanation methods often produce counterfactuals whose validity is not preserved under model multiplicity. We then study the problem of generating counterfactuals that are guaranteed to be robust to model multiplicity, characterise its complexity and propose an approach to solve this problem using ideas from relational verification.
Connecting Proof Theory and Knowledge Representation: Sequent Calculi and the Chase with Existential Rules
Authors: Lyon Tim S. , Ostropolski-Nalewaja Piotr
Published: July 2023

Chase algorithms are indispensable in the domain of knowledge base querying, which enable the extraction of implicit knowledge from a given database via applications of rules from a given ontology. Such algorithms have proved beneficial in identifying logical languages which admit decidable query entailment. Within the discipline of proof theory, sequent calculi have been used to write and design proof-search algorithms to identify decidable classes of logics. In this paper, we show that the chase mechanism in the context of existential rules is in essence the same as proof-search in an extension of Gentzen's sequent calculus for first-order logic. Moreover, we show that proof-search generates universal models of knowledge bases, a feature also exhibited by the chase. Thus, we formally connect the main tool for establishing decidability proof-theoretically with a central decidability tool in the context of knowledge representation.
Eliminating Redundant Actions from Plans Using Classical Planning
Authors: Salerno Mauricio , Fuentetaja Raquel , Seipp Jendrik
Published: July 2023

Even though automated planning is PSPACE-complete in general, satisficing planners are able to solve large planning tasks quickly. However, the found plans are often far from optimal and may even contain actions that can be removed while maintaining a valid plan. The problem of finding and eliminating the most expensive set of such redundant actions in a plan is NP-complete and there is a compilation to MaxSAT that solves it. Here, we introduce a simple and natural formulation of the problem as a planning task. Solving it with an optimal planner guarantees finding a minimal reduction. Our experiments show that this is competitive with the previous state of the art for optimal action elimination.
Forgetting Aspects in Assumption-Based Argumentation
Authors: Berthold Matti , Rapberger Anna , Ulbricht Markus
Published: July 2023

We address the issue of forgetting in assumption-based argumentation (ABA). Forgetting is driven by the goal to remove certain elements from a knowledge base, while preserving the structure of its models as well as possible. We introduce several forgetting operators tailored to accomplish the removal of different pieces of the ABA knowledge base—assumptions, contraries, and atoms—formalizing a diverse selection of perspectives on this issue. We examine the quality of our operators by studying their compliance with suitable desiderata we propose. Thereby, we investigate the impact of the operators on the syntax of the given ABA knowledge base, its semantics, but also the instantiated argumentation framework; thus bridging recent forgetting studies on non-monotonic formalisms including argumentation theory.
Regional Constellation Reconfiguration Problem: Integer Linear Programming Formulation and Lagrangian Heuristic Method
Authors: Lee Hang Woon , Ho Koki
Published: July 2023

A group of satellites, with either homogeneous or heterogeneous orbital characteristics and/or hardware specifications, can undertake a reconfiguration process due to variations in operations pertaining to Earth observation missions. This paper investigates the problem of optimizing a satellite constellation reconfiguration process against two competing mission objectives: 1) the maximization of the total coverage reward, and 2) the minimization of the total cost of the transfer. The decision variables for the reconfiguration process include the design of the new configuration and the assignment of satellites from one configuration to another. We present a novel biobjective integer linear programming formulation that combines constellation design and transfer problems. The formulation lends itself to the use of generic mixed-integer linear programming (MILP) methods such as the branch-and-bound algorithm for the computation of provably optimal solutions; however, these approaches become computationally prohibitive even for moderately sized instances. In response to this challenge, this paper proposes a Lagrangian relaxation-based heuristic method that leverages the assignment problem structure embedded in the problem. The results from the computational experiments attest to the near-optimality of the Lagrangian heuristic solutions and a significant improvement in the computational runtime as compared to a commercial MILP solver.
Estimation of the Fan Rotational Speed Using Flyover Audio Recordings
Authors: Ramseier Thomas , Pieren Reto
Published: July 2023

Aircraft noise emissions affect societies around the world by impacting the population’s health and land use planning. This calls for simulation tools able to predict these types of noise emissions with high accuracy. A crucial aircraft parameter to achieve satisfying precision is the rotating frequency of the low-pressure shaft of the turbofan engine, called [Formula: see text]. [Formula: see text] determines the engine’s power use and is here estimated acoustically from ground-based microphones. A new method for dynamic [Formula: see text] estimation is presented, which is more robust as compared to earlier approaches. It makes use of different aircraft sound characteristics and combines two methods. The first method tracks multiple fan tone harmonics over time within a de-Dopplerized sound pressure spectrogram. This frequency-tracking task is solved by dynamic programming to find the global optimum. The second method relates to buzz-saw noise, and is thus applied to departures only. The buzz-saw fundamental frequency is estimated in the cepstral domain. Both submethods are separately validated and assessed with concurrent sound pressure measurements and flight deck recording data of [Formula: see text]. The new robust [Formula: see text] estimation method will be applied in noise measurement campaigns with the goal of improving current aircraft noise emission models.
Selecting Minimal Motion Primitive Libraries with Genetic Algorithms
Authors: Goddard Zachary C. , Wardlaw Kenneth , Williams Kyle , Mazumdar Anirban
Published: July 2023

Motion primitives allow for application of discrete search algorithms to rapidly produce trajectories in complex continuous space. The maneuver automaton (MA) provides an elegant formulation for creating a primitive library based on trims and maneuvers. However, performance is fundamentally limited by the contents of the primitive library. If the library is too sparse, performance can be poor in terms of path cost, whereas a library that is too large can increase run time. This work outlines new methods for using genetic algorithms to prune a primitive library. The proposed methods balance the path cost and planning time while maintaining the reachability of the MA. The genetic algorithm in this paper evaluates and mutates populations of motion primitive libraries to optimize both objectives. We illustrate the performance of these methods with a simulated study using a nonlinear medium-fidelity F-16 model. We optimize a library with the presented algorithm for obstacle-free navigation and a nap-of-the-Earth navigation task. In the obstacle-free navigation task, we show a tradeoff of a 10.16% higher planning cost for a 96.63% improvement in run time. In the nap-of-the-Earth task, we show a tradeoff of a 9.712% higher planning cost for a 92.06% improvement in run time.
Dynamic Pressure Measurements in a Rectangular Cavity with Multiple Stores
Authors: Smith Eric , Kumar Rajan , Eymann Timothy
Published: July 2023

An experimental investigation is carried out to study the effects of Mach number on the acoustic resonance characteristics of a rectangular cavity with and without multiple stores. Measurements are conducted for a cavity with a length-to-depth ratio of 4.5 at Mach numbers of 2, 3, 4, and 5. Dynamic pressures are measured within the cavity and on the store surfaces. An increase in Mach number results in a decrease in overall sound pressure levels at all measurement locations within the cavity. Pressure spectra indicate that increasing the Mach number decreases both the peak and broadband amplitudes of the cavity pressure fluctuations. At Mach 5, the amplitude of the cavity modes is significantly reduced in the upstream half of the cavity, and the modes are either indistinguishable from broadband levels or absent in the downstream half. The addition of stores reduces cavity acoustics, with two stores offering greater reduction than a single store. The effect of Mach number and the presence of stores on the aeroacoustic feedback loop in a cavity align with literature. Additionally, the pressure fluctuations on the windward store surface scale with Mach number in a similar trend as the cavity acoustics.
Information-Based Sensor Placement for Data-Driven Estimation of Unsteady Flows
Authors: Graff John , Medina Albert , Lagor Francis D.
Published: July 2023

Estimation of unsteady flowfields around flight vehicles may improve flow interactions and lead to enhanced vehicle performance. Although flowfield representations can be very high-dimensional, their dynamics can sometimes have low-order representations that may be estimated using a few, appropriately placed measurements. This paper presents a sensor-selection framework for the intended application of data-driven, flowfield estimation. This framework combines data-driven modeling, steady-state Kalman filter design, and sparse, sequential sensor selection. This paper also uses the sensor selection framework to design sensor arrays that can perform well for a collection of operating conditions. Flow estimation results on numerical data show that the proposed framework produces arrays that are highly effective at flowfield estimation for the flow behind and an airfoil at a high angle of attack using embedded pressure sensors. Analysis of the flowfields reveals that paths of impinging stagnation points along the airfoil’s surface during a shedding period of the flow are highly informative locations for placement of pressure sensors.
مستوى تضمين القِـيَم في مُقرَّر لغتي للصف الثالث الابتدائي في المملكة العربية السُّعودية في ضوء الأبعاد المشتركة لمعايير مناهج التعليم العام
Authors: الرساسمه تغريد سعيد , العرفج عبير محمد
Published: July 2023

هدفت الدراسة إلى الكشف عن مستوى تضمين مُؤشرات القيم في مُقرَّر لغتي للصف الثالث الابتدائي في المملكة العربية السُّعودية، في ضوء الأبعاد المشتركة لمعايير مناهج التعليم العام. ولتحقيق ذلك أُتبع المنهج الوصفي مُـمـثَّلًا بأسلوب تحليل المحتوى، حيث تم إعداد بطاقة التحليل من خلال الاستناد إلى مصفوفة القيم التي أقرتها هيئة تقويم التعليم والتدريب، في ضوء الأبعاد المشتركة لمعايير مناهج التعليم العام، وقد تكونت في صورتها النهائية من (28) مُؤشرًا، وحلل في ضوئها مُقرَّر لغتي للصف الثالث الابتدائي في التعليم العام بالمملكة العربية السُّعودية للفصلين الدراسيين الأول والثاني طبعة عام 1443ه-2021م، ثم حُلِلت البيانات برصد التكرارات، وحساب النسب المئوية. وتوصلت الدراسة إلى أنّ مستوى تضمين مُؤشرات القيم قد توافرت بنسب تراوحت بين مستوى تضمين متوسط، ومستوى تضمين منخفض، حيث جاءت قيمة "المسؤولية" في المرتبة الأولى بنسبة بلغت (38.58%)، وبمستوى تضمين متوسط، وقيمة "تقدير الذات" في المرتبة الثانية بنسبة (21.78%)، وبمستوى تضمين منخفض، وقيمة "الشغف المعرفي" في المرتبة الثالثة بنسبة (18.58%)، وبمستوى تضمين منخفض، وقيمة "الوسطية والاعتدال" في المرتبة الرابعة بنسبة (11.48%)، وبمستوى تضمين منخفض، وقيمة "تقوى الله" في المرتبة الخامسة بنسبة (6.04%)، وبمستوى تضمين منخفض، وقيمة "تقدير العمل وإتقانه" في المرتبة الأخيرة بنسبة (3.55%)، وبمستوى تضمين منخفض، وجاء بُعد القيم في عينة الدراسة بإجمالي تضمين بلغ (55.85%)، وبمستوى تضمين متوسط. وفي ضوء تلك النتائج قُدِّمت مجموعة من التوصيات، أبرزها: الاهتمام بمراعاة التوازن المنطقي في تضمين القيم في مُقرَّر لغتي للصف الثالث الابتدائي في المملكة العربية السُّعودية، في ضوء الأبعاد المشتركة لمعايير مناهج التعليم العام.
أثر تطبيق آليات الحوكمة على الإفصاح عن المسؤولية الاجتماعية في البنوك السعودية
Authors: الصائغ مها فيصل , الجعيد نوال محمد
Published: July 2023

هدفت الدراسة إلى معرفة أثر تطبيق آليات الحوكمة على الإفصاح عن المسؤولية الاجتماعية في البنوك السعودية وذلك من خلال دراسة أثر كلاً من حجم مجلس الإدارة؛ استقلالية المجلس؛ وحجم لجنة المراجعة ونشاطها، على هذا النوع من الإفصاح. ولتحقيق هذا الهدف تم الاعتماد على المنهج الاستقرائي لتكوين الإطار النظري، والمنهج الوصفي التحليلي في الجانب التطبيقي من الدراسة. تم جمع بيانات البنوك السعودية محل الدراسة عن الفترة (2018-2021م) من خلال التقارير السنوية المنشورة على موقع تداول. وأيضاً قامت الباحثتان ببناء مؤشر لقياس الإفصاح عن المسؤولية الاجتماعية اشتمل على 26 عنصر من عناصر المسؤولية الاجتماعية، كما تم استخدام اختبار تحليل الانحدار الخطي المتعدد لاختبار الفروض. أشارت نتائج الدراسة إلى وجود أثر لآليات الحوكمة المتمثلة في حجم مجلس الإدارة؛ وحجم لجنة المراجعة على الإفصاح عن المسؤولية الاجتماعية في البنوك السعودية. بينما لا يوجد أثر لكلاً من استقلالية المجلس ونشاط لجنة المراجعة على الإفصاح عن المسؤولية الاجتماعية في البنوك السعودية. تحديداً أشارت النتائج إلى وجود علاقة ارتباط طردية معنوية بين كلاً من حجم مجلس الإدارة وحجم لجنة المراجعة والإفصاح عن المسؤولية الاجتماعية، في حين أن هناك علاقة ارتباط طردية غير معنوية بين استقلالية المجلس والإفصاح. خلصت الدراسة لعدة توصيات أهمها: ضرورة قيام الجهات التنظيمية بوضع مؤشر خاص بالإفصاح وممارسات المسؤولية الاجتماعية ليكون بمثابة دليل استرشادي لمنظمات الأعمال؛ وليمثل مرجعية للباحثين المهتمين بمجال المسؤولية الاجتماعية. كما توصي الدراسة بعمل دراسات مستقبلية يتم من خلالها اختبار آليات أخرى للحوكمة مختلفة عن الآليات المستخدمة في الدراسة الحالية وبيان أثرها على الإفصاح عن المسؤولية الاجتماعية من حيث نوعية الإفصاح وجودته.