<p><span class="math-container">$\beta(E_1)$</span> is the language <span class="math-container">$s^nx,s^{n+1}x$</span>. This language is straightforwardly not regular, by the pumping lemma.</p>
<p>If we assume that the language is regular, the pumping lemma tells us that there must exist some <span class="math-container">$p, q$</span> such that for all <span class="math-container">$n \ge p$</span>, <span class="math-container">$s^{n+q}x,s^{n+1}x$</span> is also in the language. This is false, meaning that the language is not regular.</p>
<p>A similar argument also demonstrates that <span class="math-container">$\beta(E_2)$</span> is not regular, and more generally demonstrates that for a graph to be regular, for any <span class="math-container">$(n, m)$</span> in the graph with <span class="math-container">$n$</span> greater than some finite cutoff <span class="math-container">$p$</span>, there must be infinitely many <span class="math-container">$n'$</span> such that <span class="math-container">$(n', m)$</span> is in the graph.</p>
<p>Since both <span class="math-container">$E_1$</span> and <span class="math-container">$E_2$</span> fail this condition, they are not regular.</p>

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

CC BY-SA 4.0
2020-10-21T05:58:43.210Z
The more natural way to encode a binary relation in this context is to *interleave* the components instead of concatenating them, or equivalently, encode the $i$th symbol of the first component and the $i$th symbol of the second component jointly as the $i$th symbol of the final word (using a larger alphabet). Graphs that are regular languages under this representation are special cases of *automatic structurures*.
Emil Jeřábek
CC BY-SA 4.0
2020-10-21T06:19:53.203Z
@EmilJeřábek Can you elaborate on that?  I.e. is there some way to precisely characterize such graphs using the encoding you describe?
wanderingmathematician
CC BY-SA 4.0
2020-10-21T06:29:37.600Z
There is a lot of literature on automatic structures. Use Google.
Emil Jeřábek
CC BY-SA 4.0
2020-10-21T08:38:53.010Z
But to elaborate, the answer to what graphs can be encoded as regular languages is that you are using a wrong definition of encoding. With the right definition, it becomes the class of automatic graphs, a very interesting, rich, and well studied class with many nice properties concerning descriptive complexity, decidability, etc. Both your examples are automatic (the second one if vertex labels are written more efficiently). In contrast, under your definition, virtually no interesting graphs are regular: it is trivial to prove that the only graphs that are regular under your encoding are ...
Emil Jeřábek
CC BY-SA 4.0
2020-10-21T08:41:28.360Z
... finite unions $\bigcup_{i<k}L_i\times L'_i$ where $L_i$ and $L'_i$ are regular sets. In fact, since your vertex labels are natural numbers written in unary, you can take $L_i$ and $L'_i$ to be arithmetic progressions.
Emil Jeřábek
CC BY-SA 4.0
2020-10-21T14:09:38.807Z
@EmilJeřábek That's very helpful.  Further question: I see there's a fundamental trait that first order definable relations are encodable into an automatic structure so it makes sense why addition (hence $E_1$) is encodable.  However, defining multiplication in general requires either a second order arithmetic axiom or an infinite number of first order axioms to define.  That being the case, what's the easiest way to see that $E_m'$ is still encodable as an automatic structure?
wanderingmathematician
CC BY-SA 4.0
2020-10-21T14:37:32.230Z
Multiplication by a *constant* is first-order definable from addition. (Note that you need to write the numbers in binary (or decimal) for either of these to work.) Or you can show directly that multiplication by a constant can be implemented by an algorithm using a single pass (starting from the least-significant bit) over the input with $O(1)$ working space (which can be encoded in the state of the machine).
Emil Jeřábek
<complexity-classes><fl.formal-languages><pl.programming-languages><regular-language><regular-expressions>
What graphs on $\mathbb{N}$ can be encoded as regular languages?
wanderingmathematician
# What graphs on $\mathbb{N}$ can be encoded as regular languages?

(Asked by: username_0 on 2020-10-21)

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

**Tags:** complexity-classes, fl.formal-languages, pl.programming-languages, regular-language, regular-expressions

> **Comments:**
> **username_1**: The more natural way to encode a binary relation in this context is to *interleave* the components instead of concatenating them, or equivalently, encode the $i$th symbol of the first component and the $i$th symbol of the second component jointly as the $i$th symbol of the final word (using a larger alphabet). Graphs that are regular languages under this representation are special cases of *automatic structurures*.  
> **username_0**: @EmilJeřábek Can you elaborate on that?  I.e. is there some way to precisely characterize such graphs using the encoding you describe?  
> **username_1**: There is a lot of literature on automatic structures. Use Google.  
> **username_1**: But to elaborate, the answer to what graphs can be encoded as regular languages is that you are using a wrong definition of encoding. With the right definition, it becomes the class of automatic graphs, a very interesting, rich, and well studied class with many nice properties concerning descriptive complexity, decidability, etc. Both your examples are automatic (the second one if vertex labels are written more efficiently). In contrast, under your definition, virtually no interesting graphs are regular: it is trivial to prove that the only graphs that are regular under your encoding are ...  
> **username_1**: ... finite unions $\bigcup_{i<k}L_i\times L'_i$ where $L_i$ and $L'_i$ are regular sets. In fact, since your vertex labels are natural numbers written in unary, you can take $L_i$ and $L'_i$ to be arithmetic progressions.  
> **username_0**: @EmilJeřábek That's very helpful.  Further question: I see there's a fundamental trait that first order definable relations are encodable into an automatic structure so it makes sense why addition (hence $E_1$) is encodable.  However, defining multiplication in general requires either a second order arithmetic axiom or an infinite number of first order axioms to define.  That being the case, what's the easiest way to see that $E_m'$ is still encodable as an automatic structure?  
> **username_1**: Multiplication by a *constant* is first-order definable from addition. (Note that you need to write the numbers in binary (or decimal) for either of these to work.) Or you can show directly that multiplication by a constant can be implemented by an algorithm using a single pass (starting from the least-significant bit) over the input with $O(1)$ working space (which can be encoded in the state of the machine).  

---

## 1 answers

### Answer by username_2 on 2020-10-21. Score: 5

$\beta(E\_1)$ is the language $s^nx,s^{n+1}x$. This language is straightforwardly not regular, by the pumping lemma.

If we assume that the language is regular, the pumping lemma tells us that there must exist some $p, q$ such that for all $n \ge p$, $s^{n+q}x,s^{n+1}x$ is also in the language. This is false, meaning that the language is not regular.

A similar argument also demonstrates that $\beta(E\_2)$ is not regular, and more generally demonstrates that for a graph to be regular, for any $(n, m)$ in the graph with $n$ greater than some finite cutoff $p$, there must be infinitely many $n'$ such that $(n', m)$ is in the graph.

Since both $E\_1$ and $E\_2$ fail this condition, they are not regular.


---

