NONDETERMINISM AND INFINITE COMPUTATIONS IN CONSTRAINT PROGRAMMING

被引：34
作者：
DEBOER, FS
DIPIERRO, A
PALAMIDESSI, C
机构：
[1] UNIV PISA,DIPARTIMENTO INFORMAT,I-56125 PISA,ITALY
[2] UNIV GENOA,DISI,I-16132 GENOA,ITALY
来源：
THEORETICAL COMPUTER SCIENCE | 1995年 / 151卷 / 01期
关键词：
D O I：
10.1016/0304-3975(95)00047-Z
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We investigate the semantics of concurrent constraint programming and of various sublanguages, with particular emphasis on nondeterminism and infinite behavior. The aim is to find out what is the minimal structure which a domain must have in order to capture these two aspects. We show that a notion of observables, obtained by the upward-closure of the results of computations, is relatively easy to model even in presence of synchronization. On the contrary, modeling the exact set of results is problematic, even for the simple sublanguage of constraint logic programming. We show that most of the standard topological techniques fail in capturing this more precise notion of observables. The analysis of these failed attempts leads us to consider a categorical approach.
引用
收藏
页码：37 / 78
页数：42
相关论文
共 32 条
  • [1] ABDALLAH MAN, 1984, P AUTOMATA LANGUAGES, V172, P374
  • [2] [Anonymous], 14TH P ACM S PRINC P
  • [3] Apt Krzysztof R, 1988, FDN DEDUCTIVE DATABA, P89, DOI [10.1016/B978-0-934613-40-8.50006-3, DOI 10.1016/B978-0-934613-40-8.50006-3]
  • [4] CLARK KL, 1979, DOC7959 IMP COLL DEP
  • [5] PROCESSES AND THE DENOTATIONAL SEMANTICS OF CONCURRENCY
    DEBAKKER, JW
    ZUCKER, JI
    [J]. INFORMATION AND CONTROL, 1982, 54 (1-2): : 70 - 120
  • [6] DEBOER FS, 1991, LECT NOTES COMPUT SC, V493, P296
  • [7] DEBOER FS, 1991, THEOR COMPUT SCI, V86, P3, DOI 10.1016/0304-3975(91)90003-K
  • [8] DEBOER FS, 1993, 18TH P ANN ACM S PRI
  • [9] DEBOER FS, 1993, LOGIC PROGRAMM, P82
  • [10] DEBOER FS, 1992, P ALPUK 92, P145
1234