Characteristic samples

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages) This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles; try the Find link tool for suggestions. (September 2024) This article may be too technical for most readers to understand. Please help improve it to make it understandable to non-experts, without removing the technical details. (September 2024) (Learn how and when to remove this message) (Learn how and when to remove this message)

Characteristic samples is a concept in the field of grammatical inference, related to passive learning. In passive learning, an inference algorithm ${\displaystyle I}$ is given a set of pairs of strings and labels ${\displaystyle S}$, and returns a representation ${\displaystyle R}$ that is consistent with ${\displaystyle S}$. Characteristic samples consider the scenario when the goal is not only finding a representation consistent with ${\displaystyle S}$, but finding a representation that recognizes a specific target language.

A characteristic sample of language ${\displaystyle L}$ is a set of pairs of the form ${\displaystyle (s,l(s))}$ where:

1. ${\displaystyle l(s)=1}$ if and only if ${\displaystyle s\in L}$
2. ${\displaystyle l(s)=-1}$ if and only if ${\displaystyle s\notin L}$

Given the characteristic sample ${\displaystyle S}$, ${\displaystyle I}$'s output on it is a representation ${\displaystyle R}$, e.g. an automaton, that recognizes ${\displaystyle L}$.