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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
Out of curiosity, may I ask why you are interested in LogDCFL? – Michaël Cadilhac Sep 17 '10 at 12:18
I am interested in space-bounded computation in general and trying understand LogDCFL. – Shiva Kintali Sep 24 '10 at 22:15
up vote 9 down vote accepted

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.