skip to main content
10.1109/LICS.2015.65acmconferencesArticle/Chapter ViewAbstractPublication PageslicsConference Proceedingsconference-collections
Article

On the Complexity of Temporal Equilibrium Logic

Published: 06 July 2015 Publication History
First page of PDF

References

[1]
P. Cabalar and G. Vega, "Temporal equilibrium logic: A first approach," in Proc. 11th EUROCAST, ser. LNCS 4739. Springer, 2007, pp. 241-248.
[2]
P. Cabalar and S. Demri, "Automata-Based Computation of Temporal Equilibrium Models," in Proc. 21st LOPSTR, ser. LNCS 7225. Springer, 2011, pp. 57-72.
[3]
G. Brewka, T. Eiter, and M. Truszczynski, "Answer set programming at a glance," Commun. ACM, vol. 54, no. 12, pp. 92-103, 2011.
[4]
D. Pearce, "A new logical characterisation of stable models and answer sets," in Proc. of NMELP'96, ser. LNCS 1216. Springer, 1996, pp. 57-70.
[5]
D. Pearce, "Equilibrium logic," Ann. Math. Artif. Intell., vol. 47, no. 1-2, pp. 3-41, 2006.
[6]
A. Heyting, "Die formalen Regeln der intuitionistischen Logik," in three parts, Sitzungsberichte der preussischen Akademie der Wissenschaften. English translation of Part I in Mancosu 1998: 311-327.
[7]
D. Pearce and A. Valverde, "Towards a first order equilibrium logic for nonmonotonic reasoning," in Proc. JELIA 2004, Springer LNCS 3229, 2004, pp. 147-160.
[8]
P. Cabalar, L. Fariñas del Cerro, D. Pearce, and A. Valverde, "A free logic for stable models with partial intensional functions," in Proc. JELIA 2014, Springer LNCS 8761, 2014, pp. 340-354.
[9]
J. de Bruijn, D. Pearce, A. Polleres, and A. Valverde, "Quantified equilibrium logic and hybrid rules," in Proc. Web Reasoning and Rule Systems, RR 2007, Springer LNCS 4524, 2007, pp. 58-72.
[10]
M. Fink and D. Pearce, "A logical semantics for description logic programs," in Proc. JELIA 2010, Springer LNCS 6341, 2010, pp. 156-168.
[11]
J. Mccarthy and P. J. Hayes, "Some philosophical problems from the standpoint of artificial intelligence," in Machine Intelligence. Edinburgh University Press, 1969, pp. 463-502.
[12]
H. A. Kautz, "The logic of persistence," in Proc. 5th AAAI, 1986, pp. 401-405.
[13]
A. Pnueli, "The temporal logic of programs," in Proc. 18th FOCS. IEEE Computer Society, 1977, pp. 46-57.
[14]
P. Cabalar and M. Diéguez, "Strong equivalence of nonmonotonic temporal theories," in Proc. 14th KR. AAAI Press, 2014.
[15]
P. Cabalar and M. Diéguez, "Stelp - A tool for temporal answer set programming," in Proc. 11th LPNMR, ser. LNCS 6645. Springer, 2011, pp. 370-375.
[16]
A. Sistla and E. Clarke, "The Complexity of Propositional Linear Temporal Logics," J. ACM, vol. 32, no. 3, pp. 733-749, 1985.
[17]
L. Bozzelli and D. Pearce, "On the complexity of temporal equilibrium logic," CoRR, vol. abs/1503.00043, 2015.
[18]
R. Fagin, J. Halpern, and M. Vardi, Reasoning about knowledge. MIT press Cambridge, 1995, vol. 4.
[19]
L. Giordano, A. Martelli, and D. T. Dupré, "Reasoning about actions with temporal answer sets," TPLP, vol. 13, no. 2, pp. 201-225, 2013.
[20]
F. Aguado, G. Pérez, and C. Vidal, "Integrating temporal extensions of answer set programming," in Proc. 12th LPNMR, ser. LNCS 8148. Springer, 2013, pp. 23-35.
[21]
P. Ferraris, "Answer Sets for Propositional Theories," in Proc. 8th LPNMR, ser. LNCS 3662. Springer, 2005, pp. 119-131.
[22]
T. Eiter and G. Gottlob, "On the Computational Cost of Disjunctive Logic Programming: Propositional Case," Ann. Math. Artif. Intell., vol. 15, no. 3-4, pp. 289-323, 1995.
[23]
D. Harel, Algorithmics: The Spirit of Computing. Wesley, 2nd edition, 1992.
[24]
P. V. E. Boas, "The Convenience of Tilings," in In Complexity, Logic, and Recursion Theory. Marcel Dekker Inc, 1997, pp. 331-363.
[25]
S. Demri and P. Schnoebelen, "The Complexity of Propositional Linear Temporal Logics in Simple Cases," Inf. Comput., vol. 174, no. 1, pp. 84-103, 2002.
[26]
M. Y. Vardi and P. Wolper, "Reasoning about infinite computations," Inf. Comput., vol. 115, no. 1, pp. 1-37, 1994.
[27]
A. P. Sistla, M. Y. Vardi, and P. Wolper, "The complementation problem for Büchi automata with appplications to temporal logic," Theor. Comput. Sci., vol. 49, pp. 217-237, 1987.
[28]
S. Safra, "Complexity of automata on infinite objects," 1989, PhD thesis, Weizmann Institute of Science, Rehovot, 1989.
[29]
P. Cabalar, "A normal form for linear temporal equilibrium logic," in Proc. 12th JELIA, ser. LNCS 6341. Springer, 2010, pp. 64-76.
[30]
F. Aguado, P. Cabalar, M. Diéguez, G. Pérez, and C. Vidal, "Temporal equilibrium logic: a survey," Journal of Applied Non-Classical Logics, vol. 23, no. 1-2, pp. 2-24, 2013.

Cited By

View all
  • (2024)Contracted temporal equilibrium logicProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2024/21(221-231)Online publication date: 2-Nov-2024
  • (2024)Computational aspects of progression for temporal equilibrium logicProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/370(3342-3350)Online publication date: 3-Aug-2024
  • (2016)Equivalent stream reasoning programsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060750(929-935)Online publication date: 9-Jul-2016
  1. On the Complexity of Temporal Equilibrium Logic

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    LICS '15: Proceedings of the 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
    July 2015
    776 pages
    ISBN:9781479988754

    Sponsors

    In-Cooperation

    • EACSL: European Association for Computer Science Logic

    Publisher

    IEEE Computer Society

    United States

    Publication History

    Published: 06 July 2015

    Check for updates

    Qualifiers

    • Article

    Acceptance Rates

    Overall Acceptance Rate 215 of 622 submissions, 35%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)3
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 13 Jan 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Contracted temporal equilibrium logicProceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning10.24963/kr.2024/21(221-231)Online publication date: 2-Nov-2024
    • (2024)Computational aspects of progression for temporal equilibrium logicProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/370(3342-3350)Online publication date: 3-Aug-2024
    • (2016)Equivalent stream reasoning programsProceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence10.5555/3060621.3060750(929-935)Online publication date: 9-Jul-2016

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media