Suppose that $G$ is a finitely generated group and $A$ is a finite set. Then we shall give $A$ the discrete topology and $A^{G}$ the product topology; in particular $A^{G}$ is compact and totally disconnected.

If $x\in A^{G}$ and $g\in G$, then define $gx\in A^{G}$ by letting $gx(h)=x(g^{-1}h)$.

We say that $F:A^{G}\rightarrow A^{G}$ is $G$-equivariant if $F(gx)=g F(x)$ for each $g\in G$ and $x\in A^{G}$.

Then a cellular automaton is a function $F:A^{G}\rightarrow A^{G}$ which is both continuous and $G$-invariant.

We say that a language $L\subseteq A^{*}$ is accepted in polynomial time by a cellular automaton over the group $G$ if there exists some $B$ with $A\subseteq B$ along with some special elements $0,u,v\in B\setminus A$, a cellular automaton $F:B^{G}\rightarrow B^{G}$, an element $g\in G$ of infinite order, and a polynomial $p$ that satisfies the following property:

Suppose that $s\in A^{*}$. Then let $x\in B^{G}$ be the string where $x[g^{i}]=s[i]$ whenever $i<|s|$ and $x[h]=0$ whenever $h\not\in\{e,...,g^{|s|-1}\}$. Then there is some natural number $n<p(|x|)$ such that $F^{n}(x)(e)\in\{u,v\}$. Furthermore, if $n$ is the least natural number such that $F^{n}(x)(e)\in\{u,v\}$, then $s\in L$ if and only if $F^{n}(x)(e)=v$.

Is there a characterization of the groups which are computable in polynomial time such that a language $L$ is accepted in polynomial time if and only if it is accepted in polynomial time by a cellular automaton over the group $G$?

  • $\begingroup$ What does 'continuous' mean in this context? I don't see any metric specified on $A^G$ and it's not immediately clear to me what sort of plausible candidate for one you're assuming. $\endgroup$ – Steven Stadnicki Sep 15 '18 at 0:56
  • 1
    $\begingroup$ It's the product topology over the discrete topology. (A topological space, not a metric space). See en.wikipedia.org/wiki/… for the characterization of cellular automata in terms of continuous equivariant functions. $\endgroup$ – David Eppstein Sep 15 '18 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.