All Questions
Tagged with formal-languages nt.number-theory
7 questions
4
votes
0
answers
122
views
Are semilinear sets piecewise periodic?
I wanted to check my understanding of semilinear sets before I give a talk on them, and I haven't been able to find this exact perspective in any of the sources I've read through. Is it correct, and ...
- 429
6
votes
1
answer
561
views
How can I catalog these generalized Collatz problems?
The Collatz conjecture can be expressed in terms of a ruleset in the language $\{x,+,1,\rightarrow,;\}$:
$x + x + 1 \rightarrow x+x+x+1+1;$
$x + x \rightarrow x;$
Whenever a number matches the LHS ...
- 2,302
2
votes
1
answer
133
views
What is the cardinality of the set of Dyck natural numbers of semilength $k$?
In arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I show that there is a 1:1 correspondence between $\mathbb{N} = \{0,1,2,3,4,\ldots\}$ and $\mathcal{D}_{r_{\...
- 129
-1
votes
1
answer
125
views
Prove using Dyck naturals: for $n \in \mathbb{N}_{+}$ and big enough $k \in \mathbb{N}_{+}$, $p_{k-1} < \cdots < np_{k-a_{n}}$ (a is A073093)
While conducting research in connection with arXiv:2102.02777 ("Recursive Prime Factorizations: Dyck Words as Numbers"), I noticed certain interesting patterns, one of which inspired the ...
- 129
19
votes
3
answers
1k
views
Status of an open problem about semilinear sets
In his book "The Mathematical Theory of Context-Free Languages" (1966), Ginsburg mentioned the following open problem:
Find a decision procedure for determining if an arbitrary semilinear set
is a ...
- 373
-1
votes
2
answers
2k
views
Any grammar for the language $L =a^p$, $p$ is prime number of $\mathbb{N}$
Any grammar for the language
$$L =a^p,\text{ $p$ is prime and }p\in \mathbb{N}?$$
Is such a grammar related to any question of number theory like RH or the conjecture of twin primes?
- 3,084
0
votes
1
answer
158
views
any given c.e.set has number M whose power bounds the corresponding elements of S?
For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq ...
- 3,084