論文

査読有り
1998年

Type inference for first-class messages with feature constraints

ADVANCES IN COMPUTING SCIENCE-ASIAN' 98
  • M Muller
  • ,
  • S Nishimura

1538
開始ページ
169
終了ページ
187
記述言語
英語
掲載種別
研究論文(学術雑誌)
出版者・発行元
SPRINGER-VERLAG BERLIN

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 compare 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.

Web of Science ® 被引用回数 : 2

リンク情報
J-GLOBAL
https://jglobal.jst.go.jp/detail?JGLOBAL_ID=200902165153752223
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000085483500014&DestApp=WOS_CPL
ID情報
  • ISSN : 0302-9743
  • J-Global ID : 200902165153752223
  • Web of Science ID : WOS:000085483500014

エクスポート
BibTeX RIS