UNDECIDABILITY RESULTS FOR DETERMINISTIC COMMUNICATING SEQUENTIAL PROCESSES

被引：8

作者：

CIESLAK, RA

VARAIYA, PP

机构：

[1] UNIV CALIF BERKELEY,DEPT ELECT ENGN & COMP SCI,BERKELEY,CA 94720

[2] UNIV CALIF BERKELEY,ELECTR RES LAB,BERKELEY,CA 94720

来源：

IEEE TRANSACTIONS ON AUTOMATIC CONTROL | 1990年 / 35卷 / 09期

关键词：

D O I：

10.1109/9.58531

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We study the subset of the communicating sequential processes formalism in which processes are described in terms of recursive equations that use only constant processes, deterministic choice, parallel composition, and sequential composition. Even with this limited version, the formalism is powerful enough to model a Turing machine, so that a number of important problems such as boundedness, deadlock, and reachability are undecidable. © 1990 IEEE

引用

页码：1032 / 1039

页数：8

共 21 条

[1]

Agerwala, 1974, 32 J HOPK U HOPK COM

[2] AUTOMATED PROTOCOL IMPLEMENTATION WITH RTAG [J].

ANDERSON, DP .

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, 1988, 14 (03) :291-300

[3] A Proof System for Communicating Sequential Processes [J].

Apt, Krzysztof R. ;

Francez, Nissim ;

De Roever, Willem P. .

ACM Transactions on Programming Languages and Systems, 1980, 2 (03) :359-385

[4]

GOSTELOW K, 1971, THESIS U CALIF LOS A

[5]

Hack M., 1975, THESIS MIT CAMBRIDGE

[6]

HACK M, 1976, TR159 MIT LAB COMP S

[7]

Hoare C.A.R., 1985, COMMUNICATING SEQUEN

[8]

Hopcroft J. E., 1979, INTRO AUTOMATA THEOR

[9]

Hopcroft J.E., 1966, SWAT, P36, DOI DOI 10.1109/SWAT.1966.22

[10] FINITELY RECURSIVE PROCESS MODELS FOR DISCRETE EVENT SYSTEMS [J].

INAN, K ;

VARAIYA, P .

IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1988, 33 (07) :626-639

← 1 2 3 →