Search papers, labs, and topics across Lattice.
This paper revisits the use of answer set programming (ASP) for term extraction from e-graphs, addressing shortcomings from a previous attempt by Philip Zucker. By refining the ASP encoding, the authors demonstrate that it achieves efficiency comparable to optimized ILP-based exact DAG extraction methods while also identifying additional optimal extractions in complex instances. The findings suggest a promising synergy between ASP and Datalog, opening avenues for enhanced extraction capabilities.
ASP can rival traditional ILP methods in e-graph extraction efficiency while uncovering previously hidden optimal solutions.
Three years ago, Philip Zucker posted an attempt to use answer set programming (ASP) for term extraction from e-graphs Although the task is NP-hard and ASP offers a natural modelling of e-graph terms, the initial attempt did not yield convincing results. From the aspect of practical ASP users, we first pinpoint the way to make ASP work and work well on the task of e-graph extraction. The initial results show the na茂ve ASP encoding is comparable on efficiency to the well-optimised ILP-based exact DAG extraction in the extraction-gym, and find several extra optimal extraction on the complex instances. This leads us to a further agenda: with the "better together of egg+Datalog", is there a better "better together" by having ASP as a more powerful Datalog? We discuss the potential benefit from each other.
NUS