3
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Just a note: the problem is decidable over unary alphabets ($\Sigma = \{1\}$). Indeed, in that case, the regular language forms a semilinear set; so for each one of the arithmetic progressions $\{a + ib \mid i > 0\}$ of the semilinear set (that can be computed efficiently), if $a,b$ are coprimes, then by Dirichlet's theorem, the sequence contains infinite primes. $\endgroup$ – Vor Oct 13 '15 at 16:40
  • $\begingroup$ fyi/ thx MW for this ref in chat: Minimal Elements for the Prime Numbers/ Bright, Devillers, Shallit $\endgroup$ – vzn Apr 8 '16 at 16:56
6
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ To hint at how to construct such a DFA for a given $d$: make the initial state the only final state, and count modulo $d$. $\endgroup$ – G. Bach Oct 10 '15 at 23:48

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.