Subtyping constraints in quasi-lattices

Emmanuel Coquery; François Fages

doi:10.1007/978-3-540-24597-1_12

Subtyping constraints in quasi-lattices

Emmanuel Coquery, François Fages

INRIA Rocquencourt

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

Abstract

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(m^vM^vn³), 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.

Original language	English
Title of host publication	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Editors	Paritosh K. Pandya, Jaikumar Radhakrishnan
Publisher	Springer Verlag
Pages	136-148
Number of pages	13
ISBN (Electronic)	9783540206804
DOIs	https://doi.org/10.1007/978-3-540-24597-1_12
Publication status	Published - 1 Jan 2003
Externally published	Yes

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2914
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Access to Document

10.1007/978-3-540-24597-1_12

Cite this

Coquery, E., & Fages, F. (2003). Subtyping constraints in quasi-lattices. In P. K. Pandya, & J. Radhakrishnan (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 136-148). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2914). Springer Verlag. https://doi.org/10.1007/978-3-540-24597-1_12

Coquery, Emmanuel ; Fages, François. / Subtyping constraints in quasi-lattices. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). editor / Paritosh K. Pandya ; Jaikumar Radhakrishnan. Springer Verlag, 2003. pp. 136-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inbook{f3e32f7b64b949e1bdcdc0a8d172444a,

title = "Subtyping constraints in quasi-lattices",

abstract = "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.",

author = "Emmanuel Coquery and Fran{\c c}ois Fages",

year = "2003",

month = jan,

day = "1",

doi = "10.1007/978-3-540-24597-1\_12",

language = "English",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "136--148",

editor = "Pandya, \{Paritosh K.\} and Jaikumar Radhakrishnan",

booktitle = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

}

Coquery, E & Fages, F 2003, Subtyping constraints in quasi-lattices. in PK Pandya & J Radhakrishnan (eds), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2914, Springer Verlag, pp. 136-148. https://doi.org/10.1007/978-3-540-24597-1_12

Subtyping constraints in quasi-lattices. / Coquery, Emmanuel; Fages, François.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). ed. / Paritosh K. Pandya; Jaikumar Radhakrishnan. Springer Verlag, 2003. p. 136-148 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2914).

Research output: Chapter in Book/Report/Conference proceeding › Chapter › peer-review

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.

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 -

Coquery E, Fages F. Subtyping constraints in quasi-lattices. In Pandya PK, Radhakrishnan J, editors, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Springer Verlag. 2003. p. 136-148. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-24597-1_12

Subtyping constraints in quasi-lattices

Abstract

Publication series

Access to Document

Fingerprint

Cite this