Undecidability of state complexity

Abstract

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.

Keywords:

• deterministic finite automaton
• state complexity
• undecidability
• combined operations
• marked concatenation

2010 AMS Subject Classification::

• 68Q45

Acknowledgements

This work was supported by Natural Science and Engineering Council of Canada Discovery Grants 147224 and 41630. A preliminary version of this paper was presented at LATA 2011.