Search

Dung's Abstract Argumentation Framework (AF) has emerged as a key formalism for argumentation in Artificial Intelligence. It has been extended in several directions, including the possibility to express supports, leading to the development of the Bipolar Argumentation Framework (BAF), and recursive attacks and supports, resulting in the Recursive BAF (Rec-BAF). Different interpretations of supports have been proposed, whereas for Rec-BAF (where the target of attacks and supports may also be attacks and supports) even different semantics for attacks have been defined. However, the semantics of these frameworks have either not been defined in the presence of support cycles, or are often quite intricate in terms of the involved definitions. We encompass this limitation and present classical semantics for general BAF and Rec-BAF and show that the semantics for specific BAF and Rec-BAF frameworks can be defined by very simple and intuitive modifications of that defined for the case of AF. This is achieved by providing a modular definition of the sets of defeated and acceptable elements for each AF-based framework. We also characterize, in an elegant and uniform way, the semantics of general BAF and Rec-BAF in terms of logic programming and partial stable model semantics., Comment: Paper presented at the 40th International Conference on Logic Programming (ICLP 2024), University of Texas at Dallas, USA, October 2024. arXiv admin note: text overlap with arXiv:2008.02550

Explainable Artificial Intelligence and Formal Argumentation have received significant attention in recent years. Argumentation-based systems often lack explainability while supporting decision-making processes. Counterfactual and semifactual explanations are interpretability techniques that provide insights into the outcome of a model by generating alternative hypothetical instances. While there has been important work on counterfactual and semifactual explanations for Machine Learning models, less attention has been devoted to these kinds of problems in argumentation. In this paper, we explore counterfactual and semifactual reasoning in abstract Argumentation Framework. We investigate the computational complexity of counterfactual- and semifactual-based reasoning problems, showing that they are generally harder than classical argumentation problems such as credulous and skeptical acceptance. Finally, we show that counterfactual and semifactual queries can be encoded in weak-constrained Argumentation Framework, and provide a computational strategy through ASP solvers.

