<p>Is there a representation of the functions from <span class="math-container">$\mathsf{DLogTime}$</span>-uniform <span class="math-container">$\mathsf{AC}^0$</span> for which equivalence is decidable?</p>

<p>Since the languages defined by nondeterministic pushdown automata belong to <span class="math-container">$\mathsf{LogCFL}$</span>, and we know that their equivalence is not decidable, we know that there can be no representation of the functions from <span class="math-container">$\mathsf{LogCFL}$</span> for which equivalence would be decidable. Since <span class="math-container">$\mathsf{AC}^0$</span> is nearly the most powerful class which we still can separate from <span class="math-container">$\mathsf{LogCFL}$</span>, learning that equivalence of <span class="math-container">$\mathsf{AC}^0$</span> is decidable should have no surprising consequences (at least I expect that if equivalence of <span class="math-container">$\mathsf{TC}^0$</span> were known to be decidable, then we could separate <span class="math-container">$\mathsf{TC}^0$</span> from <span class="math-container">$\mathsf{LogCFL}$</span>).</p>

<hr>

<p><strong>Edit:</strong> Emil's comment hints that the answer is "no", but that this question did not define what it means by "representation" rigorously enough to allow any definite answer at all. Let me first try to guess why the answer is "no": Since <a href="https://cstheory.stackexchange.com/questions/33778/is-length-uniform-ac0-computable">length is <span class="math-container">$\mathsf{DLogTime}$</span> computable</a>, it is probably possible to pad the input at will, by writting the padded length in binary at the beginning, and hence reducing the equivalence problem for  <span class="math-container">$\mathsf{CFL}$</span> to the equivalence problem for  <span class="math-container">$\mathsf{DLogTime}$</span>.</p>

<p>Given the paragraph about <span class="math-container">$\mathsf{LogCFL}$</span> above, one should expect that this question interprets "representation" in a way that is compatible with that conclusion. But that is not the case. (But making my guess about padding the input rigorous would nevertheless answer this question.) It assumes that "representation" simply has its intuitive meaning. So we have strings over some alphabet, we can computationally decide whether a string is "valid", every language from <span class="math-container">$\mathsf{DLogTime}$</span>-uniform <span class="math-container">$\mathsf{AC}^0$</span> is represented by some "valid" string, and given a "valid" string, it is possible to computationally enumerate the language represented by that string.</p>

