<p>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.</p>

<p>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.</p>

CC BY-SA 4.0
2022-10-19T18:00:50.247Z
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.
SamiD
CC BY-SA 4.0
2022-10-19T22:12:34.603Z
@SamiD: Just checked the original paper, and the language L is defined in a slightly different way indeed.  That being said, isn't that language also LogDCFL-complete?
Michaël Cadilhac
CC BY-SA 4.0
2022-10-21T08:11:56.830Z
Not sure that the language you define is in LogDCFL -- I can see that it is in LogCFL but how do you predict that the choice made at an intermediate stage will lead to acceptance eventually. In deterministic block choice however the choice is dictated by what is the last open parenthesis. I have not checked the hardness proof to see that goes through for your language, though.
SamiD
CC BY-SA 2.5
2010-09-14T11:51:35.723Z
2010-09-14T13:22:08.050Z
2010-09-14T13:22:08.050Z
Michaël Cadilhac
<p><a href="http://en.wikipedia.org/wiki/LOGCFL">LogCFL</a> 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 <a href="http://en.wikipedia.org/wiki/LOGCFL">wikipedia article</a> 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.</p>

CC BY-SA 2.5
2010-09-17T12:18:50.953Z
Out of curiosity, may I ask why you are interested in LogDCFL?
Michaël Cadilhac
CC BY-SA 2.5
2010-09-24T22:15:28.500Z
I am interested in space-bounded computation in general and trying understand LogDCFL.
Shiva Kintali
<cc.complexity-theory><complexity-classes>
LogDCFL-complete problems
Shiva Kintali
# LogDCFL-complete problems

(Asked by: username_0 on 2010-09-14)

[LogCFL](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/LOGCFL) 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.

**Tags:** cc.complexity-theory, complexity-classes
> **Comments:**
> **username_1**: Out of curiosity, may I ask why you are interested in LogDCFL?  
> **username_0**: I am interested in space-bounded computation in general and trying understand LogDCFL.  

---

## 1 answers

### Answer by username_1 on 2010-09-14. Score: 12 | Accepted answer

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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @SamiD: Just checked the original paper, and the language L is defined in a slightly different way indeed.  That being said, isn't that language also LogDCFL-complete?  
> **username_2**: Not sure that the language you define is in LogDCFL -- I can see that it is in LogCFL but how do you predict that the choice made at an intermediate stage will lead to acceptance eventually. In deterministic block choice however the choice is dictated by what is the last open parenthesis. I have not checked the hardness proof to see that goes through for your language, though.  

---

