On Equivalence and Cores for Incomplete Databases in Open and Closed Worlds. Data exchange heavily relies on the notion of incomplete database instances. Several semantics for such instances have been proposed and include open (OWA), closed (CWA), and openclosed (OCWA) world. For all these semantics important questions are: whether one incomplete instance semantically implies another; when two are semantically equivalent; and whether a smaller or smallest semantically equivalent instance exists. For OWA and CWA these questions are fully answered. For several variants of OCWA, however, they remain open. In this work we adress these questions for Closed Powerset semantics and the OCWA semantics of Libkin and Sirangelo, 2011. We define a new OCWA semantics, called OCWA*, in terms of homomorphic covers that subsumes both semantics, and characterize semantic implication and equivalence in terms of such covers. This characterization yields a guessandcheck algorithm to decide equivalence, and shows that the problem is NPcomplete. For the minimization problem we show that for several common notions of minimality there is in general no unique minimal equivalent instance for Closed Powerset semantics, and consequently not for the more expressive OCWA* either. However, for Closed Powerset semantics we show that one can find, for any incomplete database, a unique finite set of its subinstances which are subinstances (up to renaming of nulls) of all instances semantically equivalent to the original incomplete one. We study properties of this set, and extend the analysis to OCWA*.

A computational complexity analysis of tunable type inference for Generic Universe Types Abstract   We address questions related to the computational complexity of inferring types for a particular type system, Generic Universe Types (GUT)  1 ,  2 , for Java programs. GUT is useful for many applications, such as program verification  3 , thread synchronization, and memory management. However, requiring the programmer to explicitly provide type information is onerous, which motivates the problem of automatically inferring types. In contrast to classical type systems, ownership type systems such as GUT may have multiple typings that satisfy the type systemu0027s rules. It is therefore appropriate for the inference to be tunable: the programmer can indicate preferences for certain typings via breakable constraints andor by partial annotations. A question then is whether efficient algorithms exist for the type inference problem. In this work we establish the following results for the type inference problem for GUT  2 . (1) The tunable type inference problem that allows breakable constraints is NPhard, (2) an encoding of the problem as boolean satisfiability (SAT), as in prior work, is indeed a polynomialtime reduction, (3)    P  xe2x89xa0  N  P    implies that the problem is not approximable in polynomial time within an approximation ratio of      n    1  xe2x88x92  xcfxb5      for any    xcfxb5  u003e  0   , and (4) while some restricted versions of the problem of practical interest, such as when breakable constraints are forbidden, are in P, others remain NPhard. Our results justify the prior approach to the problem that is based on reduction to SAT. Apart from these results, given the observation in prior work that instances of the problem that arise in practice appear to be easy, we address the natural question as to what hard instances may look like, and whether they may arise in practice. We identify a class of hard instances of the problem by devising a method to generate such instances starting at instances of the Vertex Cover problem, which is known to be NPhard. We then analyze the structural properties of such instances as compared to easy instances of similar size. We find that for the classes of instances we consider, certain SAT structural parameters may be predictive of empirical hardness.