Re: (N)Linspace

From: Jose Juan Mendoza Rodriguez (me_at_privacy.net)
Date: 10/03/04

  • Next message: peter_douglass: "Re: Zenkin's paper on Cantor" 
    Date: Sun, 3 Oct 2004 15:12:21 +0100

    >I think that context-free grammars caracterise Linspace, but does there
    >exist other similar caracterisations for either Linspace or NLinspace ?
    >
    >Jym.

    Hello,

    though I haven't done it, exercise 3.4.2(e) of C. H. Papadimitriou's
    Computational Complexity asks to prove that NSPACE(n) is precisely the
    class of languages generated by context-sensitive grammars.
    I don't know about DSPACE(n), but your conjecture seems reasonable.

    Regards.
    José Juan Mendoza Rodríguez

  • Next message: peter_douglass: "Re: Zenkin's paper on Cantor"