Document Open Access Logo

On the Decidability of a Fragment of preferential LTL

Authors Anasse Chafik, Fahima Cheikh-Alili, Jean-François Condotta, Ivan Varzinczak

PDF
Thumbnail PDF

File

LIPIcs.TIME.2020.19.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Author Details

Anasse Chafik
  • CRIL, University of Artois & CNRS, Arras, France
Fahima Cheikh-Alili
  • CRIL, University of Artois & CNRS, Arras, France
Jean-François Condotta
  • CRIL, University of Artois & CNRS, Arras, France
Ivan Varzinczak
  • CRIL, University of Artois & CNRS, Arras, France

Cite As Get BibTex

Anasse Chafik, Fahima Cheikh-Alili, Jean-François Condotta, and Ivan Varzinczak. On the Decidability of a Fragment of preferential LTL. In 27th International Symposium on Temporal Representation and Reasoning (TIME 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 178, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.TIME.2020.19

Abstract

Linear Temporal Logic (LTL) has found extensive applications in Computer Science and Artificial Intelligence, notably as a formal framework for representing and verifying computer systems that vary over time. Non-monotonic reasoning, on the other hand, allows us to formalize and reason with exceptions and the dynamics of information. The goal of this paper is therefore to enrich temporal formalisms with non-monotonic reasoning features. We do so by investigating a preferential semantics for defeasible LTL along the lines of that extensively studied by Kraus et al. in the propositional case and recently extended to modal and description logics. The main contribution of the paper is a decidability result for a meaningful fragment of preferential LTL that can serve as the basis for further exploration of defeasibility in temporal formalisms.

Subject Classification

ACM Subject Classification
  • Theory of computation → Modal and temporal logics
Keywords
  • Knowledge Representation
  • non-monotonic reasoning
  • temporal logic

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. O. Arieli and A. Avron. General patterns for nonmonotonic reasoning: From basic entailments to plausible relations. Logic Journal of the IGPL, 8:119-148, 2000. Google Scholar
  2. M. Ben-Ari. Mathematical Logic for Computer Science, third edition. Springer, 2012. Google Scholar
  3. K. Britz, T. Meyer, and I. Varzinczak. Preferential reasoning for modal logics. Electronic Notes in Theoretical Computer Science, 278:55-69, 2011. Proceedings of the 7th Workshop on Methods for Modalities and the 4th Workshop on Logical Aspects of Multi-Agent Systems. URL: https://doi.org/10.1016/j.entcs.2011.10.006.
  4. K. Britz, T. Meyer, and I. Varzinczak. Semantic foundation for preferential description logics. In Dianhui Wang and Mark Reynolds, editors, AI 2011: Advances in Artificial Intelligence, pages 491-500, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg. Google Scholar
  5. K. Britz and I. Varzinczak. From KLM-style conditionals to defeasible modalities, and back. Journal of Applied Non-Classical Logics, 28(1):92-121, 2018. URL: https://doi.org/10.1080/11663081.2017.1397325.
  6. K. Britz and I. Varzinczak. Preferential tableaux for contextual defeasible ALC. In S. Cerrito and A. Popescu, editors, Proceedings of the 28th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABLEAUX), number 11714 in LNCS, pages 39-57. Springer, 2019. Google Scholar
  7. D. M. Gabbay. Theoretical foundations for non-monotonic reasoning in expert systems. In Krzysztof R. Apt, editor, Logics and Models of Concurrent Systems, pages 439-457, Berlin, Heidelberg, 1985. Springer Berlin Heidelberg. Google Scholar
  8. D. M. Gabbay. The declarative past and imperative future: Executable temporal logic for interactive systems. In B. Banieqbal, H. Barringer, and A. Pnueli, editors, Temporal Logic in Specification, Altrincham, UK, April 8-10, 1987, Proceedings, volume 398 of Lecture Notes in Computer Science, pages 409-448. Springer, 1987. URL: https://doi.org/10.1007/3-540-51803-7_36.
  9. L. Giordano, V. Gliozzi, N. Olivetti, and G.L. Pozzato. Preferential description logics. In N. Dershowitz and A. Voronkov, editors, Logic for Programming, Artificial Intelligence, and Reasoning (LPAR), number 4790 in LNAI, pages 257-272. Springer, 2007. Google Scholar
  10. L. Giordano, V. Gliozzi, N. Olivetti, and G.L. Pozzato. Analytic tableaux calculi for KLM logics of nonmonotonic reasoning. ACM Transactions on Computational Logic, 10(3):18:1-18:47, 2009. Google Scholar
  11. R. Goré. Tableau methods for modal and temporal logics. In M. D'Agostino, D.M. Gabbay, R. Hähnle, and J. Posegga, editors, Handbook of Tableau Methods, pages 297-396. Kluwer Academic Publishers, 1999. Google Scholar
  12. S. Kraus, D. Lehmann, and M. Magidor. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence, 44:167-207, 1990. Google Scholar
  13. N. Laverny and J. Lang. From knowledge-based programs to graded belief-based programs, part i: On-line reasoning*. Synthese, 147(2):277-321, November 2005. URL: https://doi.org/10.1007/s11229-005-1350-1.
  14. D. Makinson. How to Go Nonmonotonic, pages 175-278. Springer Netherlands, Dordrecht, 2005. URL: https://doi.org/10.1007/1-4020-3092-4_3.
  15. A. Pnueli. The temporal logic of programs. In 18th Annual Symposium on Foundations of Computer Science (sfcs 1977), pages 46-57, October 1977. URL: https://doi.org/10.1109/SFCS.1977.32.
  16. Y. Shoham. A semantical approach to nonmonotic logics. In Proceedings of the Symposium on Logic in Computer Science (LICS '87), Ithaca, New York, USA, June 22-25, 1987, pages 275-279, 1987. Google Scholar
  17. Y. Shoham. Reasoning about Change: Time and Causation from the Standpoint of Artificial Intelligence. MIT Press, 1988. Google Scholar
  18. A. P. Sistla and E. M. Clarke. The complexity of propositional linear temporal logics. J. ACM, 32(3):733-749, July 1985. URL: https://doi.org/10.1145/3828.3837.
  19. P. Wolper. Temporal logic can be more expressive. Information and Control, 56(1):72-99, 1983. URL: https://doi.org/10.1016/S0019-9958(83)80051-5.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact