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.
Tell me more
×
Theoretical Computer Science Stack Exchange is a question and answer site for
theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.
|
|
The following language is a slight tweak of the usual LogCFL complete one so that it is LogDCFL complete. The proof can be found in Sudborough's On the Tape Complexity of Deterministic Context-Free Languages. 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. |
||||
|
|
