DocumentCode
2131591
Title
Undecidability results for deterministic communicating sequential processes
Author
Cieslak, Randall A. ; Varaiya, Pravin
Author_Institution
Dept. of Electr. Eng. & Comput. Sci., California Univ., Berkeley, CA, USA
fYear
1989
fDate
13-15 Dec 1989
Firstpage
2701
Abstract
A study is made of 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
Keywords
Turing machines; decidability; deterministic automata; discrete time systems; sequential machines; Turing machine; boundedness; deadlock; deterministic choice; deterministic communicating sequential processes; parallel composition; reachability; recursive equations; Equations; System recovery; Turing machines;
fLanguage
English
Publisher
ieee
Conference_Titel
Decision and Control, 1989., Proceedings of the 28th IEEE Conference on
Conference_Location
Tampa, FL
Type
conf
DOI
10.1109/CDC.1989.70670
Filename
70670
Link To Document