In the classic setting, an automaton for a language $L$ is required to accept all words in $L$ and reject/get stuck on every word in $\Sigma^*\setminus L$.
All of the related concepts are then defined with respect to $\Sigma^*$ as the possible inputs (e.g. $L$'s regularity/CF/state complexity/ etc.).
But we can think of a model where the possible input is some set $I\subseteq \Sigma^*$, and consider $L$'s attributes with respect to $I$.
Formally, an automaton for a language $L$ with respect to possible input set $I$ is required to:
- Accept every word $w\in I\cap L$.
- Reject every word in $I\setminus L$.
(i.e. its action on $\Sigma^*\setminus I$ could be arbitrary).
If such automaton exists, we say that $L$ is regular with respect to $I$.
If this model is known, can anyone provide a reference?
An immediate result that if $I$ is finite, every language (including, say, the Halting Problem) becomes regular w.r.t. $I$.
How can we characterize the requirements from $L$,$I$ such that $L$ is regular with respect to $I$?
Note that this is not the same as $L\cap I$ being regular (e.g. $I\subseteq L$ for some non-regular language $I$).
