Treffer: Type inference for first-class messages with feature constraints

Title:
Type inference for first-class messages with feature constraints
Authors:
MÜLLER, M, NISHIMURA, S
Source:
Advances in computing science - ASIAN'98 (Manila, 8-10 December 1998)Lecture notes in computer science. :169-187
Publisher Information:
Berlin: Springer, 1998.
Publication Year:
1998
Physical Description:
print, 33 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Théorie programmation, Programming theory, Complexité programme, Program complexity, Complejidad programa, Informatique théorique, Computer theory, Informática teórica, Programmation logique, Logical programming, Programación lógica, Programmation orientée objet, Object-oriented programming, Règle inférence, Inference rule, Regla inferencia
Document Type:
Konferenz Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Universität des Saarlandes, 66041 Saarbrücken, Germany
RIMS, Kyoto University, Sakyo-ku, Kyoto 606-8502, Japan
ISSN:
0302-9743
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=1572195
Rights:
Copyright 1999 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems
Accession Number:
edscal.1572195
Database:
PASCAL Archive

Weitere Informationen

We present a constraint system OF of feature trees that is appropriate to specify and implement type inference for first-class messages. OF extends traditional systems of feature constraints by a selection constraint x<y>z by first-class feature tree y, in contrast to the standard selection constraint x[f]y by fixed feature f. We investigate the satisfiability problem of OF and show that it can be solved in polynomial time, and even in quadratic time in an important special case. We cdmpare OF with Treinen's constraint system EF of feature constraints with first-class features, which has an NP-complete satisfiability problem. This comparison yields that the satisfiability problem for OF with negation is NP-hard. Based on OF we give a simple account of type inference for first-class messages in the spirit of Nishimura's recent proposal, and we show that it has polynomial time complexity: We also highlight an immediate extension that is desirable but makes type inference NP-hard.