Parallel Time O(\log n) Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
From MaRDI portal
Publication:3798245
Recommendations
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
- A tight ω(loglog n)-bound on the time for parallel RAM's to compute nondegenerated boolean functions
- Limits on the power of parallel random access machines with weak forms of write conflict resolution
- scientific article; zbMATH DE number 512845
- scientific article; zbMATH DE number 3917742
- Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's
- On the power of concurrent-write PRAMs with read-only memory
- Lower bounds for randomized exclusive write PRAMs
Cited in
(9)- Limits on the power of parallel random access machines with weak forms of write conflict resolution
- scientific article; zbMATH DE number 3960999 (Why is no real title available?)
- scientific article; zbMATH DE number 512845 (Why is no real title available?)
- Parallel RAMs with owned global memory and deterministic context-free language recognition
- Efficient sublinear time parallel algorithms for dynamic programming and context-free recognition
- Parallel recognition and ranking of context-free languages
- Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
- Fast recognition of deterministic cfl's with a smaller number of processors
- Fast parallel recognition of LR language suffixes
This page was built for publication: Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3798245)
