Abstract
We investigate expressiveness issues of Temporal Equilibrium Logic (TEL), a promising nonmonotonic logical framework for temporal reasoning. TEL shares the syntax of standard linear temporal logic LTL, but its semantics is an orthogonal combination of the LTL semantics with the nonmonotonic semantics of Equilibrium Logic. We establish that TEL is more expressive than LTL, and captures a strict subclass of \(\omega \)-regular languages. We illustrate the expressive power of \(\textsf {TEL} \) by showing that \(\textsf {LTL} \)-conformant planning, which is not expressible in \(\textsf {LTL} \), can be instead expressed in \(\textsf {TEL} \). Additionally, we provide a systematic study of the expressiveness comparison between the LTL semantics and the TEL semantics for various natural syntactical fragments.
An authors’ online version of this paper is available at https://www.dropbox.com/s/x0fnjzhjwira780/TEL%20Expression.pdf?dl=0. Its appendix includes proofs that are omitted here for lack of space.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
On both the initial situation and on the full effects of actions.
References
Aguado, F., Pérez, G., Vidal, C.: Integrating temporal extensions of answer set programming. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS (LNAI), vol. 8148, pp. 23–35. Springer, Heidelberg (2013). doi:10.1007/978-3-642-40564-8_3
Bozzelli, L., Pearce, D.: On the complexity of temporal equilibrium logic. In: Proceedings of 30th LICS, pp. 645–656. IEEE Computer Society (2015)
Brewka, G., Eiter, T., Truszczynski, M.: Answer set programming at a glance. Commun. ACM 54(12), 92–103 (2011)
Cabalar, P., Demri, S.: Automata-based computation of temporal equilibrium models. In: Vidal, G. (ed.) LOPSTR 2011. LNCS, vol. 7225, pp. 57–72. Springer, Heidelberg (2012). doi:10.1007/978-3-642-32211-2_5
Cabalar, P., Diéguez, M.: STeLP– a tool for temporal answer set programming. In: Delgrande, J.P., Faber, W. (eds.) LPNMR 2011. LNCS (LNAI), vol. 6645, pp. 370–375. Springer, Heidelberg (2011). doi:10.1007/978-3-642-20895-9_43
Cabalar, P., Diéguez, M.: Strong equivalence of non-monotonic temporal theories. In: Proceedings of 14th KR. AAAI Press (2014)
Cabalar, P., Cerro, L.F., Pearce, D., Valverde, A.: A free logic for stable models with partial intensional functions. In: Fermé, E., Leite, J. (eds.) JELIA 2014. LNCS (LNAI), vol. 8761, pp. 340–354. Springer, Heidelberg (2014). doi:10.1007/978-3-319-11558-0_24
Cabalar, P., Pérez Vega, G.: Temporal equilibrium logic: a first approach. In: Moreno Díaz, R., Pichler, F., Quesada Arencibia, A. (eds.) EUROCAST 2007. LNCS, vol. 4739, pp. 241–248. Springer, Heidelberg (2007). doi:10.1007/978-3-540-75867-9_31
Calvanese, D., De Giacomo, G., Vardi, M.Y.: Reasoning about actions and planning in LTL action theories. In: Proceedings of 8th KR, pp. 593–602. Morgan Kaufmann (2002)
Bruijn, J., Pearce, D., Polleres, A., Valverde, A.: Quantified equilibrium logic and hybrid rules. In: Marchiori, M., Pan, J.Z., Marie, C.S. (eds.) RR 2007. LNCS, vol. 4524, pp. 58–72. Springer, Heidelberg (2007). doi:10.1007/978-3-540-72982-2_5
Etessami, K.: Stutter-invariant languages, \(\omega \)-automata, and temporal logic. In: Halbwachs, N., Peled, D. (eds.) CAV 1999. LNCS, vol. 1633, pp. 236–248. Springer, Heidelberg (1999). doi:10.1007/3-540-48683-6_22
Fagin, R., Halpern, J., Vardi, M.: Reasoning About Knowledge, vol. 4. MIT Press, Cambridge (1995)
Ferraris, P.: Answer sets for propositional theories. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol. 3662, pp. 119–131. Springer, Heidelberg (2005). doi:10.1007/11546207_10
Fink, M., Pearce, D.: A logical semantics for description logic programs. In: Janhunen, T., Niemelä, I. (eds.) JELIA 2010. LNCS (LNAI), vol. 6341, pp. 156–168. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15675-5_15
Gelfond, M., Morales, A.: Encoding conformant planning in A-Prolog. In: Proceedings of DRT. LNCS. Springer (2004)
Giordano, L., Martelli, A., Dupré, D.T.: Reasoning about actions with temporal answer sets. TPLP 13(2), 201–225 (2013)
Heyting, A.: Die formalen Regeln der intuitionistischen Logik. In: Three Parts, Sitzungsberichte der preussischen Akademie der Wissenschaften, pp. 311–327 (2011). English translation of Part I in Mancosu
Kucera, A., Strejcek, J.: The stuttering principle revisited. Acta Informatica 41(7–8), 415–434 (2005)
Pearce, D.: A new logical characterisation of stable models and answer sets. In: Dix, J., Pereira, L.M., Przymusinski, T.C. (eds.) NMELP 1996. LNCS, vol. 1216, pp. 57–70. Springer, Heidelberg (1997). doi:10.1007/BFb0023801
Pearce, D.: Equilibrium logic. Ann. Math. Artif. Intell. 47(1–2), 3–41 (2006)
Pearce, D., Valverde, A.: Towards a first order equilibrium logic for nonmonotonic reasoning. In: Alferes, J.J., Leite, J. (eds.) JELIA 2004. LNCS (LNAI), vol. 3229, pp. 147–160. Springer, Heidelberg (2004). doi:10.1007/978-3-540-30227-8_15
Pnueli, A.: The temporal logic of programs. In: Proceedings of 18th FOCS, pp. 46–57. IEEE Computer Society (1977)
Sistla, A., Vardi, M., Wolper, P.: The complementation problem for Büchi automata with appplications to temporal logic. Theor. Comput. Sci. 49, 217–237 (1987)
Wu, Z.: On the expressive power of QLTL. In: Jones, C.B., Liu, Z., Woodcock, J. (eds.) ICTAC 2007. LNCS, vol. 4711, pp. 467–481. Springer, Heidelberg (2007). doi:10.1007/978-3-540-75292-9_32
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing AG
About this paper
Cite this paper
Bozzelli, L., Pearce, D. (2016). On the Expressiveness of Temporal Equilibrium Logic. In: Michael, L., Kakas, A. (eds) Logics in Artificial Intelligence. JELIA 2016. Lecture Notes in Computer Science(), vol 10021. Springer, Cham. https://doi.org/10.1007/978-3-319-48758-8_11
Download citation
DOI: https://doi.org/10.1007/978-3-319-48758-8_11
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-48757-1
Online ISBN: 978-3-319-48758-8
eBook Packages: Computer ScienceComputer Science (R0)