Hier finden Sie wissenschaftliche Publikationen aus den Fraunhofer-Instituten.

The intersection type unification problem

: Dudenhefner, A.; Martens, M.; Rehof, J.

Fulltext ()

Kesner, D.:
1st International Conference on Formal Structures for Computation and Deduction, FSCD 2016 : 22nd - 26th June 2016, Porto, Portugal
Saarbrücken/Wadern: Dagstuhl Publ., 2016 (Leibniz International Proceedings in Informatics. LIPIcs 52)
ISBN: 978-3-95977-010-1
Art. 19, 16 pp.
International Conference on Formal Structures for Computation and Deduction (FSCD) <1, 2016, Porto>
Conference Paper, Electronic Publication
Fraunhofer ISST ()

The 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 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 fixed-parameter intractability result for intersection type matching (one-sided unification), which is known to be NP-complete. We place the 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 ACI-unification theory and use game-theoretic methods for two-player tiling games.