Thumbnail
Access Restriction
Subscribed

Author Dymond, Patrick W. ♦ Ruzzo, Walter L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2000
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword CROW-PRAM ♦ DCFL recognition ♦ Owner write ♦ Parallel algorithms
Abstract We identify and study a natural and frequently occurring subclass of Concurrent Read, Exclusive Write Parallel Random Access Machines (CREW-PRAMs). Called Concurrent Read, $\textit{Owner}$ Write, or CROW-PRAMS, these are machines in which each global memory location is assigned a unique “owner” processor, which is the only processor allowed to write into it. Considering the difficulties that would be involved in physically realizinga full CREW-PRAM model and demonstrate its stability under several definitional changes. Second, we precisely characterize the power of the CROW-PRAM by showing that the class of languages recognizable by it in time $\textit{O}(log$ n) (and implicity with a polynomial number of processors) is exactly the class LOGDCFL of languages log space reducible to deterministic context-free languages. Third, using the same basic machinery, we show that the recognition problem for deterministic context-free languages can be solved quickly on a deterministic auxilliary pushdown automation having random access to its input tape, a log $\textit{n}$ space work tape, and pushdown store of small maximum height. For example, time $\textit{O}(\textit{n}1$ + ε) is achievable with pushdown height $\textit{O}(log2$ $\textit{n}).$ These result extend and unify work of von Braunmöhl, Cook, Mehlhorn, and Verbeek, Klein and Reif; and Rytter.
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 2000-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 47
Issue Number 1
Page Count 30
Starting Page 16
Ending Page 45


Open content in new tab

   Open content in new tab
Source: ACM Digital Library