Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
We study here the language Datalog (≠), which is the query language obtained from Datalog by allowing equalities and inequalities in the bodies of the rules. We view Datalog (≠) as a fragment of an infinitary logic Lw and show that Lw can be characterized in terms of certain two-person pebble games. This characterization provides us with tools for investigating the expressive power of Datalog (≠). As a case study, we classify the expressibility of fixed subgraph homeomorphism queries on directed graphs. S. Fortune, J. Hopcroft, and J. Wyllie (Theoret. Comput. Sci. 10 (1980), 111-121) classified the computational complexity of these queries by establishing two dichotomies, which are proper only if P ≠ NP. Without using any complexity-theoretic assumptions, we show here that the two dichotomies are indeed proper in terms of expressibility in Datalog (≠). © 1995 by Academic Press, Inc.
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
Matthew A Grayson
Journal of Complexity
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization