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.

Elaborating dependent (co)pattern matching: No pattern left behind In a dependently typed language, we can guarantee correctness of our programmes by providing formal proofs. To check them, the typechecker elaborates these programs and proofs into a lowlevel core language. However, this core language is by nature hard to understand by mere humans, so how can we know we proved the right thing? This question occurs in particular for dependent copattern matching, a powerful language construct for writing programmes and proofs by dependent case analysis and mixed inductioncoinduction. A definition by copattern matching consists of a list of  clauses  that are elaborated to a  case tree , which can be further translated to primitive  eliminators . In previous work this second step has received a lot of attention, but the first step has been mostly ignored so far. We present an algorithm elaborating definitions by dependent copattern matching to a core language with inductive data types, coinductive record types, an identity type, and constants defined by welltyped case trees. To ensure correctness, we prove that elaboration preserves the firstmatch semantics of the user clauses. Based on this theoretical work, we reimplement the algorithm used by Agda to check lefthand sides of definitions by pattern matching. The new implementation is at the same time more general and less complex, and fixes a number of bugs and usability issues with the old version. Thus, we take another step towards the formally verified implementation of a practical dependently typed language.