EXplainable AI has received significant attention in recent years. Machine learning models often operate as black boxes, lacking explainability and transparency while supporting decision-making processes. Local post-hoc explainability queries attempt to answer why individual inputs are classified in a certain way by a given model. While there has been important work on counterfactual explanations, less attention has been devoted to semifactual ones. In this paper, we focus on local post-hoc explainability queries within the semifactual `even-if' thinking and their computational complexity among different classes of models, and show that both linear and tree-based models are strictly more interpretable than neural networks. After this, we introduce a preference-based framework that enables users to personalize explanations based on their preferences, both in the case of semifactuals and counterfactuals, enhancing interpretability and user-centricity. Finally, we explore the complexity of several interpretability problems in the proposed preference-based framework and provide algorithms for polynomial cases., Comment: arXiv admin note: text overlap with arXiv:2010.12265 by other authors

Data exchange, the problem of transferring data from a source schema to a target schema, has been studied for several years. The semantics of answering positive queries over the target schema has been defined in early work, but little attention has been paid to more general queries. A few proposals of semantics for more general queries exist but they either do not properly extend the standard semantics under positive queries, giving rise to counterintuitive answers, or they make query answering undecidable even for the most important data exchange settings, e.g., with weakly-acyclic dependencies. The goal of this paper is to provide a new semantics for data exchange that is able to deal with general queries. At the same time, we want our semantics to coincide with the classical one when focusing on positive queries, and to not trade-off too much in terms of complexity of query answering. We show that query answering is undecidable in general under the new semantics, but it is $\co\NP\complete$ when the dependencies are weakly-acyclic. Moreover, in the latter case, we show that exact answers under our semantics can be computed by means of logic programs with choice, thus exploiting existing efficient systems. For more efficient computations, we also show that our semantics allows for the construction of a representative target instance, similar in spirit to a universal solution, that can be exploited for computing approximate answers in polynomial time. Under consideration in Theory and Practice of Logic Programming (TPLP)., Comment: Under consideration in Theory and Practice of Logic Programming (TPLP)

Open-source, Decentralized Online Social Networks (DOSNs) are emerging as alternatives to the popular yet centralized and profit-driven platforms like Facebook or Twitter. In DOSNs, users can set up their own server, or instance, while they can actually interact with users of other instances. Moreover, by adopting the same communication protocol, DOSNs become part of a massive social network, namely the Fediverse. Mastodon is the most relevant platform in the Fediverse to date, and also the one that has attracted attention from the research community. Existing studies are however limited to an analysis of a relatively outdated sample of Mastodon focusing on few aspects at a user level, while several open questions have not been answered yet, especially at the instance level. In this work, we aim at pushing forward our understanding of the Fediverse by leveraging the primary role of Mastodon therein. Our first contribution is the building of an up-to-date and highly representative dataset of Mastodon. Upon this new data, we have defined a network model over Mastodon instances and exploited it to investigate three major aspects: the structural features of the Mastodon network of instances from a macroscopic as well as a mesoscopic perspective, to unveil the distinguishing traits of the underlying federative mechanism; the backbone of the network, to discover the essential interrelations between the instances; and the growth of Mastodon, to understand how the shape of the instance network has evolved during the last few years, also when broading the scope to account for instances belonging to other platforms. Our extensive analysis of the above aspects has provided a number of findings that reveal distinguishing features of Mastodon and that can be used as a starting point for the discovery of all the DOSN Fediverse., Comment: Accepted for publication with Applied Network Science, Springer Open, June 12, 2021

Since the first conference held in Marseille in 1982, ICLP has been the premier international event for presenting research in logic programming. Contributions are solicited in all areas of logic programming and related areas, including but not restricted to: - Foundations: Semantics, Formalisms, Answer-Set Programming, Non-monotonic Reasoning, Knowledge Representation. - Declarative Programming: Inference engines, Analysis, Type and mode inference, Partial evaluation, Abstract interpretation, Transformation, Validation, Verification, Debugging, Profiling, Testing, Logic-based domain-specific languages, constraint handling rules. - Related Paradigms and Synergies: Inductive and Co-inductive Logic Programming, Constraint Logic Programming, Interaction with SAT, SMT and CSP solvers, Logic programming techniques for type inference and theorem proving, Argumentation, Probabilistic Logic Programming, Relations to object-oriented and Functional programming, Description logics, Neural-Symbolic Machine Learning, Hybrid Deep Learning and Symbolic Reasoning. - Implementation: Concurrency and distribution, Objects, Coordination, Mobility, Virtual machines, Compilation, Higher Order, Type systems, Modules, Constraint handling rules, Meta-programming, Foreign interfaces, User interfaces. - Applications: Databases, Big Data, Data Integration and Federation, Software Engineering, Natural Language Processing, Web and Semantic Web, Agents, Artificial Intelligence, Bioinformatics, Education, Computational life sciences, Education, Cybersecurity, and Robotics.

Recently there has been an increasing interest in frameworks extending Dung's abstract Argumentation Framework (AF). Popular extensions include bipolar AFs and AFs with recursive attacks and necessary supports. Although the relationships between AF semantics and Partial Stable Models (PSMs) of logic programs has been deeply investigated, this is not the case for more general frameworks extending AF. In this paper we explore the relationships between AF-based frameworks and PSMs. We show that every AF-based framework $\Delta$ can be translated into a logic program $P_\Delta$ so that the extensions prescribed by different semantics of $\Delta$ coincide with subsets of the PSMs of $P_\Delta$. We provide a logic programming approach that characterizes, in an elegant and uniform way, the semantics of several AF-based frameworks. This result allows also to define the semantics for new AF-based frameworks, such as AFs with recursive attacks and recursive deductive supports. Under consideration for publication in Theory and Practice of Logic Programming., Comment: Paper presented at the 36th International Conference on Logic Programming (ICLP 2019), University Of Calabria, Rende (CS), Italy, September 2020, 16 pages

It is widely acknowledged that function symbols are an important feature in answer set programming, as they make modeling easier, increase the expressive power, and allow us to deal with infinite domains. The main issue with their introduction is that the evaluation of a program might not terminate and checking whether it terminates or not is undecidable. To cope with this problem, several classes of logic programs have been proposed where the use of function symbols is restricted but the program evaluation termination is guaranteed. Despite the significant body of work in this area, current approaches do not include many simple practical programs whose evaluation terminates. In this paper, we present the novel classes of rule-bounded and cycle-bounded programs, which overcome different limitations of current approaches by performing a more global analysis of how terms are propagated from the body to the head of rules. Results on the correctness, the complexity, and the expressivity of the proposed approach are provided., Comment: Under consideration in Theory and Practice of Logic Programming (TPLP)

Recently, there has been an increasing interest in the bottom-up evaluation of the semantics of logic programs with complex terms. The presence of function symbols in the program may render the ground instantiation infinite, and finiteness of models and termination of the evaluation procedure, in the general case, are not guaranteed anymore. Since the program termination problem is undecidable in the general case, several decidable criteria (called program termination criteria) have been recently proposed. However, current conditions are not able to identify even simple programs, whose bottom-up execution always terminates. The paper introduces new decidable criteria for checking termination of logic programs with function symbols under bottom-up evaluation, by deeply analyzing the program structure. First, we analyze the propagation of complex terms among arguments by means of the extended version of the argument graph called propagation graph. The resulting criterion, called Gamma-acyclicity, generalizes most of the decidable criteria proposed so far. Next, we study how rules may activate each other and define a more powerful criterion, called safety. This criterion uses the so-called safety function able to analyze how rules may activate each other and how the presence of some arguments in a rule limits its activation. We also study the application of the proposed criteria to bound queries and show that the safety criterion is well-suited to identify relevant classes of programs and bound queries. Finally, we propose a hierarchy of classes of terminating programs, called k-safety, where the k-safe class strictly includes the (k-1)-safe class. Note: To appear in Theory and Practice of Logic Programming (TPLP)., Comment: 36 pages, 7 figures

This paper presents a logic language for expressing NP search and optimization problems. Specifically, first a language obtained by extending (positive) Datalog with intuitive and efficient constructs (namely, stratified negation, constraints and exclusive disjunction) is introduced. Next, a further restricted language only using a restricted form of disjunction to define (non-deterministically) subsets (or partitions) of relations is investigated. This language, called NP Datalog, captures the power of Datalog with unstratified negation in expressing search and optimization problems. A system prototype implementing NP Datalog is presented. The system translates NP Datalog queries into OPL programs which are executed by the ILOG OPL Development Studio. Our proposal combines easy formulation of problems, expressed by means of a declarative logic language, with the efficiency of the ILOG System. Several experiments show the effectiveness of this approach., Comment: To appear in Theory and Practice of Logic Programming (TPLP)

In this paper we analyze declarative deterministic and non-deterministic semantics for active rules. In particular we consider several (partial) stable model semantics, previously defined for deductive rules, such as well-founded, max deterministic, unique total stable model, total stable model, and maximal stable model semantics. The semantics of an active program AP is given by first rewriting it into a deductive program P, then computing a model M defining the declarative semantics of P and, finally, applying `consistent' updates contained in M to the source database. The framework we propose permits a natural integration of deductive and active rules and can also be applied to queries with function symbols or to queries over infinite databases., Comment: 27 pages

