The most widely used notion of equivalence of regular expressions $r_1$ and $r_2$, or finite state automata ${A}_1$ and ${A}_2$ resp., over an alphabet $\Sigma$, is to consider their languages: we can define

$$r_1 \cong r_2 \qquad\text{iff}\qquad \mathsf{language}(r_1) = \mathsf{language}(r_2) $$ and likewise for ${A}_1 \cong {A}_2$. My question is about a natural generalisation: fix a set $S$ and define

$$r_1 \cong_{S} r_2 \qquad \text{iff} \qquad \mathsf{language}(r_1)\cap S = \mathsf{language}(r_2) \cap S$$

I call this "equivalence-up-to $S$". Clearly $\cong$, the standard equivalence, arises as special case with $S = \Sigma^*$. Equivalence-up-to a set is a natural and versatile construction, not restricted to regular languages, and I've seen it used before.

Question: Where can I find equivalence-up-to a set in older papers? Does it have a name, can it be found in one of the well-known textbooks on automata theory?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.