<p>Your definition seems to extend the notion of "convolution products" in groups; this can be seen as follows. Consider a finite group $G$ with generating set $\Sigma$, with the corresponding map $i_G : \Sigma^* \rightarrow G$. Construct the corresponding automaton $\cal{A}(G,\Sigma)$ with state set $G$ and which contains a transition $x \rightarrow_a a.x$ for every $x \in G, a \in \Sigma$.</p>

<p>Let $H$ be a normal subgroup of $G$, and consider the quotient $Q = G / H$; we can view $Q$ as a finite group with generating set $\Sigma$, up to identifying each $a \in \Sigma$ with its class $aH$. By the factor theorem, there is a projection $j : G \rightarrow Q$ (mapping $x$ to $xH$) and an homomorphism $i_Q : \Sigma^* \rightarrow Q$ such that $i_Q = j \circ i_G$.</p>

<p>Consider the corresponding automata $A = \cal{A}(G,\Sigma)$ and $B = \cal{A}(Q,\Sigma)$. Define the relation $R$ by: $R(a,bH) \Leftrightarrow a \in bH$. This defines an automata relation: for every $u,v \in \Sigma^*$ such that $u.a = v.a$, we have $i_G(u) = i_G(v)$ and thus $i_Q(u) = i_Q(v)$, implying that $u.(bH) = v.(bH)$.</p>

<p>Consider the tuple $T = (A,B,R)$. For every coset $k = tH \in Q$, it is easy to see that the set $R^{-1}(k)$ consists exactly of the elements of $k$, and that given an element $s \in G$, the operation $s^{-1} k$ gives the coset $(s^{-1} t) H$. As $H$ is a normal subgroup of $G$, we have $(s^{-1} t) H = (s^{-1} H) (t H)$, and in this case we obtain a "convolution product" over $Q$: given two weight functions $f,g$ over $Q(B)$, we obtain $\Theta_{T,f,g}(s) = \sum_{t \in Q} f(t) g(s^{-1} t)$. In particular, the function is stabilized by $H$, as for $r \in H$ the function $t \rightarrow (s^{-1} r s) t$ is a bijection over $Q$.</p>

<p>This suggests a possible connection with Fourier analysis and with the theta functions of integer lattices; there might be also a relation with the notion of harmonic functions over group actions. I'm not sure though if this is the kind of questions you are interested in.</p>

CC BY-SA 3.0
2014-04-01T14:24:44.910Z
2014-04-02T14:23:29.777Z
2014-04-02T14:23:29.777Z
NisaiVloot
<p>Let $A,B$ be two automata over the same alphabet $\Sigma$; they are supposed to be complete, strongly connected DFAs. We denote by $._A$ (resp. $._B$) the action induced by $\Sigma^*$ over $Q(A)$, i.e. $u ._A s$ designates the state reached from $s$ upon reading $u$ - note that this is more commonly denoted by $\delta_A(u,s)$ but we adopt the first notation for conciseness.  Say that an "automata relation" between $A$ and $B$ is a relation $R \subseteq Q(A) \times Q(B)$ such that:</p>

<p>(*) if $R(s,t)$ holds, then for any $u,v \in \Sigma^*$ we have: $u ._A s = v ._A s \Rightarrow u ._B t = v ._B t$.</p>

<p>Given $R$ and $t \in Q(B)$, we then define $R^{-1}(t) = \{ s \in Q(A) : R(s,t) \text{ holds} \}$.</p>

<p>Given such a relation, it is possible to define an action of $Q(A)$ over $Q(B)$ as follows: given $t \in Q(B)$ and $s \in Q(A)$, we define $s^{-1} t$ as the unique state $t' \in Q(B)$ such that for every $s' \in R^{-1}(t)$, $L_A(s',s).t = \{t'\}$. Note that the existence of $t'$ follows from the strong connectedness of $A$, and that the unicity follows by observing that if $u,v \in L_A(s',s)$, we have $u ._A s' = v ._A s' = s$ and thus $u ._B t = v ._B t = t'$.</p>

<p>Now, given the tuple $T = (A,B,R)$ and given two weight functions $f,g$ over $Q(B)$, let us define the "theta function" $\Theta_{T,f,g}(s) = \sum_{t \in Q(B)} f(t) g(s^{-1} t)$.</p>

<p>Question: what are the interesting questions to ask about this notion?</p>

