Thumbnail
Access Restriction
Subscribed

Author Chang, Jik H. ♦ Ibarra, Oscar H. ♦ Vergis, Anastasios
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1988
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In this paper, a very simple model of parallel computation is considered, and the question of how restricting the flow of data to be one way compares with two-way flow is studied. It is shown that the one-way version is surprisingly very powerful in that it can solve problems that seemingly require two-way communication. Whether or not one-way communication is strictly weaker than two-way is an open problem, although the conjecture in this paper is in the positive. It is shown, however, that proving this conjecture is at least as hard as some well-known open problems in complexity theory.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1988-06-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 35
Issue Number 3
Page Count 30
Starting Page 697
Ending Page 726


Open content in new tab

   Open content in new tab
Source: ACM Digital Library