{
  "id": "enwiki-001370551737",
  "slug": "characteristic-samples",
  "title": "Characteristic samples",
  "qid": "",
  "lead": "Characteristic samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm I is given a set of pairs of strings and labels S , and returns a representation R that is consistent with S . Characteristic samples consider the scenario when the goal is not only finding a representation consistent with S , but finding a representation that recognizes a specific target language. A characteristic sample of language L is a set of pairs of the form (s, l(s)) where: # l(s) = 1 if and only if s\\in L # l(s) = -1 if and only if s\\notin L Given the characteristic sample S , I 's output on it is a representation R , e.g. an automaton, that recognizes L .",
  "body": "Characteristic samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm I is given a set of pairs of strings and labels S , and returns a representation R that is consistent with S . Characteristic samples consider the scenario when the goal is not only finding a representation consistent with S , but finding a representation that recognizes a specific target language. A characteristic sample of language L is a set of pairs of the form (s, l(s)) where: l(s) = 1 if and only if s\\in L l(s) = -1 if and only if s\\notin L Given the characteristic sample S , I 's output on it is a representation R , e.g. an automaton, that recognizes L . l(s) = 1\\text{ if and only if } s\\in L l(s) = -1 \\text{ if and only if } s\\notin L If equivalence is undecidable for a class \\mathbb{C} over \\Sigma of cardinality bigger than 1, then \\mathbb{C} doesn't have characteristic samples. Given a class of representations \\mathbb{C} such that equivalence is undecidable, for every polynomial p(x) and every n \\in \\mathbb{N} , there exist two representations r_1 and r_2 of sizes bounded by n , that recognize different languages but are inseparable by any string of size bounded by p(n) . Assuming this is not the case, we can decide if r_1 and r_2 are equivalent by simulating their run on all strings of size smaller than p(n) , contradicting the assumption that equivalence is undecidable. Given a class \\mathbb{C} that has characteristic samples, let R_1 and R_2 be representations that recognize L_1 and L_2 respectively. Under the assumption that there is a characteristic sample for L_1 , S_1 that is also consistent with L_2 , we'll assume falsely that there exist a characteristic sample for L_2 , S_2 that is consistent with L_1 . By the definition of characteristic sample, the inference algorithm I must return a representation which recognizes the language if given a sample that subsumes the characteristic sample itself. But for the sample S_1\\cup S_2 , the answer of the inferring algorithm needs to recognize both L_1 and L_2 , in contradiction. Given the sample from the adversary W , the construction of the automaton by the inference algorithm I starts with defining P = \\text{prefix}(W) and S = \\text{suffix}(W) , which are the set of prefixes and suffixes of W respectively. Now the algorithm constructs a matrix M where the elements of P function as the rows, ordered by the shortlex order, and the elements of S function as the columns, ordered by the shortlex order. Next, the cells in the matrix are filled in the following manner for prefix p_i and suffix s_j : If p_is_j \\in W \\rightarrow M_{ij} = l(p_is_j) else, M_{ij} = 0 Now, we say row i and t are distinguishable if there exists an index j such that M_{ij} = -1\\times M_{tj} . The next stage of the inference algorithm is to construct the set Q of distinguishable rows in M , by initializing Q with \\epsilon and iterating from the first row of M downwards and doing the following for row r_i : If r_i is distinguishable from all elements in Q , add it to Q else, pass on it to the next row From the way the teacher constructed the sample it passed to the adversary, we know that for every s \\in Q and every \\sigma \\in \\Sigma , the row s\\sigma exists in M , and from the construction of Q , there exists a row s' \\in Q such that s' and s\\sigma are indistinguishable. The output automaton will be defined as follows: The set of states is Q . The initial state is the state corresponding to row \\epsilon \\in Q . The accepting states is the set \\{s\\in Q|\\text{ } l(s)=1\\} . The transitions function will be defined \\delta(s,\\sigma) = s' , where s' is the element in Q that is indistinguishable from s\\sigma .",
  "categories": [
    "100622861",
    "100622909",
    "100622940",
    "23603337",
    "23933915",
    "24686817",
    "26220375",
    "26748027",
    "31347309",
    "9567816"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1370551737",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1787335552.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001370551737",
    "type": "webpage",
    "title": "Characteristic samples",
    "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/characteristic-samples",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          15
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001370551737",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1370551737",
    "note": "Immutable snapshot enwiki-001370551737"
  }
}