Alternating state complexity of the set of primes and squarefree integers
Jan‐Christoph Schlage‐Puchta · arXiv (Cornell University) · 2023
We show that the set of prime numbers has exponential alternating complexity, proving a conjecture by Fijalkow. We further show that the set of squarefree integers has essentially maximal possible alternating complexity.