Pointers versus arithmetic in PRAMs

Author

Dymond, Patrick W. ; Fich, Faith E. ; Nishimura, Naomi ; Ragde, Prabhakar ; Ruzzo, Walter L.

Author_Institution

York Univ., Toronto, Ont., Canada

fYear

1993

fDate

18-21 May 1993

Firstpage

239

Lastpage

252

Abstract

A parallel pointer machine, (PPM) is a parallel model having pointers as its principal data type. PPMs have been characterized as PRAMs obeying two restrictions: restricted arithmetic capabilities and the CROW (concurrent read, owner write) memory access restriction. Results concerning the relative power of PPMs (and other arithmetically restricted PRAMs) versus CROW PRAMs having ordinary arithmetic capabilities are presented. First, lower bounds separating PPMs from CROW PRAMs are proved. Second, it is shown that this lower bound is tight. As a corollary, sharply improved PPM algorithms are obtained for a variety of problems, including deterministic context-free language recognition

Keywords

computational complexity; context-free languages; parallel algorithms; type theory; CROW; CROW PRAMs; PPMs; PRAMs; deterministic context-free language recognition; memory access restriction; parallel pointer machine; pointers; principal data type; Arithmetic; Computer architecture; Concurrent computing; Data structures; Parallel algorithms; Phase change random access memory; Polynomials; Random access memory; Read-write memory; Upper bound;

fLanguage

English

Publisher

ieee

Conference_Titel

Structure in Complexity Theory Conference, 1993., Proceedings of the Eighth Annual

Conference_Location

San Diego, CA

Print_ISBN

0-8186-4070-7

Type

conf

DOI

10.1109/SCT.1993.336522

Filename

336522