Proceedings

Linear Temporal Logic and Linear Dynamic Logic on Finite Traces

Download BibTeX Cite

Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence. Pages 854-859.

© 2013 International Joint Conferences on Artificial Intelligence

Abstract

In this paper we look into the assumption of interpreting LTL over finite traces. In particular we show that LTLf, i.e., LTL under this assumption, is less expressive than what might appear at first sight, and that at essentially no computational cost one can make a significant increase in expressiveness while maintaining the same intuitiveness of LTLf. Indeed, we propose a logic, LDLf for Linear Dynamic Logic over finite traces, which borrows the syntax from Propositional Dynamic Logic PDL, but is interpreted over finite traces. Satisfiability, validity and logical implication (as well as model checking) for LDLf are PSPACE-complete as for LTLf (and LTL).

  1. R. Armoni, L. Fix, A. Flaisher, R. Gerth, B. Ginsburg, T. Kanza, A. Landver, S. Mador-Haim, E. Singerman, A. Tiemeyer, M. Y. Vardi, and Y. Zbar. The forspec tempo- ral logic: A new temporal property-specification language. In TACAS, 2002.
  2. F. Bacchus and F. Kabanza. Planning for temporally extended goals. In AAAI, 1996.
  3. F. Bacchus and F. Kabanza. Using temporal logics to express search control knowledge for planning. Artif. Intell., 116(1- 2):123-191, 2000.
  4. C. Baier and J.-P. Katoen. Principles of Model Checking. MIT Press, 2008.
  5. M. Bienvenu, C. Fritz, and S. A. McIlraith. Planning with qualitative temporal preferences. In KR, 2006.
  6. M. Bienvenu, C. Fritz, and S. A. McIlraith. Specifying and computing preferred plans. Artif. Intell., 175(7-8):1308-1345, 2011.
  7. R. Bloem, A. Cimatti, I. Pill, M. Roveri, and S. Semprini. Sym- bolic implementation of alternating automata. Implementation and Application of Automata, LNCS 4094, 2006.
  8. J. A. Brzozowski and E. L. Leiss. On equations for regular languages, finite automata, and sequential networks. Theor. Comput. Sci., 10:19-35, 1980.
  9. J. R. Büchi. Weak second-order arithmetic and finite automata. Zeit. Math. Logik. Grund. Math., 6:66-92, 1960.
  10. T. Bylander. The computational complexity of propositional STRIPS planning. Artif. Intell., 69(1-2):165-204, 1994.
  11. D. Calvanese, G. De Giacomo, and M. Y. Vardi. Reasoning about actions and planning in LTL action theories. In KR, 2002.
  12. A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. Alterna- tion. Journal of the ACM (JACM), 28(1), Jan. 1981.
  13. G. De Giacomo and M. Y. Vardi. Automata-theoretic approach to planning for temporally extended goals. In ECP, 1999.
  14. V. Diekert and P. Gastin. First-order definable languages. In Logic and automata: history and perspectives. Amsterdam University Press, 2008.
  15. C. Eisner and D. Fisman. A practical introduction to PSL. Springer-Verlag New York Inc, 2006.
  16. C. C. Elgot. Decision problems of finite automata design and related arithmetics. Trans. Amer. Math. Soc., 98:21-52, 1961.
  17. R. Fagin, J. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, 1995.
  18. P. Felli, G. De Giacomo, and A. Lomuscio. Synthesizing agent protocols from LTL specifications against multiple partially- observable environments. In KR, 2012.
  19. M. J. Fischer and R. E. Ladner. Propositional dynamic logic of regular programs. J. Comput. Syst. Sci., 18:194-211, 1979.
  20. A. Gabaldon. Precondition control and the progression algo- rithm. In KR, 2004.
  21. D. M. Gabbay, A. Pnueli, S. Shelah, and J. Stavi. On the tem- poral analysis of fairness. In POPL, 1980.
  22. D. Harel. Dynamic logic. In Handbook of Philosophical Logic, D. Reidel Publishing Company, 1984.
  23. D. Harel, D. Kozen, and J. Tiuryn. Dynamic Logic. MIT Press, 2000.
  24. J. E. Hopcroft and J. D. Ullman. Introduction to automata theory, languages, and computation. Addison-Wesley, 1979.
  25. H. Kamp. On tense logic and the theory of order. PhD thesis, UCLA, 1968.
  26. B. Khoussainov and A. Nerode. Automata theory and its ap- plications. Birkhauser, 2001.
  27. E. L. Leiss. Succint representation of regular languages by boolean automata. Theor. Comput. Sci., 13:323-330, 1981.
  28. H. J. Levesque, R. Reiter, Y. Lesperance, F. Lin, and R. Scherl. GOLOG: A logic programming language for dynamic do- mains. J. of Logic Programming, 31:59-84, 1997.
  29. J. McCarthy and P. J. Hayes. Some philosophical problems from the standpoint of aritificial intelligence. Machine Intelli- gence, 4:463-502, 1969.
  30. R. McNaughton and S. Papert. Counter-Free Automata. MIT Press, 1971.
  31. F. Patrizi, N. Lipovetzky, G. D. Giacomo, and H. Geffner. Computing infinite plans for LTL goals using a classical plan- ner. In IJCAI, 2011. IJCAI
  32. M. Pešić, D. Bošnački, and W. van der Aalst. Enacting declar- ative languages using LTL: avoiding errors and improving per- formance. Model Checking Software, 2010.
  33. A. Pnueli. The temporal logic of programs. In FOCS, 1977.
  34. A. Pnueli, O. Lichtenstein, and L. Zuck. The Glory of The Past. Logics of Programs: Brooklyn, June 17-19, 1985, 193:194, 1985.
  35. A. Pnueli and R. Rosner. On the synthesis of a reactive module. In POPL, 1989.
  36. R. Reiter. Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems. MIT Press, 2001.
  37. A. P. Sistla and E. M. Clarke. The complexity of propositional linear temporal logics. J. ACM, 32(3):733-749, July 1985.
  38. S. Sohrabi, J. A. Baier, and S. A. McIlraith. Preferred expla- nations: Theory and generation via planning. In AAAI, 2011.
  39. L. J. Stockmeyer and A. Meyer. Cosmological lower bound on the circuit complexity of a small problem in logic. J. ACM, 49(6):753-784, 2002.
  40. W. Thomas. Star-free regular sets of ω-sequences. Information and Control, 42(2):148-156, 1979.
  41. W. Thomas. Languages, Automata, and Logic. Handbook of formal languages: beyond words, 1997.
  42. B. Trakhtenbrot. Finite automata and monadic second order logic. Siberian Math. J, 3:101-131, 1962. Russian; English translation in: AMS Transl. 59 (1966), 23-55.
  43. W. M. P. van der Aalst, M. Pešić, and H. Schonenberg. Declar- ative workflows: Balancing between flexibility and support. Computer Science -Research and Development, Mar. 2009.
  44. M. Y. Vardi. The rise and fall of linear time logic In 2nd Int'l Symp. on Games, Automata, Logics and Formal Verification, 2011.
  45. M. Y. Vardi. An automata-theoretic approach to linear tem- poral logic. In Logics for Concurrency: Structure versus Au- tomata, LNCS 1043, 1996.
  46. T. Wilke. Classifying discrete temporal properties. STACS,1999.
  47. P. Wolper. Temporal logic can be more expressive. Information and Control, 56(1/2):72-99, 1983.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards