TY - CHAP
T1 - Subtyping constraints in quasi-lattices
AU - Coquery, Emmanuel
AU - Fages, François
PY - 2003/1/1
Y1 - 2003/1/1
N2 - In this paper, we show the decidability and NP-completeness of the satisfiability problem for non-structural subtyping constraints in quasi-lattices. This problem, first introduced by Smolka in 1989, is important for the typing of logic and functional languages. The decidability result is obtained by generalizing Trifonov and Smith's algorithm over lattices, to the case of quasi-lattices with a complexity in O(mvMvn3), where m (resp. M) stands for the number of minimal (resp. maximal) elements of the quasi-lattice, v is the number of unbounded variables and n is the number of constraints. Similarly, we extend Pottier's algorithm for computing explicit solutions to the case of quasi-lattices. Finally we evoke some applications of these results to type inference in constraint logic programming and functional programming languages.
AB - In this paper, we show the decidability and NP-completeness of the satisfiability problem for non-structural subtyping constraints in quasi-lattices. This problem, first introduced by Smolka in 1989, is important for the typing of logic and functional languages. The decidability result is obtained by generalizing Trifonov and Smith's algorithm over lattices, to the case of quasi-lattices with a complexity in O(mvMvn3), where m (resp. M) stands for the number of minimal (resp. maximal) elements of the quasi-lattice, v is the number of unbounded variables and n is the number of constraints. Similarly, we extend Pottier's algorithm for computing explicit solutions to the case of quasi-lattices. Finally we evoke some applications of these results to type inference in constraint logic programming and functional programming languages.
UR - https://www.scopus.com/pages/publications/35248832117
U2 - 10.1007/978-3-540-24597-1_12
DO - 10.1007/978-3-540-24597-1_12
M3 - Chapter
AN - SCOPUS:35248832117
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 136
EP - 148
BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
A2 - Pandya, Paritosh K.
A2 - Radhakrishnan, Jaikumar
PB - Springer Verlag
ER -