2026-07-20T11:45:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5995 2024-03-06T10:37:25Z ddc:004 open_access

The Intersection Type Unification Problem Dudenhefner, Andrej Martens, Moritz Rehof, Jakob Intersection Type Equational Theory Unification Tiling Complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrej Dudenhefner and Moritz Martens and Jakob Rehof 2016 Is Part Of LIPIcs, Volume 52, 1st International Conference on Formal Structures for Computation and Deduction (FSCD 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSCD.2016.19 urn:nbn:de:0030-drops-59955 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2016.19 eng https://creativecommons.org/licenses/by/3.0/legalcode