2
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Oct 21 '20 at 5:58
  • 1
    $\begingroup$ There is a lot of literature on automatic structures. Use Google. $\endgroup$
    – Emil Jeřábek
    Oct 21 '20 at 6:29
  • 2
    $\begingroup$ 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 ... $\endgroup$
    – Emil Jeřábek
    Oct 21 '20 at 8:38
  • 2
    $\begingroup$ ... 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. $\endgroup$
    – Emil Jeřábek
    Oct 21 '20 at 8:41
  • 2
    $\begingroup$ 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). $\endgroup$
    – Emil Jeřábek
    Oct 21 '20 at 14:37
5
$\begingroup$

$\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.

Improve this answer
$\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.