drh@duke.cs.duke.edu (D. Richard Hipp) (05/20/91)
I'm searching for references to papers/books/articles which discuss
problems similar to the examples listed below. Any responses will be
appreciated.
1. G is a CFG and L(G) is its language. K is a positive integer. Given G,
find the K-th element of L(G) assuming the elements are listed
in dictionary order (shortest first). Do this in time which is
a polynomial in K.
1b. Quickly list all elements of L(G) which are shorter than K symbols.
1c. Quickly count the number of elements in L(G) which are less than
K symbols long.
2. G is a CFG and R is a regular language. Find G' which is a subset
of G consisting of all production rules in G which are used in any
derivation of any string in R.
2b. Given CFG G and regular expression R, find G' such that
L(G') = L(G) \intersect L(R) and |G'| = O(|G|).
Please E-mail responses to drh@cs.duke.edu. Thanks!hans@lscs.ed.ac.uk (Hans Huttel) (05/21/91)
In article <674752501@romeo.cs.duke.edu>, drh@duke.cs.duke.edu (D. Richard Hipp) writes: > I'm searching for references to papers/books/articles which discuss > problems similar to the examples listed below. Any responses will be > appreciated. > > 1. [ stuff deleted ] > 1b. [ stuff deleted ] > 1c. [ stuff deleted ] > 2. [ stuff deleted ] > 2b. [ stuff deleted ] > Please E-mail responses to drh@cs.duke.edu. Thanks! Is it just me, or is this person having a take-home exam ? (I think the format of his question gives it all away...) -- Hans H\"{u}ttel, Office 1603 JANET: hans@uk.ac.ed.lfcs Lab. for Foundations of Comp. Sci. UUCP: ..!mcvax!ukc!lfcs!hans JCMB, University of Edinburgh ARPA: hans%lfcs.ed.ac.uk@nsfnet-relay.ac.uk Edinburgh EH9 3JZ, SCOTLAND This is _not_ a clever quote from a song.
cliff@cs.man.ac.uk (Cliff B Jones) (05/26/91)
I have recently (together with Ketil Stoelen) been working on a new way of developing shared-variable style concurrent programs. One of the examples that we have tried is a parallel version of J. Earley's parsing (well, we've focussed on the recogniser) algorithm. There are some interesting questions about the form of the parallel version of the algorithm itself. Does anyone have any references to this (or other) parallel parsing algorithms? cliff jones