The ability to abstract is important in AI systems and in problem solving, as generalizing over irrelevant details facilitates finding solutions. In the context of Answer Set Programming (ASP), abstraction has been recently investigated with a focus on the omission of unnecessary details, which is related to forgetting, as well as on clustering vocabulary of similar concepts into a common abstract representation. In the latter case, a characterization has been provided that identifies when such abstraction is possible without affecting the answer sets under the addition of any set of facts, in the spirit of uniform equivalence and aligned with the ASP methodology where a general problem encoding is used with varying instances. However, when this characterization fails, no abstraction is possible, and even if it succeeds, computing an abstracted program syntactically is only possible for a limited subclass of programs. In this paper, we consider that not all kinds of facts are required to be added in general, and investigate under which conditions such abstraction is indeed always possible as well as when and how to compute abstracted programs, generalizing at the same time (compared to related work) to a larger class of programs with wider applicability.

Generalization is an important ability that allows humans to tackle complex problems by identifying common problem structures and omitting irrelevant details. Whereas such ability comes naturally to humans, it has proved challenging to establish within AI systems. Although different research communities have tackled this challenge, their focus has usually been set on developing efficient algorithms for concrete problems, and a general theoretical understanding of the generalization ability is still lacking. In the context of Answer Set Programming (ASP), a well-established knowledge representation and reasoning paradigm for solving highly combinatorial search problems, research on generalization has primarily focused on forgetting and projection, two related operations that aim at the omission of irrelevant details, while abstraction, an operation that aims at providing a higher-level view on the common solution and problem structures, has largely been overlooked. In this paper, we develop the theoretical foundation for generalized reasoning through abstraction in ASP, focusing on the notion of abstraction through vocabulary clustering. We formally characterize when abstraction is possible, semantically define the desired result, investigate syntactic operators to obtain such abstractions, and study the computational complexity of this problem.

Boolean regulatory networks are used to represent complex biological processes, modelling the interactions of biological compounds, such as proteins or genes, with each other and with other substances in a cell. Creating and maintaining computational models of these networks is crucial for comprehending corresponding cellular processes, as they allow reproducing known behaviours and testing new hypotheses and predictions in silico. In this context, model revision focuses on validating and (if necessary) repairing existing models based on new experimental data. However, model revision is commonly performed manually, which is inefficient and prone to error, and the few existing automated solutions either only apply to simpler networks or are limited in their revision process, since they may not be able to produce a solution within a reasonable time frame or miss the optimal solution. In this paper, we develop a solution for revising logical models of Boolean regulatory networks, able to find repairs that are consistent with provided, possibly incomplete experimental data, and minimal w.r.t. the differences to the original network. We show that our solution can be used to revise different real-world Boolean logical models very efficiently, surpassing a previous solution in terms of solved instances and with a considerable margin w.r.t. processing time.

Abstract Forgetting – or variable elimination – is an operation that allows the removal, from a knowledge base, ofmiddlevariables no longer deemed relevant. In recent years, many different approaches for forgetting in Answer Set Programming have been proposed, in the form of specific operators, or classes of such operators, commonly following different principles and obeying different properties. Each such approach was developed to address some particular view on forgetting, aimed at obeying a specific set of properties deemed desirable in such view, but a comprehensive and uniform overview of all the existing operators and properties is missing. In this article, we thoroughly examine existing properties and (classes of) operators for forgetting in Answer Set Programming, drawing a complete picture of the landscape of these classes of forgetting operators, which includes many novel results on relations between properties and operators, including considerations on concrete operators to compute results of forgetting and computational complexity. Our goal is to provide guidance to help users in choosing the operator most adequate for their application requirements.

Modular programming facilitates the creation and reuse of large software, and has recently gathered considerable interest in the context of Answer Set Programming (ASP). In this setting, forgetting, or the elimination of middle variables no longer deemed relevant, is of importance as it allows one to, e.g., simplify a program, make it more declarative, or even hide some of its parts without affecting the consequences for those parts that are relevant. While forgetting in the context of ASP has been extensively studied, its known limitations make it unsuitable to be used in Modular ASP. In this paper, we present a novel class of forgetting operators and show that such operators can always be successfully applied in Modular ASP to forget all kinds of atoms – input, output and hidden – overcoming the impossibility results that exist for general ASP. Additionally, we investigate conditions under which this class of operators preserves the module theorem in Modular ASP, thus ensuring that answer sets of modules can still be composed, and how the module theorem can always be preserved if we further allow the reconfiguration of modules.

Abstract Whereas the operation of forgetting has recently seen a considerable amount of attention in the context of Answer Set Programming (ASP), most of it has focused on theoretical aspects, leaving the practical issues largely untouched. Recent studies include results about what sets of properties operators should satisfy, as well as the abstract characterization of several operators and their theoretical limits. However, no concrete operators have been investigated. In this paper, we address this issue by presenting the first concrete operator that satisfies strong persistence – a property that seems to best capture the essence of forgetting in the context of ASP – whenever this is possible, and many other important properties. The operator is syntactic, limiting the computation of the forgetting result to manipulating the rules in which the atoms to be forgotten occur, naturally yielding a forgetting result that is close to the original program.

Abstract Among the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming,strong persistencenaturally captures its essence. Recently, it has been shown that it is not always possible to forget a set of atoms from a program while obeying this property, and a precise criterion regarding what can be forgotten has been presented, accompanied by a class of forgetting operators that return the correct result when forgetting is possible. However, it is an open question what to do when we have to forget a set of atoms, but cannot without violating this property. In this paper, we address this issue and investigate three natural alternatives to forget when forgetting without violating strong persistence is not possible, which turn out to correspond to the different possible relaxations of the characterization of strong persistence. Additionally, we discuss their preferable usage, shed light on the relation between forgetting and notions of relativized equivalence established earlier in the context of Answer Set Programming, and present a detailed study on their computational complexity.

