patternMinor
Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular
Viewed 0 times
provingmidgeqregularthat
Problem
We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can be generated just by concatenating $0^9$. Hence we can represent $L^$ using a FSM.
My Question :
-
Here I got these numbers $120$–$128$ for $m^2$ by trial and error. Is there any formal method to arrive at these numbers?
-
If we consider $m^2$ to be a function such that we get $L^*$ is regular, will it also be regular for $m^3$?
My Question :
-
Here I got these numbers $120$–$128$ for $m^2$ by trial and error. Is there any formal method to arrive at these numbers?
-
If we consider $m^2$ to be a function such that we get $L^*$ is regular, will it also be regular for $m^3$?
Solution
Consider the language
$$
L = \{ 0^{m^k} : m \geq m_0 \}.
$$
Since $m_0$ and $m_0+1$ are relatively prime, so are $m_0^k$ and $(m_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m_0^k$ and $(m_0+1)^k$, implying that
$$L^* \supseteq \{ 0^m : m \geq M_0 \}$$
for some $M_0$, and so $L^*$ is regular. Using the classical formula of the coin problem applied to $m_0^k$ and $(m_0+1)^k$, we can upper bound the optimal value of $M_0$ by
$$
M_0 \leq (m_0^k-1)((m_0+1)^k-1).
$$
For example, the case considered in your post has $k=2$ and $m_0=3$, and this gives the bound $M_0 \leq (3^2-1)(4^2-1) = 120$, which is (apparently) tight in this case.
Recently it has been shown that it is $\Sigma_2^P$ hard to determine the largest integer which cannot be represented as a non-negative combination of given positive integers (Matsubara 2016), though in your particular case the set $\{ m^k : m \geq m_0 \}$ has a lot of structure, and so the problem might be feasible.
$$
L = \{ 0^{m^k} : m \geq m_0 \}.
$$
Since $m_0$ and $m_0+1$ are relatively prime, so are $m_0^k$ and $(m_0+1)^k$. Hence every large enough integer is a non-negative integer combination of $m_0^k$ and $(m_0+1)^k$, implying that
$$L^* \supseteq \{ 0^m : m \geq M_0 \}$$
for some $M_0$, and so $L^*$ is regular. Using the classical formula of the coin problem applied to $m_0^k$ and $(m_0+1)^k$, we can upper bound the optimal value of $M_0$ by
$$
M_0 \leq (m_0^k-1)((m_0+1)^k-1).
$$
For example, the case considered in your post has $k=2$ and $m_0=3$, and this gives the bound $M_0 \leq (3^2-1)(4^2-1) = 120$, which is (apparently) tight in this case.
Recently it has been shown that it is $\Sigma_2^P$ hard to determine the largest integer which cannot be represented as a non-negative combination of given positive integers (Matsubara 2016), though in your particular case the set $\{ m^k : m \geq m_0 \}$ has a lot of structure, and so the problem might be feasible.
Context
StackExchange Computer Science Q#95414, answer score: 6
Revisions (0)
No revisions yet.