0
$\begingroup$

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.)

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.