Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T01:16:29.119Z Has data issue: false hasContentIssue false
  • English
  • Français

Incremental maintenance of overgrounded logic programs with tailored simplifications

Published online by Cambridge University Press:  21 September 2020

Giovambattista Ianni ,
Francesco Pacenza Open the ORCID record for Francesco Pacenza [Opens in a new window]  and
Jessica Zangari Open the ORCID record for Jessica Zangari [Opens in a new window]
Giovambattista Ianni
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Rende, Italy (e-mail: [email protected]) - https://www.mat.unical.it
Francesco Pacenza
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Rende, Italy (e-mail: [email protected]) - https://www.mat.unical.it
Jessica Zangari
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Rende, Italy (e-mail: [email protected]) - https://www.mat.unical.it
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Keywords

Knowledge Representation and ReasoningAnswer Set ProgrammingStream ReasoningGroundingInstantiation of Logic ProgramsOvergrounding
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 20 , Issue 5: 36th International Conference on Logic Programming Special Issue I , September 2020 , pp. 719 - 734
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

*

We thank the reviewers of this paper, whose constructive comments helped to improve our work. This work has been partially supported by MIUR under project “Declarative Reason- ing over Streams” (CUP H24I17000080001) – PRIN 2017, by MISE under project “S2BDW” (F/050389/01-03/X32) – “Horizon2020” PON I&C2014-20, by Regione Calabria under project “DLV Large Scale” (CUP J28C17000220006) – POR Calabria 2014-20.

References

Alviano, M., Dodaro, C., Leone, N., and Ricca, F. Advances in WASP. In LPNMR 2015, Volume 9345 of LNCS, pp. 40–54. Springer.Google Scholar
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.Google Scholar
Beck, H., Dao-Tran, M., and Eiter, T. 2018. LARS: A logic-based framework for analytic reasoning over streams. Artificial Intelligence 261, 16–70.Google Scholar
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.Google Scholar
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.Google Scholar
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.CrossRefGoogle Scholar
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.Google Scholar
Calimeri, F., Fuscà, D., Perri, S., and Zangari, J. 2017. I-DLV: The New Intelligent Grounder of DLV. Intelligenza Artificiale 11, 1, 5–20.Google Scholar
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.Google Scholar
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.Google Scholar
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.CrossRefGoogle Scholar
Dal Palù, A., Dovier, A., Pontelli, E., and Rossi, G. 2009. GASP: answer set programming with lazy grounding. Fundamenta Informaticae 96, 3, 297–322.CrossRefGoogle Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
Gebser, M., Kaufmann, B., and Schaub, T. Conflict-driven answer set solving: From theory to practice. Artificial Intelligence 187, 52–89.Google Scholar
Kaufmann, B., Leone, N., Perri, S., and Schaub, T. 2016. Grounding and solving in answer set programming. AI Magazine 37, 3, 25–32.CrossRefGoogle Scholar
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.Google Scholar
Leone, N., Rullo, P., and Scarcello, F. 1997. Disjunctive stable models: Unfounded sets, fixpoint semantics, and computation. Information and Computation 135, 2, 69–112.CrossRefGoogle Scholar
Motik, B., Nenov, Y., Piro, R., and Horrocks, I. 2019. Maintenance of datalog materialisations revisited. Artificial Intelligence 269, 76–136.Google Scholar
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.Google Scholar
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.Google Scholar
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.Google Scholar
Truszczynski, M. and Woltran, S. 2009. Relativized hyperequivalence of logic programs for modular programming. Theory and Practice of Logic Programming 9, 6, 781–819.CrossRefGoogle Scholar
Supplementary material: PDF

Ianni et al. supplementary material

Ianni et al. supplementary material 1

Download Ianni et al. supplementary material(PDF)
PDF 146.5 KB
Supplementary material: File

Ianni et al. supplementary material

Ianni et al. supplementary material 2

Download Ianni et al. supplementary material(File)
File 125.7 KB