Before revision:  The oracle can answer queries of the form " Is s a substring of S? " . The Substring Query Complexity of a string S, denoted \chi(S), is the minimum number of adaptive substring queries that are needed to exactly reconstruct (or learn) S. It has been introduced in 1995 by Skiena and Sundaram, who showed that \chi(S) \geq \sigma n/4 -
After revision:  The oracle can answer queries of the form `` Is s a substring of S? " . The Substring Query Complexity of a string S, denoted \chi(S), is the minimum number of adaptive substring queries that are needed to exactly reconstruct (or learn) S. It has been introduced in 1995 by Skiena and Sundaram, who showed that \chi(S) \geq \sigma n/4 -