Dudenhefner, Andrej and Martens, Moritz and Rehof, Jakob - The Algebraic Intersection Type Unification Problem

lmcs:3858 - Logical Methods in Computer Science, August 15, 2017, Volume 13, Issue 3
The Algebraic Intersection Type Unification Problem

Authors: Dudenhefner, Andrej and Martens, Moritz and Rehof, Jakob

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


Source : oai:arXiv.org:1611.05672
DOI : 10.23638/LMCS-13(3:9)2017
Volume: Volume 13, Issue 3
Published on: August 15, 2017
Submitted on: August 15, 2017
Keywords: Computer Science - Logic in Computer Science,F.4.1


Share

Consultation statistics

This page has been seen 162 times.
This article's PDF has been downloaded 79 times.