Undecidability of state complexity
Arto K. Salomaa, Kai Salomaa, Sheng Yü · International Journal of Computer Mathematics · 2012
We consider the state complexity of compositions of regularity-preserving language operations. As our main result, we establish that determining the state complexity of an operation composed just from intersections and marked concatenations is undecidable. The proof relies on the undecidability of Hilbert's Tenth Problem. The languages used in the construction are over a fixed alphabet with at most 50 letters. We also consider some implications and generalizations, as well as discuss open problems.