Querying Sequential and Concurrent Horn Transaction Logic Programs using Tabling Techniques

Paul Fodor

In this poster we describe the tabling techniques for Sequential and Concurrent Horn Transaction Logic. Horn Transaction Logic is an extension of classical logic programming with state updates and it has a SLD-style evaluation algorithm. This SLD-style algorithm enters into infinite loops when computing answers to many recursive programs when they change the underlying state of the knowledge base. We solve this problem by tabling (caching) the calls, call states and answers (unifications and return states) in a searchable structure for the Sequential Transaction Logic, or building a graph for the query and memoize the "hot" vertices (vertices, currently, possible to execute) for the Propositional Concurrent Transaction Logic, so that the same call is not re-executed ad infinum. With these techniques, we can efficiently compute queries to transaction logic programs, and when the underlying programs have the bounded term-depth property (Transaction Datalog) the techniques are guaranteed to terminate. The applications of these techniques promise termination and great improvements in the uses of transaction logic: state-changing systems, artificial intelligence planning, dynamic constraints on transaction execution, workflow modeling and verification, and systems involving financial transactions.

Subjects: 9.3 Mathematical Foundations; 1.11 Planning

Submitted: Apr 8, 2008

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.