Some considerations about NPRIORITY(1) without ROM

DOI10.1016/0020-0190(88)90212-8MaRDI QIDQ1113673zbMATH OpenOpenAlexFDO

Authors Katsushi Inoue, Itsuo Takanami

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90212-8

zbMATH Keywords

complexityk-sensitive everywhere functionnondeteministic one-way pushdown automatanondeterministic CRCW PRAMparallel computation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Review text

This article observes some computational time bounds on a kind of a nondeterministic CRCW PRAM. In particular the authors prove that nondeteministic one-way pushdown automata can be simulated by nondeterministic PRIORITY(1)'s without ROM in O(\(\sqrt{n})\) time. This time bound is tight.

Recommendations

• Separation and lower bounds for ROM and nondeterministic models of parallel computation
• Time lower bounds do not exist for CRCW PRAMs
• New lower bounds for parallel computation
• Processor-time tradeoffs in PRAM simulations
• scientific article; zbMATH DE number 17533

Cites work

• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Quasi-realtime languages
• Separation and lower bounds for ROM and nondeterministic models of parallel computation
• Trade-Offs between Depth and Width in Parallel Computation

This page was built for publication: Some considerations about NPRIORITY(1) without ROM

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113673)