{
  "id": "enwiki-001211319383",
  "slug": "recognizable-set",
  "title": "Recognizable set",
  "qid": "",
  "lead": "In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism 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.",
  "body": "In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism 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. ==Definition== Let N be a monoid, a subset S\\subseteq N is recognized by a monoid M if there exists a homomorphism \\phi from N to M such that S=\\phi^{-1}(\\phi(S)) , and recognizable if it is recognized by some finite monoid. This means that there exists a subset T of M (not necessarily a submonoid of M ) such that the image of S is in T and the image of N \\setminus S is in M \\setminus T . ==Example== Let A be an alphabet: the set A^* of words over A is a monoid, the free monoid on A . The recognizable subsets of A^* are precisely the regular languages. Indeed, such a language is recognized by the transition monoid of any automaton that recognizes the language. The recognizable subsets of \\mathbb N are the ultimately periodic sets of integers. ==Properties== A subset of N is recognizable if and only if its syntactic monoid is finite. The set \\mathrm{REC}(N) of recognizable subsets of N is closed under: union intersection complement right and left quotient Mezei's theorem states that if M is the product of the monoids M_1, \\dots, M_n , then a subset of M is recognizable if and only if it is a finite union of subsets of the form R_1 \\times \\cdots \\times R_n , where each R_i is a recognizable subset of M_i . For instance, the subset \\{1\\} of \\mathbb N is rational and hence recognizable, since \\mathbb N is a free monoid. It follows that the subset S=\\{(1,1)\\} of \\mathbb N^2 is recognizable. McKnight's theorem states that if N is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole N is always recognizable but it is not rational if N is infinitely generated. Conversely, a rational subset may not be recognizable, even if N is finitely generated. In fact, even a finite subset of N is not necessarily recognizable. For instance, the set \\{0\\} is not a recognizable subset of (\\mathbb Z, +) . Indeed, if a homomorphism \\phi from \\mathbb Z to M satisfies \\{0\\}=\\phi^{-1}(\\phi(\\{0\\})) , then \\phi is an injective function; hence M is infinite. Also, in general, \\mathrm{REC}(N) is not closed under Kleene star. For instance, the set S=\\{(1,1)\\} is a recognizable subset of \\mathbb N^2 , but S^*=\\{(n, n)\\mid n\\in \\mathbb N\\} is not recognizable. Indeed, its syntactic monoid is infinite. The intersection of a rational subset and of a recognizable subset is rational. Recognizable sets are closed under inverse of homomorphisms. I.e. if N and M are monoids and \\phi:N\\rightarrow M is a homomorphism then if S\\in\\mathrm{REC}(M) then \\phi^{-1}(S)=\\{x\\mid \\phi(x)\\in S\\}\\in\\mathrm{REC}(N) . For finite groups the following result of Anissimov and Seifert is well known: a subgroup H of a finitely generated group G is recognizable if and only if H has finite index in G. In contrast, H is rational if and only if H is finitely generated. ==See also== Rational set Rational monoid ==References== Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets",
  "categories": [
    "22914317",
    "22947451",
    "24043274",
    "24745122",
    "27894481"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1211319383",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1709331285.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001211319383",
    "type": "webpage",
    "title": "Recognizable set",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/recognizable-set",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          20
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001211319383",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1211319383",
    "note": "Immutable snapshot enwiki-001211319383"
  }
}