patternMinor
Determining if (infinite) binary language DFAs contain at least 1 prime?
Viewed 0 times
infinitedeterminingcontainlanguagedfasbinaryleastprime
Problem
This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. [1][2]) but not in any papers. Almost nothing seems to be known or published. I am looking for any nontrivial analysis or references.
Given: binary DFA D. Does L(D) contain at least 1 prime?
(Binary means Σ = {0, 1}.) As an example of something nontrivial about it (a subproblem), what can be said of the base-2 DFA language representations, what is their general form? Or, given any d, does there exist a DFA (language) that contains only multiples of d in binary? Are there arithmetic progressions embedded in DFA binary languages? Note there are many number theoretic investigations into primes in arithmetic sequences/ progressions and recent findings/ research, could any be demonstrated to be applicable?
[1] a simple problem whose decidability is not known / cstheory.SE
[2] are there any open problems left about DFAs? / cstheory.SE
Given: binary DFA D. Does L(D) contain at least 1 prime?
(Binary means Σ = {0, 1}.) As an example of something nontrivial about it (a subproblem), what can be said of the base-2 DFA language representations, what is their general form? Or, given any d, does there exist a DFA (language) that contains only multiples of d in binary? Are there arithmetic progressions embedded in DFA binary languages? Note there are many number theoretic investigations into primes in arithmetic sequences/ progressions and recent findings/ research, could any be demonstrated to be applicable?
[1] a simple problem whose decidability is not known / cstheory.SE
[2] are there any open problems left about DFAs? / cstheory.SE
Solution
It's a standard intro theory exercise that for any $d\ge 0$ there's a FA that accepts all and only those strings in $\{0, 1\}^*$ that are the binary representations of integer multiples of $d$. Thus, the answer to your second question is "yes".
For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language consists of those binary representations of
$$
\frac{10\cdot 4^n-4}{3}
$$
and clearly this sequence is too sparse to contain an arithmetic subsequence of any length greater than 2.
For your third question, the answer is "no". Consider the regular language denoted by $1(10)^*0$. This language consists of those binary representations of
$$
\frac{10\cdot 4^n-4}{3}
$$
and clearly this sequence is too sparse to contain an arithmetic subsequence of any length greater than 2.
Context
StackExchange Computer Science Q#48084, answer score: 6
Revisions (0)
No revisions yet.