✦ LIBER ✦

Almost optimal sublinear time parallel recognition algorithms for three subclasses of context free languages

✍ Scribed by Lawrence L. Larmore; Wojciech Rytter

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 803 KB
Volume: 197
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00253-3

No coin nor oath required. For personal study only.

✦ Synopsis

Sublinear time almost optimal algorithms for the recognition problem for three basic subclasses of context-free languages (unambiguous, deterministic and linear) are presented. Optimality is measured with respect to the work of the best-known sequential algorithm for a given problem.