Path: utzoo!attcan!uunet!van-bc!ubc-cs!alberta!hoover
From: hoover@cs.UAlberta.CA (Jim Hoover)
Newsgroups: comp.theory
Subject: Re: Parallel Parsing?
Message-ID: <1990Oct16.150050.21926@cs.UAlberta.CA>
Date: 16 Oct 90 15:00:50 GMT
References: <40171@shemp.CS.UCLA.EDU>
Sender: news@cs.UAlberta.CA (News Administrator)
Organization: University of Alberta, Edmonton, Canada
Lines: 21

In article <40171@shemp.CS.UCLA.EDU> chou@lanai.cs.ucla.edu (Ching-Tsun Chou) writes:
>
>Does anyone know of any works, either theoretical or practical, on
>parsing context-free languages with parallel algorithms?
>I would greatly appreciate any pointers and will post a summary of responses.
>
>Please mail your response to <chou@cs.ucla.edu>.
>
>- Ching Tsun

You wouldn't know it from the title, but Larry Ruzzo's paper:
    Walter L. Ruzzo, "Tree-Size Bounded Alternation", J. Computer and System
    Sciences, 21, 1980, pp 218-235.
shows that CFL recognition can be done in O(log n)^2 time with a polynomial 
number of processors.  There may be an efficient parser lurking in the proofs.

--
Prof. Jim Hoover                   | Office +1 403 492 5401 or 5290
Dept. of Computing Science         | FAX    +1 403 492 1071
University of Alberta              | hoover@cs.ualberta.ca
Edmonton, Alberta, Canada T6G 2H1  |