In the design of algorithms, the greedy paradigm provides a powerful tool for solving efficiently classical computational problems, within the framework of procedural languages. However, expressing these algorithms within the declarative framework of logic-based languages has proven a difficult research challenge. In this paper, we extend the framework of Datalog-like languages to obtain simple declarative formulations for such problems, and propose effective implementation techniques to ensure computational complexities comparable to those of procedural formulations. These advances are achieved through the use of the "choice" construct, extended with preference annotations to effect the selection of alternative stable-models and nondeterministic fixpoints. We show that, with suitable storage structures, the differential fixpoint computation of our programs matches the complexity of procedural algorithms in classical search and optimization problems., Comment: 27 pages

In this paper, we propose a variant of stable model semantics for disjunctive logic programming and deductive databases. The semantics, called minimal founded, generalizes stable model semantics for normal (i.e. non disjunctive) programs but differs from disjunctive stable model semantics (the extension of stable model semantics for disjunctive programs). Compared with disjunctive stable model semantics, minimal founded semantics seems to be more intuitive, it gives meaning to programs which are meaningless under stable model semantics and is no harder to compute. More specifically, minimal founded semantics differs from stable model semantics only for disjunctive programs having constraint rules or rules working as constraints. We study the expressive power of the semantics and show that for general disjunctive datalog programs it has the same power as disjunctive stable model semantics., Comment: 20 pages