Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
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.
Frank R. Libsch, Takatoshi Tsujimura
Active Matrix Liquid Crystal Displays Technology and Applications 1997
Arnon Amir, Michael Lindenbaum
IEEE Transactions on Pattern Analysis and Machine Intelligence
Trang H. Tran, Lam Nguyen, et al.
INFORMS 2022
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010