<p>(Some examples and suggestions should follow, I'm still trying to clear my thoughts on this problem.)</p>

<automata-theory>
Theta functions of automata relations
Super0
# Theta functions of automata relations

(Asked by: username_0 on 2014-03-31)

Let $A,B$ be two automata over the same alphabet $\Sigma$; they are supposed to be complete, strongly connected DFAs. We denote by $.\_A$ (resp. $.\_B$) the action induced by $\Sigma^\*$ over $Q(A)$, i.e. $u .\_A s$ designates the state reached from $s$ upon reading $u$ - note that this is more commonly denoted by $\delta\_A(u,s)$ but we adopt the first notation for conciseness. Say that an "automata relation" between $A$ and $B$ is a relation $R \subseteq Q(A) \times Q(B)$ such that:

(\*) if $R(s,t)$ holds, then for any $u,v \in \Sigma^\*$ we have: $u .\_A s = v .\_A s \Rightarrow u .\_B t = v .\_B t$.

Given $R$ and $t \in Q(B)$, we then define $R^{-1}(t) = \{ s \in Q(A) : R(s,t) \text{ holds} \}$.

Given such a relation, it is possible to define an action of $Q(A)$ over $Q(B)$ as follows: given $t \in Q(B)$ and $s \in Q(A)$, we define $s^{-1} t$ as the unique state $t' \in Q(B)$ such that for every $s' \in R^{-1}(t)$, $L\_A(s',s).t = \{t'\}$. Note that the existence of $t'$ follows from the strong connectedness of $A$, and that the unicity follows by observing that if $u,v \in L\_A(s',s)$, we have $u .\_A s' = v .\_A s' = s$ and thus $u .\_B t = v .\_B t = t'$.

Now, given the tuple $T = (A,B,R)$ and given two weight functions $f,g$ over $Q(B)$, let us define the "theta function" $\Theta\_{T,f,g}(s) = \sum\_{t \in Q(B)} f(t) g(s^{-1} t)$.

Question: what are the interesting questions to ask about this notion?

(Some examples and suggestions should follow, I'm still trying to clear my thoughts on this problem.)

**Tags:** automata-theory

---

## 1 answers

### Answer by username_1 on 2014-04-01. Score: 5

Your definition seems to extend the notion of "convolution products" in groups; this can be seen as follows. Consider a finite group $G$ with generating set $\Sigma$, with the corresponding map $i\_G : \Sigma^\* \rightarrow G$. Construct the corresponding automaton $\cal{A}(G,\Sigma)$ with state set $G$ and which contains a transition $x \rightarrow\_a a.x$ for every $x \in G, a \in \Sigma$.

Let $H$ be a normal subgroup of $G$, and consider the quotient $Q = G / H$; we can view $Q$ as a finite group with generating set $\Sigma$, up to identifying each $a \in \Sigma$ with its class $aH$. By the factor theorem, there is a projection $j : G \rightarrow Q$ (mapping $x$ to $xH$) and an homomorphism $i\_Q : \Sigma^\* \rightarrow Q$ such that $i\_Q = j \circ i\_G$.

Consider the corresponding automata $A = \cal{A}(G,\Sigma)$ and $B = \cal{A}(Q,\Sigma)$. Define the relation $R$ by: $R(a,bH) \Leftrightarrow a \in bH$. This defines an automata relation: for every $u,v \in \Sigma^\*$ such that $u.a = v.a$, we have $i\_G(u) = i\_G(v)$ and thus $i\_Q(u) = i\_Q(v)$, implying that $u.(bH) = v.(bH)$.

Consider the tuple $T = (A,B,R)$. For every coset $k = tH \in Q$, it is easy to see that the set $R^{-1}(k)$ consists exactly of the elements of $k$, and that given an element $s \in G$, the operation $s^{-1} k$ gives the coset $(s^{-1} t) H$. As $H$ is a normal subgroup of $G$, we have $(s^{-1} t) H = (s^{-1} H) (t H)$, and in this case we obtain a "convolution product" over $Q$: given two weight functions $f,g$ over $Q(B)$, we obtain $\Theta\_{T,f,g}(s) = \sum\_{t \in Q} f(t) g(s^{-1} t)$. In particular, the function is stabilized by $H$, as for $r \in H$ the function $t \rightarrow (s^{-1} r s) t$ is a bijection over $Q$.

This suggests a possible connection with Fourier analysis and with the theta functions of integer lattices; there might be also a relation with the notion of harmonic functions over group actions. I'm not sure though if this is the kind of questions you are interested in.


---

