On the Equivalence of a Class of Purely Exponential Logic Queries to Linear Queries

スポンサーリンク

概要

• 論文の詳細を見る

• Purely exponential queries are logic programs of the form:S(X^^-) - S(X^^-_1), S(X^^-_2),. . ., S(X^^-_n). S(X^^-) - A(X^^-).where S and A are predicates of arity m. In this paper, we provide a syntactic condition under which these queries call be rewritten as linear queries. As an application of this result, we give a new proof for Guessarian's theorem [5] on converting binary chained exponential queries to linear queries. Moreover, an iIlfinite chain of progressively weaker template dependencies is constructed via expansion of the logic program for transitive closure of a relation R. This natural chain yields another proof for the result of R. Fagin, et al. [4].

• 一般社団法人情報処理学会の論文
• 1989-12-25

著者

• Wu Tian-zheng

  Department Of Computer Science New Mexico Tech.

• Taghva Kazem

  Department Of Computer Science University Of Nevada

関連論文

• On the Equivalence of a Class of Purely Exponential Logic Queries to Linear Queries

スポンサーリンク