Reasoning about Action in Polynomial Time
Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computat ional complexity into considerat ion. The contributions of this paper are the fol lowing: a temporal logic w i th a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about act ion, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondetermin ism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.