Compilability of Domain Descriptions in the Language A.
Paolo Liberatore · 1997
In this note we analyze the possibility of reducing the complexity of entailment in A by a compilation of the domain description. Since a single domain description D must in general be queried many times with respect to many different queries V, it makes sense to reduce it in a form that allows the solving problem of entailment in polynomial time. Using results from the field of language compilation, we prove that such a compilation is impossible, if we impose the result of compilation to be a polynomial data structure.