✦ LIBER ✦

Reasoning about action in polynomial time

✍ Scribed by Thomas Drakengren; Marcus Bjäreland

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 196 KB
Volume: 115
Category: Article
ISSN: 0004-3702
DOI: 10.1016/s0004-3702(99)00065-x

No coin nor oath required. For personal study only.

✦ Synopsis

Although many formalisms for reasoning about action exist, surprisingly few approaches have taken computational complexity into consideration. The contributions of this article are the following: a temporal logic with a restriction for which deciding satisfiability is tractable, a tractable extension for reasoning about action, and NP-completeness results for the unrestricted problems. Many interesting reasoning problems can be modelled, involving nondeterminism, concurrency and memory of actions. The reasoning process is proved to be sound and complete.

📜 SIMILAR VOLUMES

Reasoning about time in the situation ca

Reasoning about time in the situation calculus

✍ Javier Pinto; Raymond Reiter 📂 Article 📅 1995 🏛 Springer Netherlands 🌐 English ⚖ 933 KB

Reasoning about actions and obligations

Reasoning about actions and obligations in first-order logic

✍ Gert -Jan C. Lokhorst 📂 Article 📅 1996 🏛 Springer Netherlands 🌐 English ⚖ 713 KB

Guest editor's introduction: Reasoning a

Guest editor's introduction: Reasoning about action and change

✍ Vladimir Lifschitz 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 94 KB

The automation of reasoning about the consequences of actions has been viewed as an important problem since the early days of Artificial Intelligence. Logic programming turned out to be an excellent tool for describing actions and their effects. The use of negation as failure leads to a simple solut

Reasoning about Strings in Databases

✍ Gösta Grahne; Matti Nykänen; Esko Ukkonen 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 499 KB

In order to enable the database programmer to reason about relations over strings of arbitrary length, we introduce alignment calculus, a modal extension of the relational calculus. In addition to relations, a state in the model consists of a two-dimensional array where the strings are aligned on to

Reasoning about preferences in argumenta

Reasoning about preferences in argumentation frameworks

✍ Sanjay Modgil 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 543 KB

Reasoning about data in middle school sc

Reasoning about data in middle school science

✍ R. Paul Vellom; Charles W. Anderson 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 75 KB

This case study illustrates instruction in an urban 6th-grade classroom in which students were learning about mass, volume, and density by attempting to layer (stack) three miscible solutions with differing densities atop one another. The study examines classroom discourse and interaction on the bas