Recognizable set

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.

This notion is different from the notion of recognizable language. Indeed, the term "recognizable" has a different meaning in computability theory.

Let ${\displaystyle N}$ be a monoid, a subset ${\displaystyle S\subseteq N}$ is recognized by a monoid ${\displaystyle M}$ if there exists a morphism ${\displaystyle \phi }$ from ${\displaystyle N}$ to ${\displaystyle M}$ such that ${\displaystyle S=\phi ^{-1}(\phi (S))}$, and recognizable if it is recognized by some finite monoid. This means that there exists a subset ${\displaystyle T}$ of ${\displaystyle M}$ (not necessarily a submonoid of ${\displaystyle M}$) such that the image of ${\displaystyle S}$ is in ${\displaystyle T}$ and the image of ${\displaystyle N\setminus S}$ is in ${\displaystyle M\setminus T}$.

...
Wikipedia