Suppose I represent the natural number 0 by "x", and use the symbol "s" for successor so that I get the following encoding of $\alpha : \mathbb{N} \rightarrow V$ of natural numbers into a formal language $V$:
$0 \mapsto x$, $1 \mapsto sx$, $2 \mapsto ssx$, $3 \mapsto sssx$, etc
So $V = \{x, sx, ssx, sssx, ... \}$ is a regular language generated by the regex $s^*x$.
Now, Suppose $G = (\mathbb{N},E \subset \mathbb{N} \times \mathbb{N})$ is a directed graph. An edge $e = (n, m) \in E$. I now define an encoding $\beta : E \rightarrow W$ of edges into a new language $W$ using the following encoding
$(n,m) \mapsto \alpha(n),\alpha(m)$ (i.e. concatenate the encoding of each number's encoding with a separating comma). For example, $W((3,1)) = $"sssx,sx"
Question: For what graphs $G$ of this type is $W$ a regular language?
Obviously if $E$ has a product structure such as $E = \{ (n, m) \ | \ n \in R_1, \ m \in R_2\}$ where each $R_i \subset \mathbb{N}$ corresponds to a regular language, then $W$ would be regular. But what about more "natural" relations on $\mathbb{N}$? In particular, here are two particular examples I am especially interested in:
Ex 1: $E_1 = \{ (n, n+1) \ | \ n \in \mathbb{N} \}$. Is $\beta(E_1)$ a regular language?
Ex 2: $E_m' = \{ (n, n \times m) \ | \ n \in \mathbb{N} \}$ (i.e. an edge from each natural number to its product with a fixed natural number $m$). Is $\beta(E_m')$ a regular language?
Any help is much appreciated :)