Forgetting in Modular Answer Set Programming

Ricardo Gonçalves, Tomi Janhunen, Matthias Knorr, João Leite, Stefan WoltranAAAI 2019 · DOI

Abstract

In the field of Answer Set Programming (ASP), "forgetting"—the process of eliminating specific variables while preserving the logical consequences of a program—is a critical yet mathematically challenging task. Traditional approaches often fail due to the strict requirements of Strong Persistence. This paper introduces a novel framework for forgetting within Modular ASP by shifting the focus to Uniform Persistence. By utilizing the $F_{UP}$ operator and module reconfiguration techniques, the authors demonstrate that forgetting is always achievable, bypassing previous impossibility results and ensuring the continued validity of the Module Theorem.

Introduction

In software engineering and knowledge representation, the ability to simplify complex systems by hiding internal logic or removing redundant "middle-man" variables is essential. This process, known as "forgetting," allows for cleaner interfaces and more efficient reasoning. However, in Answer Set Programming (ASP)—a declarative logic programming paradigm used for complex combinatorial problems—forgetting is notoriously difficult.

The difficulty stems from ASP's non-monotonic nature: adding new information can invalidate previous conclusions. Consequently, removing a variable requires ensuring that the relationships between the remaining variables remain unchanged under all future conditions. Historically, researchers sought "Strong Persistence," which requires a program to remain equivalent even if arbitrary new rules are added. Recent findings, however, have proven that satisfying Strong Persistence while forgetting is often mathematically impossible for many ASP programs.

The Shift to Uniform Persistence

This paper proposes a paradigm shift. Instead of pursuing the overly restrictive Strong Persistence, the authors argue that Uniform Persistence (UP) is the appropriate standard for Modular ASP. In a modular context, components typically interact by exchanging sets of facts (inputs) rather than raw logic rules. Uniform Persistence ensures that a program behaves identically when any set of facts is added, a requirement that is both more practical and mathematically flexible.

To implement this, the authors introduce the $F_{UP}$ operator. This operator is grounded in HT-models (the "Here-and-There" logic), which provide the semantic foundation for ASP. The $F_{UP}$ operator systematically maps the models of an original program to a simplified version that excludes the forgotten atoms, ensuring the core logic remains intact.

Forgetting in a Modular Framework

Modular ASP breaks large programs into independent components (modules) that communicate via defined input/output interfaces. While this structure aids in managing complexity, it introduces a new challenge: the Module Theorem. This theorem allows researchers to combine the results of individual modules to understand the global system.

The authors identify that forgetting can be "fragile"—if a variable shared between two modules is forgotten in one but retained in another, the compositionality of the system breaks. To resolve this, the paper introduces Module Reconfiguration. This technique involves merging or splitting modules to ensure that forgotten atoms do not disrupt the global logic. By identifying "strongly connected components" of modules that share forgotten atoms, the authors provide a formal method to restore the Module Theorem's applicability.

Key Insights and Results

The most significant contribution of this work is the Existence Proof. The authors demonstrate that for any ASP program and any set of atoms, a forgetting result satisfying Uniform Persistence always exists. This effectively circumvents the impossibility results that have hindered the field for years.

Other key findings include:

  • Universal Applicability: The $F_{UP}$ operator handles all atom types—input, output, and hidden (internal) variables—making it a versatile tool for system simplification.
  • Preservation of Properties: The operator is "closed" for specific program classes, such as Horn programs, and preserves standard semantic equivalences.
  • Computational Complexity: The paper identifies the complexity of determining if a program is a valid result of forgetting at the $\Pi^P_3$ level of the polynomial hierarchy.

Limitations and Future Directions

While the paper provides a robust semantic framework, it acknowledges certain limitations. The current reconfiguration strategy requires "white-box" access to the internal rules of modules. In "black-box" scenarios, where only the interface is accessible, these techniques may not apply.

Furthermore, the current work is primarily semantic, focusing on models rather than the rules themselves. A crucial next step for practical application is the development of syntactic operators—algorithms that can automatically rewrite the text of logic rules to perform forgetting. Expanding this framework to other modular ASP paradigms also remains a promising area for future research.

Conclusion

By moving from Strong to Uniform Persistence, this research provides a viable path forward for simplifying modular logic programs. The introduction of the $F_{UP}$ operator and reconfiguration techniques ensures that forgetting can be performed without sacrificing the mathematical integrity or the compositional nature of Answer Set Programming.

Summary updated

BibTeX
@inproceedings{goncalves2019forgetting,
  author = {Ricardo Gonçalves and Tomi Janhunen and Matthias Knorr and João Leite and Stefan Woltran},
  title = {{Forgetting in Modular Answer Set Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012843},
}
Figure