[Solved]: Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

The class $LOG_{CF}$ is in fact the class of regular languages $R$ (and thus have all of the regular languages closure properties). $Rsubseteq LOG_{CF}$ is trivial, so we’ll concern ourselves only with the the other direction. Let $A$ be some PDA, and let $s(n)$ be the maximal stack size of $A$’s run on a length-$n$ word. First notice that if $s(n)=O(1)$, then $L(A)$ is regular (you can always encode a finite set of stack configurations into a NFA). We will claim that if $s(n)=omega(1)$, then $s(n)=Theta(n)$, thus there can’t be any PDA which is guaranteed to use non-constant sub-linear space. We define Automaton-Sub-Configuration to be a tuple $(q,x)in Qtimes Gamma^*$ such that currently the automaton is in state $q$, and the top of his stack (the suffix of the stack word), is a word $xinGamma^*$. Now if $s(n)=omega(1)$, there has to be some automaton sub-configuration, $(q’,x’)$, for the such that: $(q’,x’)$ can be reached unbounded number of times, and on every time it is reached, the stack size grows by at least one symbol. Let $w_0in Sigma^*$ be a word such that the automaton would reach $(q’,x’)$, and let $w_1$ be a word such that when reading $w_1$ out of $(q’,x’)$, the automaton ends at $(q’,x’)$ with at least one additional symbol in the stack. Finally, consider the word $w=w_0cdot w_1^k$. Notice that the automaton stack size after reading $w$ is (at least) $k$, while $|w|=|w_0|+k|w_1|$, hence the stack size could be linear in the length of the word. The conclusion is that for any PDA $A$, $s(n)=O(1)$ or $s(n)=Theta(n)$.