Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!think.com!sdd.hp.com!news.cs.indiana.edu!rutgers!mcnc!duke!drh
From: drh@duke.cs.duke.edu (D. Richard Hipp)
Newsgroups: comp.theory
Subject: Looking for references...
Keywords: Formal languages, generation, CFGs
Message-ID: <674752501@romeo.cs.duke.edu>
Date: 20 May 91 15:15:02 GMT
Organization: Duke University Computer Science Dept.; Durham, N.C.
Lines: 22

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!