<p>The paper </p>

<p>J.-M. Autebert, Une note sur le cylindre des langages déterministes,
<em>Theoretical Computer Science</em> <strong>8</strong> (1979), 395-399</p>

<p>gives a short proof of the following result (credited to Greibach) which seems to answer your question: </p>

<blockquote>
  <p>there is no deterministic context-free language $L$ such that, for
  every deterministic context-free language $C$, there is an
  homomorphism $h$ and a regular language $R$ such that $C = h^{-1}(L)\cap R$.</p>
</blockquote>

CC BY-SA 3.0
2016-03-26T17:02:05.350Z
2016-03-26T17:02:05.350Z
J.-E. Pin
<p>There actually <em>is</em> a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in <em>On 
deterministic 
context-free 
languages, 
multihead 
automata, 
and 
the 
power 
of 
an 
auxiliary 
pushdown 
store</em>—it is however hardest w.r.t log-space reduction.  The language $L_0^{(2)}$ referred therein is the set of  words over $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$ where:</p>

<p>$$\gamma_0\;[\bar{a}\gamma_a^{(1)}\#\bar{b}\gamma_b^{(1)}]\;\cdots\; [\bar{a}\gamma_a^{(k)}\#\bar{b}\gamma_b^{(k)}]\enspace,$$</p>

<p>with $\gamma_0, \gamma_a^{(i)}, \gamma_b^{(i)}$ words over $\{a, \bar{a}, b, \bar{b}\}$, such that there exists a word $w_1w_2\cdots w_k \in \{a, b\}^k$ with $\gamma_0 \; \bar{w_1}\gamma_{w_1}^{(1)} \cdots  \bar{w_k}\gamma_{w_k}^{(k)}$ a Dyck word.</p>

<p>It then holds that <strong>$L_0^{(2)}$ is a DCFL and any DCFL log-space-reduces to $L_0^{(2)}$.  In that sense, $L_0^{(2)}$ is the hardest <em>tape</em> DCFL.</strong></p>

<p>As mentioned by contributor Mateus de Oliveira Oliveira, DCFL is <em>not</em> a principal AFL, and it is <em>unknown</em> whether there exists an exact characterization involving the closure of a single language under some operations.</p>

CC BY-SA 3.0
2016-02-24T17:21:53.727Z
2016-02-24T17:21:53.727Z
Michaël Cadilhac
<p>An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original <a href="http://epubs.siam.org/doi/abs/10.1137/0202025?journalCode=smjcat">paper</a>.</p>

<blockquote>
  <p>We show that every context-free language can be expressed as $h^{-1}(L_0)$ or $h^{-1}(L_0-\{e\})$ for a homomorphism $h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By way of contrast, the family of deterministic context-free languages is not a principal AFDL [7].</p>
</blockquote>

<p>The <a href="http://dl.acm.org/citation.cfm?id=804031">paper 7</a> is the conference version of the paper. In the conference version, Theorem 4.2 states that "The family of deterministic context-free languages is not a principal AFDL". </p>

<p>However some analogue characterization may still be possible. <a href="http://tucs.fi/publications/attachment.php?fname=tOkhotin_Alexander13a.full.pdf">Okhotin</a> provided homomorphic characterizations of conjunctive and Boolean grammars. For DCFL's the problem seems to be open. The following is the conclusion of Okhotin's paper (from 2013). </p>

<blockquote>
  <p>Every family of languages closed under inverse homomorphisms can potentially
  have an analogue of Greibach’s inverse homomorphic characterization.
  The question is, which families have it? Could it exist for linear, deterministic
  or unambiguous variants of ordinary (context-free) grammars? Could
  there be such a characterization for linear conjunctive grammars, unambiguous
  conjunctive grammars, etc.?</p>
</blockquote>

CC BY-SA 3.0
2016-02-21T22:59:55.713Z
Thanks! However, I do know that the DCFL are not principal ; this is why I'm allowing the morphisms to be restricted if needed - I can more accurately word my question as: what is the smallest class of functions F for which there is a language H where F(H) is the set of all DCFL - give or take some additional closures.
Michaël Cadilhac
CC BY-SA 3.0
2016-02-21T23:28:05.430Z
Ok. I edited my answer. It seems that for DCFL this is an open problem.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2016-02-23T15:54:36.847Z
Funnily enough, I know very well Okhotin's article, but didn't notice that he was explicitly referring to the problem!  Well then, I'm not sure what to do here; sure, it is a *valid* answer *for the moment*, but should it be left open until solved?
Michaël Cadilhac
CC BY-SA 3.0
2016-02-23T23:46:42.613Z
I don't know what is the police of the site about asking solutions for hard open problems. Personally, if someone pointed to me that a problem I'm interested in is open for many years, then I would accept the answer. My opinion is that in this case it is more appropriate to view the question as a reference request. But there may be divergent points of view with relation to this. I think this discussion in meta.cstheory might be helpful http://meta.cstheory.stackexchange.com/questions/1058/tag-wiki-open-problem
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2016-02-24T17:23:48.977Z
I've asked around for more, and the result of Sudborough seems to be the general consensus about hardest DCFL.  Would you mind if I ended up accepting my own answer?—I'm sorry for the bad practice :-(
Michaël Cadilhac
CC BY-SA 3.0
2016-02-29T20:48:37.710Z
Of course I don't mind you accepting your the answer. Indeed it is a very interesting answer. However although the answer kind of fits the title, it is very different from the question itself, since logspace reductions are much more powerful than homomorphisms.
Mateus de Oliveira Oliveira
CC BY-SA 3.0
2016-02-21T22:44:41.803Z
2016-02-21T23:27:20.520Z
2016-02-21T23:27:20.520Z
Mateus de Oliveira Oliveira
<p>Greibach famously defined a language $H$, the so-called <em>nondeterministic version</em> of $D_2$, such that any CFL is an inverse morphic image of $H$.  Does there exist a similar statement with DCFL, possibly with some restriction on the morphisms allowed?</p>

<p>(See, e.g., M. Autebert, J. Berstel, and L. Boasson. Context-free languages and
pushdown automata. In R. Rozenberg and A. Salomaa, editors,
Handbook of Formal Languages, volume I, chapter 3. Springer Verlag, 1997.)</p>

<fl.formal-languages><open-problem><context-free><nondeterminism><hard-instances>
Does there exist a hardest DCFL?
Michaël Cadilhac
# Does there exist a hardest DCFL?

(Asked by: username_0 on 2016-02-21)

Greibach famously defined a language $H$, the so-called *nondeterministic version* of $D\_2$, such that any CFL is an inverse morphic image of $H$. Does there exist a similar statement with DCFL, possibly with some restriction on the morphisms allowed?

(See, e.g., M. Autebert, J. Berstel, and L. Boasson. Context-free languages and
pushdown automata. In R. Rozenberg and A. Salomaa, editors,
Handbook of Formal Languages, volume I, chapter 3. Springer Verlag, 1997.)

**Tags:** fl.formal-languages, open-problem, context-free, nondeterminism, hard-instances


---

## 3 answers

### Answer by username_1 on 2016-03-26. Score: 8

The paper

J.-M. Autebert, Une note sur le cylindre des langages déterministes,
*Theoretical Computer Science* **8** (1979), 395-399

gives a short proof of the following result (credited to Greibach) which seems to answer your question:

> there is no deterministic context-free language $L$ such that, for
> every deterministic context-free language $C$, there is an
> homomorphism $h$ and a regular language $R$ such that $C = h^{-1}(L)\cap R$.


---

### Answer by username_0 on 2016-02-24. Score: 8

There actually *is* a hardest DCFL, which is a deterministic version of Greibach's; it was introduced by Sudborough in 78 in *On
deterministic
context-free
languages,
multihead
automata,
and
the
power
of
an
auxiliary
pushdown
store*—it is however hardest w.r.t log-space reduction. The language $L\_0^{(2)}$ referred therein is the set of words over $\{a, \bar{a}, b, \bar{b}, \#, [, ]\}$ where:

$$\gamma\_0\;[\bar{a}\gamma\_a^{(1)}\#\bar{b}\gamma\_b^{(1)}]\;\cdots\; [\bar{a}\gamma\_a^{(k)}\#\bar{b}\gamma\_b^{(k)}]\enspace,$$

with $\gamma\_0, \gamma\_a^{(i)}, \gamma\_b^{(i)}$ words over $\{a, \bar{a}, b, \bar{b}\}$, such that there exists a word $w\_1w\_2\cdots w\_k \in \{a, b\}^k$ with $\gamma\_0 \; \bar{w\_1}\gamma\_{w\_1}^{(1)} \cdots \bar{w\_k}\gamma\_{w\_k}^{(k)}$ a Dyck word.

It then holds that **$L\_0^{(2)}$ is a DCFL and any DCFL log-space-reduces to $L\_0^{(2)}$. In that sense, $L\_0^{(2)}$ is the hardest *tape* DCFL.**

As mentioned by contributor username_2, DCFL is *not* a principal AFL, and it is *unknown* whether there exists an exact characterization involving the closure of a single language under some operations.


---

### Answer by username_2 on 2016-02-21. Score: 8

An identical homomorphism characterization of DCFL does not seem to be possible. The following is extracted from Greibach's original [paper](http://epubs.siam.org/doi/abs/10.1137/0202025?journalCode=smjcat).

> We show that every context-free language can be expressed as $h^{-1}(L\_0)$ or $h^{-1}(L\_0-\{e\})$ for a homomorphism $h$. The algebraic statement is: the family of context-free languages is a principal AFDL; ... By way of contrast, the family of deterministic context-free languages is not a principal AFDL [7].

The [paper 7](http://dl.acm.org/citation.cfm?id=804031) is the conference version of the paper. In the conference version, Theorem 4.2 states that "The family of deterministic context-free languages is not a principal AFDL".

However some analogue characterization may still be possible. [Okhotin](http://tucs.fi/publications/attachment.php?fname=tOkhotin_Alexander13a.full.pdf) provided homomorphic characterizations of conjunctive and Boolean grammars. For DCFL's the problem seems to be open. The following is the conclusion of Okhotin's paper (from 2013).

> Every family of languages closed under inverse homomorphisms can potentially
> have an analogue of Greibach’s inverse homomorphic characterization.
> The question is, which families have it? Could it exist for linear, deterministic
> or unambiguous variants of ordinary (context-free) grammars? Could
> there be such a characterization for linear conjunctive grammars, unambiguous
> conjunctive grammars, etc.?

> **Comments:**
> **username_0**: Thanks! However, I do know that the DCFL are not principal ; this is why I'm allowing the morphisms to be restricted if needed - I can more accurately word my question as: what is the smallest class of functions F for which there is a language H where F(H) is the set of all DCFL - give or take some additional closures.  
> **username_2**: Ok. I edited my answer. It seems that for DCFL this is an open problem.  
> **username_0**: Funnily enough, I know very well Okhotin's article, but didn't notice that he was explicitly referring to the problem!  Well then, I'm not sure what to do here; sure, it is a *valid* answer *for the moment*, but should it be left open until solved?  
> **username_2**: I don't know what is the police of the site about asking solutions for hard open problems. Personally, if someone pointed to me that a problem I'm interested in is open for many years, then I would accept the answer. My opinion is that in this case it is more appropriate to view the question as a reference request. But there may be divergent points of view with relation to this. I think this discussion in meta.cstheory might be helpful http://meta.cstheory.stackexchange.com/questions/1058/tag-wiki-open-problem  
> **username_0**: I've asked around for more, and the result of Sudborough seems to be the general consensus about hardest DCFL.  Would you mind if I ended up accepting my own answer?—I'm sorry for the bad practice :-(  
> **username_2**: Of course I don't mind you accepting your the answer. Indeed it is a very interesting answer. However although the answer kind of fits the title, it is very different from the question itself, since logspace reductions are much more powerful than homomorphisms.  

---

