Proceedings

Automata Theory for Reasoning About Actions

Download BibTeX Cite

Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 153-158.

© 1999 International Joint Conferences on Artificial Intelligence

Abstract

In this paper, we show decidability of a rather expressive fragment of the situation calculus. We allow second order quantification over finite and infinite sets of situations. We do not impose a domain closure assumption on actions; therefore , infinite and even uncountable domains are allowed. The decision procedure is based on automata accepting infinite trees.

  1. [Gelfond and Lifschitz, 1993] M. Gelfond and V. Lifs- chitz. Representing action and change by logic pro- grams. J. of Logic Programming, 17:301-322 , 1993 .
  2. [Liberatore, 1997] P. Liber~tore . The complexity of the language A. Linkoping Electronic Articles in Com- puter and Information Science, 2, 1997.
  3. [Miller and Shanahan, 1994] R. Miller and M. Shana- han. Narratives in the situation calculus. J . of Logic and Computation (Special Issue on Actions and Pro- cesses), 4(5):513-530, 1994.
  4. [Pirri and Reiter , 1999] F. Pirri and R. Reiter . Some contributions to the metatheory of the situation cal- culus. J. of ACM, to appear, 1999.
  5. [Reiter, 1991] R. Reiter. The frame problem in the sit- uation calculus: a simple solution (sometimes) and a completeness result for goal regression . In Vladimir Lifschitz , editor, Artificial Intelligence and Math e- matical Theory of Computation : Papers in Honor of John McCarthy, pages 359-380. Academic Press, San Diego, CA, 1991.
  6. [Sandewall , 1994] E. Sandewall. Features and Fluents: Th e Representation of Knowledge about Dynamic Sys- tems. Oxford University Press, 1994.
  7. [Ternovskaia, 1998] E. Ternovskaia. Inductive definabil- ity and the situation calculus. In Transaction and Change in Logic Databases, volume 1472 of Lecture Notes in Computer Science. Springer-Verlag, 1998.
  8. [Thomas, 1990] W. Thomas. Automata on infinite ob- jects. In J. van Leeuwen, editor, Handbook of Theo- retical Computer Science, pages 134-191. 1990.

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

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