Observations on (n) time parallel recognition of unambiguous cfl's

DOI10.1016/0020-0190(92)90212-EMaRDI QIDQ1209354zbMATH OpenOpenAlexFDO

Authors Peter Rossmanith, Wojciech Rytter

Publication date 16 May 1993

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

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

zbMATH Keywords

CREW PRAMunambiguous context-free languagesparallel recognition

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Distributed algorithms (68W15)

Recommendations

• On the parallel recognition of unambiguous context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages
• scientific article; zbMATH DE number 3917742
• Parallel recognition and ranking of context-free languages
• scientific article; zbMATH DE number 3978426

Cites work

• scientific article; zbMATH DE number 4209587 (Why is no real title available?)
• scientific article; zbMATH DE number 43583 (Why is no real title available?)
• On the parallel recognition of unambiguous context-free languages
• Parallel time O(log n) recognition of unambiguous context-free languages

Cited in

(6)

• Unambiguous Boolean grammars
• Sublogarithmic ambiguity
• Parallel time O(log n) recognition of unambiguous context-free languages
• Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
• Formal languages over GF(2)
• scientific article; zbMATH DE number 3917742 (Why is no real title available?)

This page was built for publication: Observations on \(\log(n)\) time parallel recognition of unambiguous cfl's

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