Le formule ben formate nella logica predicata per una data firma possono essere riconosciute in Logspace?

Question

L'ho letto Lingue visibilmente pushdown dovrebbero modellare i linguaggi formali semplici tipici come XML meglio delle lingue libere di contesto deterministiche. Le lingue visibilmente pushdown possono essere riconosciute in Logspace. Mi chiedo se le formule ben formate nella logica predicata per una determinata firma siano un linguaggio visibilmente pushdown o possa almeno essere riconosciuta in Logspace.

Ecco una tipica formula ben formata nella logica predicata, per la firma data $ (f ( CDOT, CDOT), G ( CDOT)) $:

$ forall x (f (x, y) = z land g (z) = x) $

Una grammatica libera del contesto corrispondente sarebbe

$ P a t = t $
$ P a (p land p) $
$ P a (p lor p) $
$ P a lnot p $
$ P a forall vp $
$ P a esiste vp $
$ T a v $

$ V a x $
$ V a y $
$ V a z $

$ T a f (t, t) $
$ T a g (t) $

Alcune persone preferiscono usare la notazione polacca inversa:

$ xyfz = zgx = land x forall $

Una grammatica libera del contesto corrispondente sarebbe

$ P a tt = $
$ P a pp land $
$ P a pp lor $
$ P a p lnot $
$ P a pv forall $
$ P a pv esiste $
$ T a v $

$ V a x $
$ V a y $
$ V a z $

$ T a ttf $
$ T a tg $

Poiché ora ho scritto due grammatiche esplicite, lascia che la domanda sia solo se queste due grammatiche generano lingue visibilmente pushdown o che possano almeno essere riconosciute in Logspace.