A Satisficing Cycle for Real-Time Reasoning in Intelligent Agents

From Tetherless World Wiki

Jump to: navigation, search

Citation: Barbara Hayes-Roth. (1993) A Satisficing Cycle for Real-Time Reasoning in Intelligent Agents. In KSL-93-17, 1993.

Publication techreport ( Edit )
type Technical Report
bibtype techreport
Bibtex basics
author Barbara Hayes-Roth
title A Satisficing Cycle for Real-Time Reasoning in Intelligent Agents
number KSL-93-17
institution Knowledge Systems, AI Laboratory
year 1993
Bibtex more
note Submitted to KSL February 1993.
Access Paper
abstract We consider the problems of query-reachability and satisfiability in datalog programs with negation and dense-order constraints. These problems are important in the context of optimization, since solving them can detect extraneous rules and predicates. Satisfiability wasshown decidable for pure datalog programs~\cite{Shmu87}; decidability for datalog with dense-order constraints follows from the workof~\cite{KKR90}. Query-reachability was shown decidable for datalog with dense-order constraints~\cite{LS92}. In this paper, we show that both query-reachability and satisfiability are decidable for datalog programs with dense-order constraints and safe stratified negation provided that negation is applied only to EDB predicates, or all EDB predicates are unary. We also give a new undecidability result for satisfiability that implies a new undecidability result for both query-reachability and equivalence. These undecidability results apply to datalog programs with unary IDB predicates, negation, and the interpreted predicate$\not=$. In comparison, note that equivalence is decidable for datalog programs with only unary IDB predicates (and neither negationnor interpreted predicates)~\cite{CGKV88}.In proving some of the decidability results, we use a rather powerful tool, the {\em query-tree,} which was first used in~\cite{LS92}. Aquery-tree is a finite structure that encodes all symbolic derivation trees (of a datalog program $P$) that satisfy some given property.Query-trees can also be viewed as a refinement of tree automata techniques for the special purpose of representing symbolic derivation trees of datalog programs. The importance of tree-automata techniques for decision problems of datalog programs was shown in~\cite{Vard89}.Query-trees can be used not just for decision problems, but also foranalyzing datalog programs and transforming those programs into more efficient ones. For example, using query-trees, it is rather easy to push the tightest possible constraints to the EDB, and to useconstraints most efficiently during a magic-set evaluation.Conceivably the same could be done by applying tree-automata techniques directly, but doing so would be considerably more intricate. So, in essence, our results do not merely provide new decidable cases, but also imply how to push constraints in those cases.

KSL Technical Report ID: KSL-93-17
Facts about A Satisficing Cycle for Real-Time Reasoning in Intelligent AgentsRDF feed
Abstract We consider the problems of query-reachabi … We consider the problems of query-reachability and satisfiability in datalog programs with negation and dense-order constraints. These problems are important in the context of optimization, since solving them can detect extraneous rules and predicates. Satisfiability wasshown decidable for pure datalog programs~\cite{Shmu87}; decidability for datalog with dense-order constraints follows from the workof~\cite{KKR90}. Query-reachability was shown decidable for datalog with dense-order constraints~\cite{LS92}. In this paper, we show that both query-reachability and satisfiability are decidable for datalog programs with dense-order constraints and safe stratified negation provided that negation is applied only to EDB predicates, or all EDB predicates are unary. We also give a new undecidability result for satisfiability that implies a new undecidability result for both query-reachability and equivalence. These undecidability results apply to datalog programs with unary IDB predicates, negation, and the interpreted predicate$\not=$. In comparison, note that equivalence is decidable for datalog programs with only unary IDB predicates (and neither negationnor interpreted predicates)~\cite{CGKV88}.In proving some of the decidability results, we use a rather powerful tool, the {\em query-tree,} which was first used in~\cite{LS92}. Aquery-tree is a finite structure that encodes all symbolic derivation trees (of a datalog program $P$) that satisfy some given property.Query-trees can also be viewed as a refinement of tree automata techniques for the special purpose of representing symbolic derivation trees of datalog programs. The importance of tree-automata techniques for decision problems of datalog programs was shown in~\cite{Vard89}.Query-trees can be used not just for decision problems, but also foranalyzing datalog programs and transforming those programs into more efficient ones. For example, using query-trees, it is rather easy to push the tightest possible constraints to the EDB, and to useconstraints most efficiently during a magic-set evaluation.Conceivably the same could be done by applying tree-automata techniques directly, but doing so would be considerably more intricate. So, in essence, our results do not merely provide new decidable cases, but also imply how to push constraints in those cases. ly how to push constraints in those cases.
Author Barbara Hayes-Roth  +
Bibtype techreport  +
Has author Barbara Hayes-Roth  +
Has identifier KSL-93-17  +
Has publishing details 1993  +
Has title A Satisficing Cycle for Real-Time Reasoning in Intelligent Agents  +
Has where published KSL-93-17  +
Has year 1993  +
Institution Knowledge Systems, AI Laboratory  +
Ksl tr id KSL-93-17  +
Note Submitted to KSL February 1993.
Number KSL-93-17  +
Process note YES  +
Title A Satisficing Cycle for Real-Time Reasoning in Intelligent Agents  +
Year 1993  +
Retrieved from "http://tw.rpi.edu/wiki/A_Satisficing_Cycle_for_Real-Time_Reasoning_in_Intelligent_Agents"
Personal tools