Dynamic Logic

By Silva, Andres | AI Magazine, Spring 2002 | Go to article overview
Save to active project

Dynamic Logic


Silva, Andres, AI Magazine


Harel, D.; Kozen, D.; and Tiuryn, J. Dynamic Logic. Cambridge, Massachusetts, The MIT Press, 2000, 459 pp., $50.00, ISBN 0-262-08289-6.

The real world is dynamic, and any intelligent perception of the world should include the concept of time. Remember that time and space are a priori conditions of human perception in Kant's philosophy. On the one hand, time is inherent to action and change; on the other, action and change are possible because of the passage of time. According to McDermott, "Dealing with time correctly would change everything in an Al program" (McDermott 1982, p. 101).

It should not be surprising then that temporal reasoning has always been a very important topic in many fields of Al, particularly areas dealing with change, causality, and action (planning, diagnosis, natural language understanding, and so on). Al developments based on temporal reasoning lead to general theories about time and action, such as McDermott's (1982) temporal logic, Vilain's (1982) theory of time, and Allen's (1984) theory of action and time. Work on the application of these results has taken place in fields such as planning and medical knowledge-based systems.

However, action and change are not an exclusive interest of AI. In mainstream computer science, any execution of a "traditional" computer program is considered to perform an action that leads to a change of state.

From this point of view, the field of program verification, traditionally focused on the correctness of actions carried out by program executions, can potentially provide AI with many approaches suitable for dealing with action and change. Temporal logic and dynamic logic are two of the approaches that have been used in the fields of both Al and program verification, temporal logic being the most popular. Both temporal and dynamic logic provide alternative applications of modal logic to program specification and verification. The main difference between the two is that temporal logic is endogenous, and dynamic logic is exogenous. A logic is exogenous if programs (actions) are explicit in the language. Temporal logic is endogenous, so its programs (actions) are never explicit in the language. Dynamic logic subsumes temporal logic.

Some cross-fertilization has already take place between AI, temporal logic, and dynamic logic. I focus on dynamic logic, which is the topic that is covered at length in the book under review. Dynamic logic is an approach to program verification with strong Al potential. One of the most prominent uses of dynamic logic in Al was Moore's (1990) approach. Moore formalized some issues related to agency, with a focus on what an agent needs to know to be able to perform an action. For more information on this topic and a clear demonstration of the usefulness of dynamic logic for agent reasoning and action, see the survey by Meyer (1999). Also, some research in knowledge engineering inspired by, or making use of, dynamic logic has been published van Harmelen and Balder (1992) and Fensel (1995).

Dynamic logic is an eclectic approach to program verification, as is evidenced by its history. This history starts with the pragmatics of programming, that is, the study of the actions that programs perform and the correctness of these actions. This has been a major issue in computer science since Dijkstra's (1968) attacks on the GOTO statement. Perhaps the most popular formal approach aimed at proving program correctness is Hoare's (1969), which is based on correctness assertions. In Hoare's logic, statements of the form (aP(b say that if program P starts in an input state satisfying a, then if and when P halts, it does so in a state satisfying b. Hoare provided some inference rules used to infer assertions about programs from assertions about other programs. IMAGE FORMULA16IMAGE FORMULA17

Here we have a book that provides a deep insight into the topic of dynamic logic.

The rest of this article is only available to active members of Questia

Sign up now for a free, 1-day trial and receive full access to:

  • Questia's entire collection
  • Automatic bibliography creation
  • More helpful research tools like notes, citations, and highlights
  • Ad-free environment

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
Loading One moment ...
Project items
Notes
Cite this article

Cited article

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

Cited article

Dynamic Logic
Settings

Settings

Typeface
Text size Smaller Larger
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

While we understand printed pages are helpful to our users, this limitation is necessary to help protect our publishers' copyrighted material and prevent its unlawful distribution. We are sorry for any inconvenience.
Full screen

matching results for page

Cited passage

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

Cited passage

Welcome to the new Questia Reader

The Questia Reader has been updated to provide you with an even better online reading experience.  It is now 100% Responsive, which means you can read our books and articles on any sized device you wish.  All of your favorite tools like notes, highlights, and citations are still here, but the way you select text has been updated to be easier to use, especially on touchscreen devices.  Here's how:

1. Click or tap the first word you want to select.
2. Click or tap the last word you want to select.

OK, got it!

Thanks for trying Questia!

Please continue trying out our research tools, but please note, full functionality is available only to our active members.

Your work will be lost once you leave this Web page.

For full access in an ad-free environment, sign up now for a FREE, 1-day trial.

Already a member? Log in now.

Are you sure you want to delete this highlight?