# LogDCFL-complete problems

LogCFL is the set of all languages that are logspace reducible to a context-free language. Similarly, LogDCFL is the set of all languages that are logspace reducible to a deterministic context-free language. See this wikipedia article for some natural LogCFL-complete problems. There are several other interesting LogCFL-complete problems. I could not find any natural LogDCFL-complete problems. Name any natural LogDCFL-complete problem.

• Out of curiosity, may I ask why you are interested in LogDCFL? Sep 17, 2010 at 12:18
• I am interested in space-bounded computation in general and trying understand LogDCFL. Sep 24, 2010 at 22:15

Let $\Sigma = \{(_1,(_2,)_1, )_2\}$ and $T = \{[,],|\}$. The following language over $\Sigma \cup T$ is LogDCFL-complete. $L$ consists of words $$w_0\left[(_1l_1|(_2r_1\right]\ldots\left[(_1l_n|(_2r_n\right]$$ where $w_0, l_i, r_i \in \Sigma^*$ such that there exists $w_1, \ldots, w_n$ with $w_i = (_1l_i$ or $w_i = (_2r_i$ for all $i \geq 1$ and $w_0w_1\ldots w_n$ is parenthetically correct.
• Shouldn't the options be $)_1l_1|)_2r_1$ etc. i.e. start with $)_1$ or $)_2$ rather than with $(_1,(_2$. Sorry for the slightly :-) delayed comment. Oct 19, 2022 at 18:00