Fast recognition of deterministic cfl's with a smaller number of processors

DOI10.1016/0304-3975(93)90333-OzbMath0783.68067MaRDI QIDQ685360

Wojciech Rytter, Burkhard Monien, Leopold Schäpers

Publication date: 17 October 1993

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

CREW PRAMdeterministic pushdown automatadeterministic context-free languageslogarithmic time

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (3)

Fast parallel recognition of LR language suffixes ⋮ Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages ⋮ Parallel recognition and ranking of context-free languages

Cites Work

• On the parallel recognition of unambiguous context-free languages
• The recognition of deterministic CFLs in small time and space
• Parallel Time $O(\log n)$ Acceptance of Deterministic CFL<scp>s</scp> on an Exclusive-Write P-RAM
• Parallelism in random access machines
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Fast recognition of deterministic cfl's with a smaller number of processors