Integration of Functions Defined with Rewriting Rules in Datalog.
Stéphane Grumbach · 1989
This work is devoted to the integration of functions in Datalog. Functions are defined with a rewrite relation. We define a fixpoint semantics for Horn programs containing both relations and rewriting rules. The principal contribution is the bounded semantics. We study the two following problems: the computability of the fixpoint in presence of an infinite universe and the completeness of the semantics restricted to interpretations containing only bounded depth terms. We prove that both problems are undecidable in general, but decidable subcases are presented.