From Decidability to Undecidability by Considering Regular Sets of Instances

Abstract

We are lifting classical problems from single instances to regular sets of instances. The task of finding a positive instance of the combinatorial problem $P$ in a potentially infinite given regular set is equivalent to the so called intreg-problem of $P$, which asks for a given DFA $A$, whether the intersection of $P$ with $L(A)$ is non-empty. The intreg-problem generalizes the idea of considering multiple instances at once and connects classical combinatorial problems with the field of automata theory. While the question of the decidability of the intreg-problem has been answered positively for several NP- and even PSPACE-complete problems, we are presenting natural problems even from L with an undecidable intreg-problem. We also discuss alphabet sizes and different encoding-schemes elaborating the boundary between problem-variants with a decidable respectively undecidable intreg-problem.