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:

  1. Accept every word $w\in I\cap L$.
  2. 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$).

  • 6
    $\begingroup$ Aren't these just promise-problems for automata? If so, perhaps this paper can be a good start. $\endgroup$ – Shaull Sep 13 '14 at 14:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.