Queryable acyclic production systems
David Arthur Tanzer, Dennis E. Shasha · 1999
We pose a query problem about the behavior of a consultation system S: given a constraint formula q and a potential conclusion c for S, determine if there is a user input binding that satisfies q and causes S to conclude c. Existing rule-based expert systems, both forward and backward chaining[3], implement a consultation mechanism S, but are not designed for these queries about S. For general production systems, the queries are undecidable. Here we solve the problem for useful sublanguages of acyclic production systems.We implement a query tool in a Datalog + constraints framework, and optimize for “embedded decision trees” in the rule system. Our data complexity is T(n·ƒ(n)) in the size of the embedded trees, versus T(n·ƒ(n) + n2) for existing datalog evaluation algorithms, where ƒ(n) is the cost of destructively conjoining a constraint of unit size into a conjunction of n constraints.