Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-18T14:26:40.018Z Has data issue: false hasContentIssue false
  • English
  • Français

Temporal Answer Set Programming on Finite Traces

Published online by Cambridge University Press:  10 August 2018

PEDRO CABALAR ,
ROLAND KAMINSKI ,
TORSTEN SCHAUB Open the ORCID record for TORSTEN SCHAUB [Opens in a new window]  and
ANNA SCHUHMANN
PEDRO CABALAR
Affiliation:
University of Corunna, Spain
ROLAND KAMINSKI
Affiliation:
University of Potsdam, Germany
TORSTEN SCHAUB
Affiliation:
University of Potsdam, Germany
ANNA SCHUHMANN
Affiliation:
University of Potsdam, Germany
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper, we introduce an alternative approach to Temporal Answer Set Programming that relies on a variation of Temporal Equilibrium Logic (TEL) for finite traces. This approach allows us to even out the expressiveness of TEL over infinite traces with the computational capacity of (incremental) Answer Set Programming (ASP). Also, we argue that finite traces are more natural when reasoning about action and change. As a result, our approach is readily implementable via multi-shot ASP systems and benefits from an extension of ASP's full-fledged input language with temporal operators. This includes future as well as past operators whose combination offers a rich temporal modeling language. For computation, we identify the class of temporal logic programs and prove that it constitutes a normal form for our approach. Finally, we outline two implementations, a generic one and an extension of the ASP system clingo.

Under consideration for publication in Theory and Practice of Logic Programming (TPLP)

Type
Rapid Communication
Information
Theory and Practice of Logic Programming , Volume 18 , Special Issue 3-4: 34th International Conference on Logic Programming , July 2018 , pp. 406 - 420
Copyright
Copyright © Cambridge University Press 2018 

References

Aguado, F., Cabalar, P., Diéguez, M., Pérez, G., and Vidal, C. 2013. Temporal equilibrium logic: a survey. Journal of Applied Non-Classical Logics 23, 1–2, 2–24.Google Scholar
Bozzelli, L. and Pearce, D. 2015. On the complexity of temporal equilibrium logic. In Proceedings of the Thirtieth Annual Symposium on Logic in Computer Science (LICS'15). IEEE Computer Society Press, 645–656.Google Scholar
Cabalar, P. 2010. A normal form for linear temporal equilibrium logic. In Proceedings of the Twelfth European Conference on Logics in Artificial Intelligence (JELIA'10), Janhunen, T. and Niemelä, I., Eds. Lecture Notes in Artificial Intelligence, vol. 6341. Springer-Verlag, 64–76.Google Scholar
Cabalar, P. and Demri, S. 2011. Automata-based computation of temporal equilibrium models. In Proceedings of the Twenty-first International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR'11), Vidal, G., Ed. Lecture Notes in Computer Science, vol. 7225. Springer-Verlag, 57–72.Google Scholar
Cabalar, P. and Diéguez, M. 2011. STELP — a tool for temporal answer set programming. In Proceedings of the Eleventh International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'11), Delgrande, J. and Faber, W., Eds. Lecture Notes in Artificial Intelligence, vol. 6645. Springer-Verlag, 370–375.Google Scholar
Cabalar, P., Diéguez, M., and Vidal, C. 2015. An infinitary encoding of temporal equilibrium logic. Theory and Practice of Logic Programming 15, 4–5, 666–680.Google Scholar
De Giacomo, G. and Vardi, M. 2013. Linear temporal logic and linear dynamic logic on finite traces. See Rossi (2013), 854–860.Google Scholar
Emerson, E. 1990. Temporal and modal logic. In Handbook of Theoretical Computer Science, van Leeuwen, J., Ed. MIT Press, 995–1072.Google Scholar
Fages, F. 1994. Consistency of Clark's completion and the existence of stable models. Journal of Methods of Logic in Computer Science 1, 51–60.Google Scholar
Gabbay, D. 1987. The declarative past and imperative future: Executable temporal logic for interactive systems. In Proceedings of the Conference on Temporal Logic in Specification, Banieqbal, B., Barringer, H., and Pnueli, A., Eds. Lecture Notes in Computer Science, vol. 398. Springer-Verlag, 409–448.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., and Schaub, T. 2018. Multi-shot ASP solving with clingo. Theory and Practice of Logic Programming. To appear.Google Scholar
Gebser, M., Kaminski, R., and Schaub, T. 2012. Gearing up for effective ASP planning. In Correct Reasoning: Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Erdem, E., Lee, J., Lierler, Y., and Pearce, D., Eds. Lecture Notes in Computer Science, vol. 7265. Springer-Verlag, 296–310.Google Scholar
Gelfond, M. and Lifschitz, V. 1998. Action languages. Electronic Transactions on Artificial Intelligence 3, 6, 193–210.Google Scholar
Heyting, A. 1930. Die formalen Regeln der intuitionistischen Logik. In Sitzungsberichte der Preussischen Akademie der Wissenschaften. Deutsche Akademie der Wissenschaften zu Berlin, 42-56. Reprint in Logik-Texte: Kommentierte Auswahl zur Geschichte der Modernen Logik, Akademie-Verlag, 1986.Google Scholar
Lee, J., Lifschitz, V., and Yang, F. 2013. Action language BC: Preliminary report. See Rossi (2013), 983–989.Google Scholar
Lifschitz, V. 1999. Answer set planning. In Proceedings of the International Conference on Logic Programming (ICLP'99), de Schreye, D., Ed. MIT Press, 23–37.Google Scholar
Oikarinen, E. and Janhunen, T. 2006. Modular equivalence for normal logic programs. In Proceedings of the Seventeenth European Conference on Artificial Intelligence (ECAI'06), Brewka, G., Coradeschi, S., Perini, A., and Traverso, P., Eds. IOS Press, 412–416.Google Scholar
Pnueli, A. 1977. The temporal logic of programs. In Proceedings of the Eight-teenth Symposium on Foundations of Computer Science (FOCS'77). IEEE Computer Society Press, 46–57.Google Scholar
Rossi, F., Ed. 2013. Proceedings of the Twenty-third International Joint Conference on Artificial Intelligence (IJCAI'13). IJCAI/AAAI Press.Google Scholar
Sandewall, E. 1994. Features and fluents: the representation of knowledge about dynamical systems. Vol. 1. Oxford University Press, New York, NY, USA.Google Scholar
Tseitin, G. 1968. On the complexity of derivation in the propositional calculus. Zapiski nauchnykh seminarov LOMI 8, 234–259.Google Scholar