Les formules bien formées dans la logique de prédicat pour une signature donnée peuvent-elles être reconnues dans Logspace?

Question

je lis ça Langages visiblement pushdown sont censés modéliser les langages formels simples typiques comme XML mieux que les langues libres de contexte déterministe. Les langages visiblement pushdown peuvent être reconnus dans Logspace. Je me demande si les formules bien formées dans la logique de prédicat pour une signature donnée sont un langage visiblement poussé, ou peuvent au moins être reconnus dans Logspace.

Voici une formule bien formée typique dans la logique du prédicat, pour la signature donnée $ (f ( cdot, cdot), g ( cdot)) $:

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

Une grammaire sans contexte correspondante serait

$ P à t = t $
$ P à (p land p) $
$ P à (p lor p) $
$ P à lnot p $
$ P to forall vp $
$ P to existant vp $
$ T à v $

$ V à x $
$ V à y $
$ V à z $

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

Certaines personnes préfèrent utiliser la notation polonaise inversée:

$ xyfz = zgx = land x forall $

Une grammaire sans contexte correspondante serait

$ P à tt = $
$ P à pp land $
$ P à pp lor $
$ P à p lnot $
$ P à pv forall $
$ P à pv existe $
$ T à v $

$ V à x $
$ V à y $
$ V à z $

$ T à ttf $
$ T à tg $

Parce que j'ai maintenant écrit deux grammaires explicites, que la question soit simplement si ces deux grammaires génèrent des langues visiblement pushdown, ou peuvent au moins être reconnues dans Logspace.