How many queries are needed to learn?
We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query complexity has previously been used to prove lower bounds on the time complexity of exact learning. We show a new relationship between query complexity and time complexity in exact learning: If any “honest” class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P = NP. In particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for Γp4.

title: On Single-Fault Set Diagnosability in the PMC Model
abstract: A. Somani et al, (1987) introduced the single-fault set diagnosability measure and gave an O(n/sup 3.5/) algorithm for determining it in the PMC model. The authors present a new algorithm for the same problem with a time complexity of only O(n/sup 2.5/).

title: On Bounds for a Board Covering Problem
abstract: On montre que k, le nombre minimal de reines couvrant entierement l'echiquier (n×n) est tel que [1/2n]≤k≤[2/3n]+2

title: Learning Monotone Term Decision Lists
abstract: We study the learnability of monotone term decision lists in the exact model of equivalence and membership queries. We show that, for any constant k≥0, k-term monotone decision lists are exactly and properly learnable with nO(k) membership queries in O(nk3) time. We also show nΩ(k) membership queries are necessary for exact learning. In contrast, both k-term monotone decision lists (k≥2) and general monotone decision lists are not learnable with equivalence queries alone.

title: Recognition Algorithms for Orders of Small Width and Graphs of Small Dilworth Number
abstract: Partially ordered sets of small width and graphs of small Dilworth number have many interesting properties and have been well studied. Here we show that recognition of such orders and graphs can be done more efficiently than by using the well-known algorithms based on bipartite matching and matrix multiplication. In particular, we show that deciding deciding if an order has width k can be done in O(kn2) time and whether a graph has Dilworth number k can be done in O(k2n2) time.For very small k we have even better results. We show that orders of width at most 3 can be recognized in O(n) time and of width at most 4 in O(nlog n).

title: Read-Twice DNF Formulas are Properly Learnable
abstract: We show that read-twice DNF formulas-Boolean formulas in disjunctive normal form in which each variable appears at most twice-are exactly and properly learnable in polynomial time. Our algorithm uses membership queries and proper equivalence queries and is based on a simple, new characterization of minimal read-twice DNF formulas. The algorithm improves on earlier results of Hancock and Aizenstein and Pitt which showed that read-twice DNF formulas are learnable using more powerful equivalence queries, i.e., where the hypotheses could be arbitrary DNF formulas. We also improve on the time-complexity of these earlier algorithms. Other results which may be of independent interest outside of learning follow directly from this paper. Specifically, we show that read-twice DNF formulas can be tested for equivalence in polynomial time and that the smallest read-twice formula equivalent to a given one can be found in polynomial time.

title: A Theoretical Framework for Association Mining Based on the Boolean Retrieval Model
abstract: Data mining has been defined as the non-trivial extraction of implicit, previously unknown and potentially useful information from data. Association mining is one of the important sub-fields in data mining, where rules that imply certain association relationships among a set of items in a transaction database are discovered. 
 
The efforts of most researchers focus on discovering rules in the form of implications between itemsets, which are subsets of items that have adequate supports. Having itemsets as both antecedent and precedent parts was motivated by the original application pertaining to market baskets and they represent only the simplest form of predicates. This simplicity is also due in part to the lack of a theoretical framework that includes more expressive predicates. 
 
The framework we develop derives from the observation that information retrieval and association mining are two complementary processes on the same data records or transactions. In information retrieval, given a query, we need to find the subset of records that matches the query. In contrast, in data mining, we need to find the queries (rules) having adequate number of records that support them. 
 
In this paper we introduce the theory of association mining that is based on a model of retrieval known as the Boolean Retrieval Model. The potential implications of the proposed theory are presented.

title: On the delusiveness of adopting a common space for modeling IR objects: are queries documents?
abstract: Many authors, who adopt the vector space model, take the view that documents, terms, queries, etc., are all elements within the same (conceptual) space. This view seems to be a natural one, given that documents and queries have the same vector notation. We show, however, that the structure of the query space can be very different from that of the document space. To this end, concepts like preference, similarity, term independence, and linearity, both in the document space and in the query space, are discussed. Our conclusion is that a more realistic and complete view of IR is obtained if we do not consider documents and queries to be elements of the same space. This conclusion implies that certain restrictions usually applied in the design of an IR system are obviated. For example, the retrieval function need not be restricted to the ones that have the possibility to be interpreted as a similarity measure.

title: Concept Based Retrieval Using Generalized Retrieval Functions
abstract: One of the essential goals in information retrieval is to bridge the gap between the way users would prefer to specify their information needs and the way queries are required to be expressed. Rule Based Information Retrieval by Computer (RUBRIC) is one of the approaches proposed to achieve this goal. This approach involves the use of production rules to capture user-query concepts (or topics). In RUBRIC, a set of related production rules is represented as an AND/OR tree, or alternatively by a disjunction of Minimal Term Sets (MTSs). The retrieval output is determined by the evaluation of the weighted Boolean expressions of the AND/OR tree, and processing efficiency can be enhanced by employing MTSs. However, since the weighted Boolean expression ignores the term-term association unless it is explicitly represented in the tree, the terminological gap between users' queries and their information needs may still remain. To solve this problem, we adopt the generalized vector space model (GVSM) and the p-norm based extended Boolean model. Experiments are performed for two variations of the RUBRIC model, extended with GVSM, as well as for the integrated use of RUBRIC with the p-norm based extended Boolean model. The results are compared to the original RUBRIC model based on recall-precision.