Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. The Algebraic Intersection Type Unification Problem
 Logical methods in computer science : LMCS 13 (2017), No.3, 26 pp. ISSN: 18605974 

 English 
 Journal Article, Electronic Publication 
 Fraunhofer ISST () 
Abstract
The algebraic intersection type unification problem is an important component in proof search related to several natural decision problems in intersection type systems. It is unknown and remains open whether the algebraic intersection type unification problem is decidable. We give the first nontrivial lower bound for the problem by showing (our main result) that it is exponential time hard. Furthermore, we show that this holds even under rank 1 solutions (substitutions whose codomains are restricted to contain rank 1 types). In addition, we provide a fixedparameter intractability result for intersection type matching (onesided unification), which is known to be NPcomplete. We place the algebraic intersection type unification problem in the context of unification theory. The equational theory of intersection types can be presented as an algebraic theory with an ACI (associative, commutative, and idempotent) operator (intersection type) combined with distributivity properties with respect to a second operator (function type). Although the problem is algebraically natural and interesting, it appears to occupy a hitherto unstudied place in the theory of unification, and our investigation of the problem suggests that new methods are required to understand the problem. Thus, for the lower bound proof, we were not able to reduce from known results in ACIunification theory and use gametheoretic methods for twoplayer tiling games.