Incremental maintenance of overgrounded logic programs with tailored simplifications.

*(English)*Zbl 07284966Summary: The repeated execution of reasoning tasks is desirable in many applicative scenarios, such as stream reasoning and event processing. When using answer set programming in such contexts, one can avoid the iterative generation of ground programs thus achieving a significant payoff in terms of computing time. However, this may require some additional amount of memory and/or the manual addition of operational directives in the declarative knowledge base at hand. We introduce a new strategy for generating series of monotonically growing propositional programs. The proposed overgrounded programs with tailoring (OPTs) can be updated and reused in combination with consecutive inputs. With respect to earlier approaches, our tailored simplification technique reduces the size of instantiated programs. A maintained OPT slowly grows in size from an iteration to another while the update cost decreases, especially in later iterations. In this paper we formally introduce tailored embeddings, a family of equivalence-preserving ground programs which are at the theoretical basis of OPTs and we describe their properties. We then illustrate an OPT update algorithm and report about our implementation and its performance.

##### MSC:

68N17 | Logic programming |

##### Keywords:

knowledge representation and reasoning; answer set programming; stream reasoning; grounding; instantiation of logic programs; overgrounding
PDF
BibTeX
XML
Cite

\textit{G. Ianni} et al., Theory Pract. Log. Program. 20, No. 5, 719--734 (2020; Zbl 07284966)

Full Text:
DOI

##### References:

[1] | Alviano, M., Dodaro, C., Leone, N., and Ricca, F. Advances in WASP. In LPNMR 2015, Volume 9345 of LNCS, pp. 40-54. Springer. · Zbl 06504220 |

[2] | Beck, H., Bierbaumer, B., Dao-Tran, M., Eiter, T., Hellwagner, H., and Schekotihin, K. Stream reasoning-based control of caching strategies in CCN routers. In ICC 2017, pp. 1-6. IEEE. · Zbl 06658182 |

[3] | Beck, H., Dao-Tran, M., and Eiter, T.2018. LARS: A logic-based framework for analytic reasoning over streams. Artificial Intelligence 261, 16-70. · Zbl 1448.68395 |

[4] | Beck, H., Eiter, T., and Folie, C.2017. Ticker: A system for incremental ASP-based stream reasoning. Theory and Practice of Logic Programming 17, 5-6, 744-763. · Zbl 1422.68218 |

[5] | Bomanson, J., Janhunen, T., and Weinzierl, A. Enhancing lazy grounding with lazy normalization in answer-set programming. In AAAI 2019, pp. 2694-2702. AAAI Press. |

[6] | Calimeri, F., Cozza, S., Ianni, G., and Leone, N.2008. Computable functions in ASP: theory and implementation. In ICLP 2008, Volume 5366 of LNCS, pp. 407-424. Springer. · Zbl 1185.68150 |

[7] | Calimeri, F., Fuscà, D., Perri, S., and Zangari, J.2016. I-DLV: The New Intelligent Grounder of DLV. In AIIA, Volume 10037 of LNCS, pp. 192-207. Springer. |

[8] | Calimeri, F., Fuscà, D., Perri, S., and Zangari, J.2017. I-DLV: The New Intelligent Grounder of DLV. Intelligenza Artificiale 11, 1, 5-20. |

[9] | Calimeri, F., Germano, S., Ianni, G., Pacenza, F., Perri, S., and Zangari, J. Integrating rule-based AI tools into mainstream game development. In RuleML+RR 2018, Volume 11092 of LNCS, pp. 310-317. Springer. |

[10] | Calimeri, F., Ianni, G., Pacenza, F., Perri, S., and Zangari, J.2019. Incremental answer set programming with overgrounding. Theory and Practice of Logic Programming 19, 5-6, 957-973. · Zbl 1434.68555 |

[11] | Calimeri, F., Perri, S., and Zangari, J.2019. Optimizing answer set computation via heuristic-based decomposition. Theory and Practice of Logic Programming 19, 4, 603-628. |

[12] | Dal Palù, A., Dovier, A., Pontelli, E., and Rossi, G.2009. GASP: answer set programming with lazy grounding. Fundamenta Informaticae 96, 3, 297-322. · Zbl 1207.68118 |

[13] | Dell’Aglio, D., Valle, E. D., Van Harmelen, F., and Bernstein, A.2017. Stream reasoning: A survey and outlook. Data Science 1, 1-2, 59-83. |

[14] | Eiter, T., Ogris, P., and Schekotihin, K.2019. A distributed approach to LARS stream reasoning (system paper). Theory and Practice of Logic Programming 19, 5-6, 974-989. · Zbl 1434.68546 |

[15] | Faber, W., Leone, N., and Perri, S.2012. The intelligent grounder of DLV. In Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Volume 7265 of LNCS, pp. 247-264. Springer. · Zbl 1357.68032 |

[16] | Faber, W., Leone, N., and Pfeifer, G. Recursive aggregates in disjunctive logic programs: Semantics and complexity. In JELIA 2004, Volume 3229 of LNCS, pp. 200-212. Springer. · Zbl 1111.68380 |

[17] | Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T.Multi-shot ASP solving with clingo. Theory and Practice of Logic Programming 19, 1, 27-82. · Zbl 07107408 |

[18] | Gebser, M., Kaufmann, B., Neumann, A., and Schaub, T. Advanced preprocessing for answer set solving. In ECAI 2008, Volume 178 of FAIA, pp. 15-19. IOS Press. |

[19] | Gebser, M., Kaufmann, B., and Schaub, T. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence 187, 52-89. · Zbl 1251.68060 |

[20] | Kaufmann, B., Leone, N., Perri, S., and Schaub, T.2016. Grounding and solving in answer set programming. AI Magazine 37, 3, 25-32. |

[21] | Lefèvre, C., Béatrix, C., Stéphan, I., and Garcia, L.2017. Asperix, a first-order forward chaining approach for answer set computing. Theory and Practice of Logic Programming 17, 3, 266-310. · Zbl 1379.68075 |

[22] | Leone, N., Rullo, P., and Scarcello, F.1997. Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation. Information and Computation 135, 2, 69-112. · Zbl 0879.68019 |

[23] | Motik, B., Nenov, Y., Piro, R., and Horrocks, I.2019. Maintenance of datalog materialisations revisited. Artificial Intelligence 269, 76-136. · Zbl 07099190 |

[24] | Pérez-Liébana, D., Samothrakis, S., Togelius, J., Schaul, T., and Lucas, S. General video game AI: competition, challenges and opportunities. In AAAI 2016, pp. 4335-4337. AAAI Press. |

[25] | Saribatur, Z. G., Patoglu, V., and Erdem, E.2019. Finding optimal feasible global plans for multiple teams of heterogeneous robots using hybrid reasoning: an application to cognitive factories. Autonomous Robots 43, 1, 213-238. |

[26] | Suchan, J., Bhatt, M., Walega, P. A., Schultz, C. P. L. Visual explanation by high-level abduction: On answer-set programming driven reasoning about moving objects. In AAAI 2018, pp. 1965-1972. AAAI Press. |

[27] | Truszczynski, M. and Woltran, S.2009. Relativized hyperequivalence of logic programs for modular programming. Theory and Practice of Logic Programming 9, 6, 781-819. · Zbl 1184.68163 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.