CC BY-SA 4.0
2019-06-29T19:31:54.030Z
What, exactly, do you mean by “a representation”? Equivalence is certainly undecidable for common natural representations of AC^0 (e.g., clocked O(log n)-time alternating turing machines with a constant number of alternations, or  FO(+,.)-formulas). However, let $\{L_n:n\in\omega\}$ be any bijective enumeration of AC^0-languages, and represent $L_n$ by $n$. Then equivalence is decidable (as it amounts to identity).
Emil Jeřábek
CC BY-SA 4.0
2019-06-29T20:25:16.840Z
@EmilJeřábek I was mostly thinking about representations by $\mathsf{FO}$ formulas, because they at least have a form where it might be possible that there is some algorithm for deciding whether they are satisfied by the same finite structures. The representation should at least allow to computationally decide membership in the language represented by a specific member. Not sure whether this will be possible for $L_n$ if you are given $n$, for your bijective enumeration of AC^0.
Thomas Klimpel
CC BY-SA 4.0
2019-06-29T22:40:29.150Z
I'm with @EmilJeřábek: I'm not sure the question is well-defined.  You mention that PDA equivalence is undecidable—sure thing, but, along the line's of Emil's argument, there are representations of CFLs for which equivalence is decidable.  If your question is about FO, you should word it this way (in which case, equivalence is surely undecidable).
Michaël Cadilhac
CC BY-SA 4.0
2019-06-30T04:33:53.143Z
@MichaëlCadilhac If the answer should be "yes, equivalence is decidable for AC0, it is even decidable for CFLs", then that would also help me. Do those representations of CFLs allow to computationally decide membership in the language represented by a specific member, or at least computationally enumerate that language? (If not, then I don't understand why it should be considered to be a reasonable representation.) Since I often struggle with descriptive complexity theory, I don't want to limit this question to $\mathsf{FO}$.
Thomas Klimpel
CC BY-SA 4.0
2019-06-30T07:02:59.987Z
*If not, then I don't understand why it should be considered to be a reasonable representation*: exactly my point. So, you need to tell us what you consider a reasonable representation.
Emil Jeřábek
<cc.complexity-theory><equivalence>
Is equivalence of uniform AC0 decidable?
Thomas Klimpel
# Is equivalence of uniform AC0 decidable?

(Asked by: username_0 on 2019-06-29)

Is there a representation of the functions from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ for which equivalence is decidable?

Since the languages defined by nondeterministic pushdown automata belong to $\mathsf{LogCFL}$, and we know that their equivalence is not decidable, we know that there can be no representation of the functions from $\mathsf{LogCFL}$ for which equivalence would be decidable. Since $\mathsf{AC}^0$ is nearly the most powerful class which we still can separate from $\mathsf{LogCFL}$, learning that equivalence of $\mathsf{AC}^0$ is decidable should have no surprising consequences (at least I expect that if equivalence of $\mathsf{TC}^0$ were known to be decidable, then we could separate $\mathsf{TC}^0$ from $\mathsf{LogCFL}$).

---

**Edit:** Emil's comment hints that the answer is "no", but that this question did not define what it means by "representation" rigorously enough to allow any definite answer at all. Let me first try to guess why the answer is "no": Since [length is $\mathsf{DLogTime}$ computable](https://cstheory.stackexchange.com/questions/33778/is-length-uniform-ac0-computable), it is probably possible to pad the input at will, by writting the padded length in binary at the beginning, and hence reducing the equivalence problem for $\mathsf{CFL}$ to the equivalence problem for $\mathsf{DLogTime}$.

Given the paragraph about $\mathsf{LogCFL}$ above, one should expect that this question interprets "representation" in a way that is compatible with that conclusion. But that is not the case. (But making my guess about padding the input rigorous would nevertheless answer this question.) It assumes that "representation" simply has its intuitive meaning. So we have strings over some alphabet, we can computationally decide whether a string is "valid", every language from $\mathsf{DLogTime}$-uniform $\mathsf{AC}^0$ is represented by some "valid" string, and given a "valid" string, it is possible to computationally enumerate the language represented by that string.

**Tags:** cc.complexity-theory, equivalence
> **Comments:**
> **username_1**: What, exactly, do you mean by “a representation”? Equivalence is certainly undecidable for common natural representations of AC^0 (e.g., clocked O(log n)-time alternating turing machines with a constant number of alternations, or  FO(+,.)-formulas). However, let $\{L_n:n\in\omega\}$ be any bijective enumeration of AC^0-languages, and represent $L_n$ by $n$. Then equivalence is decidable (as it amounts to identity).  
> **username_0**: @EmilJeřábek I was mostly thinking about representations by $\mathsf{FO}$ formulas, because they at least have a form where it might be possible that there is some algorithm for deciding whether they are satisfied by the same finite structures. The representation should at least allow to computationally decide membership in the language represented by a specific member. Not sure whether this will be possible for $L_n$ if you are given $n$, for your bijective enumeration of AC^0.  
> **username_2**: I'm with @EmilJeřábek: I'm not sure the question is well-defined.  You mention that PDA equivalence is undecidable—sure thing, but, along the line's of Emil's argument, there are representations of CFLs for which equivalence is decidable.  If your question is about FO, you should word it this way (in which case, equivalence is surely undecidable).  
> **username_0**: @MichaëlCadilhac If the answer should be "yes, equivalence is decidable for AC0, it is even decidable for CFLs", then that would also help me. Do those representations of CFLs allow to computationally decide membership in the language represented by a specific member, or at least computationally enumerate that language? (If not, then I don't understand why it should be considered to be a reasonable representation.) Since I often struggle with descriptive complexity theory, I don't want to limit this question to $\mathsf{FO}$.  
> **username_1**: *If not, then I don't understand why it should be considered to be a reasonable representation*: exactly my point. So, you need to tell us what you consider a reasonable representation.  

---

## 0 answers