Selectively forgetting information while preserving what matters the most is becoming an increasingly important issue in many areas, including in knowledge representation and reasoning. Depending on the application at hand, forgetting operators are defined to obey different sets of desirable properties. Of the myriad of desirable properties discussed in the context of forgetting in Answer Set Programming, strong persistence, which imposes certain conditions on the correspondence between the answer sets of the program pre-and post-forgetting, and a certain independence from non-forgotten atoms, seems to best capture its essence, and be desirable in general. However, it has remained an open problem whether it is always possible to forget a set of atoms from a program while obeying strong persistence. In this paper, after showing that it is not always possible to forget a set of atoms from a program while obeying this property, we move forward and precisely characterise what can and cannot be forgotten from a program, by presenting a necessary and sufficient criterion. This characterisation allows us to draw some important conclusions regarding the existence of forgetting operators for specific classes of logic programs, to characterise the class of forgetting operators that achieve the correct result whenever forgetting is possible, and investigate the related question of determining what we can forget from some specific logic program.

Managed Multi-Context Systems (mMCSs) provide a general framework for integrating knowledge represented in heterogeneous KR formalisms. However, mMCSs are essentially static as they were not designed to run in a dynamic scenario. In this paper, we introduce evolving Multi-Context Systems (eMCSs), a general and flexible framework which inherits from mMCSs the ability to integrate knowledge represented in heterogeneous KR formalisms, and at the same time is able to both react to, and reason in the presence of commonly temporary dynamic observations, and evolve by incorporating new knowledge. We show that eMCSs are indeed very general and expressive enough to capture several existing KR approaches that model dynamics of knowledge.

In open environments, agents need to reason with knowledge from various sources, represented in different languages. Multi-Context Systems (MCSs) allow for the integration of knowledge from different heterogeneous sources in an effective and modular way. Whereas most knowledge bases (contexts) typically considered within an MCS are written in some description logic or some non-monotonic rule-based language, sometimes more expressive languages that combine the features of both these paradigms are necessary, such as Hybrid MKNF. However, since agents may not have access to specialized reasoners for contexts using all these languages, it proves useful to have tools that equivalently simplify or transform a given MCS into another MCS that only uses the reasoners that are available. In this article, we thoroughly investigate the relation between MCSs and Hybrid MKNF. We provide a number of transformations that show that Hybrid MKNF knowledge bases can be embedded into MCSs without the need for specific MKNF reasoners. To complete the picture, we also show that when an MKNF reasoner is available, it can be used to handle several description logic and rule contexts joined into a single MKNF context. Furthermore, we show that we can encapsulate the non-monotonic transfer of information between different contexts in one rule language context, allowing e.g. the use of external non-monotonic reasoners.

Hybrid MKNF knowledge bases are one of the most prominent tightly integrated combinations of open-world ontology languages with closed-world (nonmonotonic) rule paradigms. Based on the logic of minimal knowledge and negation as failure (MKNF), the definition of Hybrid MKNF is parametric on the description logic (DL) underlying the ontology language, in the sense that nonmonotonic rules can extend any decidable DL language. Two related semantics have been defined for Hybrid MKNF: one that is based on the Stable Model Semantics for logic programs and one on the Well-Founded Semantics (WFS). Under WFS, the definition of Hybrid MKNF relies on a bottom-up computation that has polynomial data complexity whenever the DL language is tractable. Here we define a general query-driven procedure for Hybrid MKNF that is sound with respect to the stable model-based semantics, and sound and complete with respect to its WFS variant. This procedure is able to answer a slightly restricted form of conjunctive queries, and is based on tabled rule evaluation extended with an external oracle that captures reasoning within the ontology. Such an (abstract) oracle receives as input a query along with knowledge already derived, and replies with a (possibly empty) set of atoms, defined in the rules, whose truth would suffice to prove the initial query. With appropriate assumptions on the complexity of the abstract oracle, the general procedure maintains the data complexity of the WFS for Hybrid MKNF knowledge bases. To illustrate this approach, we provide a concrete oracle for EL + , a fragment of the lightweight DL EL ++ . Such an oracle has practical use, as EL ++ is the language underlying OWL 2 EL, which is part of the W3C recommendations for the Semantic Web, and is tractable for reasoning tasks such as subsumption. We show that query-driven Hybrid MKNF preserves polynomial data complexity when using the EL + oracle and WFS.

A general top-down algorithmization for the Well-Founded MKNF Semantics – a semantics for combining rules and ontologies – was recently defined based on an extension of SLG resolution for Logic Programming with an abstract oracle to the parametric ontology language. Here we provide a concrete oracle with practical usage, namely for ℰℒ+which is tractable for reasoning tasks like subsumption. We show that the defined oracle remains tractable (wrt. data complexity) so that the combined (query-driven) approach of non-monotonic rules with that oracle is tractable as well.

With the advent of the Semantic Web, the question becomes important how to best combine open-world based ontology languages, like OWL, with closed-world rules paradigms. One of the most mature proposals for this combination is known as Hybrid MKNF knowledge bases [11], which is based on an adaptation of the stable model semantics to knowledge bases consisting of ontology axioms and rules. In this paper, we propose a well-founded semantics for such knowledge bases which promises to provide better efficiency of reasoning, which is compatible both with the OWL-based semantics and the traditional well-founded semantics for logic programs, and which surpasses previous proposals for such a well-founded semantics by avoiding some issues related to inconsistency handling.