Decision lists and related Boolean functions.
We consider Boolean functions represented by decision lists, and study their relationships to other classes of Boolean functions. It turns out that the elementary class of 1-decision lists has interesting relationships to independently defined classes such as disguised Horn functions, read-once functions, nested differences of concepts, threshold functions, and 2-monotonic functions. In particular, 1-decision lists coincide with fragments of the mentioned classes. We further investigate the recognition problem for this class, as well as the extension problem in the context of partially defined Boolean functions (pdBfs). We show that finding an extension of a given pdBf in the class of 1-decision lists is possible in linear time. This improves on previous results. Moreover, we present an algorithm for enumerating all such extensions with polynomial delay.
Introduction
Decision lists have been proposed in [31] as a specification of Boolean functions which amounts to a simple
strategy for evaluating a Boolean function on a given assignment. This approach has been become popular
in learning theory, since bounded decision lists naturally generalize other important classes of Boolean
functions. For example, k-bounded decision lists generalize the classes whose members have a CNF or
DNF expression where each clause or term, respectively, has at most k literals, and, as a consequence,
also those classes whose members have a DNF or CNF containing at most k terms or clauses, respectively.
Another class covered by decision lists the one of decision trees [30].
Informally, a decision list can be written as a cascaded conditional statement of the form:
else b d
where each t i (v) means the evaluation of a term t i , i.e., a conjunction of Boolean literals, on an assignment
v to the x each b i is either 0 (false) or 1 (true).
The important result established in [31] is that k-decision lists, i.e., decision lists where each term t i has
at most k literals and k is a constant, are probably approximately correct (PAC) learnable in Valiant's model
[35]. This has largely extended the classes of Boolean functions which are known to be learnable. In the
sequel, decision lists have been studied extensively in the learning field, see e.g. [18, 8, 16, 9].
However, while it is known that decision lists generalize some classes of Boolean functions [31], their relationships
to other classes such as Horn functions, read-once functions, threshold functions, or 2-monotonic
functions, which are widely used in the literature, were only partially known (cf. [5, 3]). It thus is interesting
to know about such relationships, in particular whether fragments of such classes correspond to decision
lists and how such fragments can be alternatively characterized. This issue is intriguing, since decision lists
are operationally defined, while other classes such as Horn functions or read-once functions are defined on
a semantical (in terms of models) or syntactical (in terms of formulas) basis, respectively.
In this paper, we shed light on this issue and study the relationship of decision lists to the classes mentioned
above. We focus on the elementary class of 1-decision lists (C 1-DL ), which has received a lot of attention
and was the subject of a number of investigations, eg. [31, 26, 8, 9]. It turns out that this class relates in an
interesting way to several other classes of Boolean functions. In particular, it coincides with independently
defined semantical and syntactical such classes, as well as with the intersections of other well-known classes
of Boolean functions. We find the following characterizations of C 1-DL . It coincides with
ffl C R
DH , the renaming-closure of the class of functions f such that both f and its complement f are Horn
[12] (also called disguised "double" Horn functions);
ffl CND , the class of nested differences of concepts [20], where each concept is described by a single
the intersection of the classes of 2-monotonic functions [29] and read-once functions,
i.e., functions definable by a formula in which each variable occurs at most once [17, 23, 35, 34].
the intersection of threshold functions (also called linearly separable functions) [29] and
read-once functions; and,
ffl CLR-1 , the class of linear read-once functions [12], i.e., functions represented by a read-once formula
such that each binary connective involves at least one literal.
Observe that the inclusion C 1-DL ' C TH " CR-1 follows from the result that C 1-DL ' C TH [5, 3] and the
fact that C 1-DL ' CR-1 ; however, the converse was not known.
The above results give us new insights into the relationships between these classes of functions. Moreover,
they provide us with a semantical and syntactical characterization of 1-decision lists in terms of (renamed)
Horn functions and read-once formulas. On the other hand, we obtain characterizations of the intersections
of well-known classes of Boolean functions in terms of operationally, semantically, and syntactically defined
classes of Boolean functions.
As we show, a natural generalization of the results from 1-decision lists to k-bounded decision lists fails
in almost all cases. The single exception is the coincidence with nested differences of concepts, which
holds for an appropriate base class generalizing terms. Thus, our results unveil characteristic properties of
1-decision lists and, vices versa, of the intersections of classes of Boolean functions to which they coincide.
Furthermore, we study computational problems on 1-decision lists. We consider recognition from a formula
(also called membership problem [19] and representation problem [4, 1]) and problems in the context
of partially defined Boolean functions.
A partially defined Boolean function (pdBf) can be viewed as a pair (T ; F ) of sets T and F of true and
false vectors v 2 f0; 1g n , respectively, where T " It naturally generalizes a Boolean function,
by allowing that the range function values on some input vectors are unknown. This concept has many
applications, e.g., in circuit design, for representation of cause-effect relationships [7], or in learning, to
mention a few. A principal issue on pdBfs is the following: Given a pdBf (T ; F ), determine whether some
f in a particular class of Boolean functions C exists such that T ' T (f) and F ' F (f), where T (f) and
F (f) denote the sets of true and false vectors of f , respectively. Any such f is called an extension of f in C,
and finding such an f is known as the extension problem [6, 27]. Since in general, a pdBf may have multiple
extensions, it is sometimes desired to know all extensions, or to compute an extension of a certain quality
(e.g., one described by a shortest formula, or having a smallest set T (f) ).
The extension problem is closely related to problems in machine learning. A typical problem there is the
following ([4]). Suppose there are n Boolean valued attributes; then, find a hypothesis in terms of a Boolean
function f in a class of Boolean functions C, which is consistent with the actual correlation of the attributes
after seeing a sample of positive and negative examples, where it is known that the actual correlation is a
function g in C. In our terms, a learning algorithm produces an extension of a pdBf. However, there is a
subtle difference between the general extension problem and the learning problem: in the latter problem,
an extension is a priori known to exist, while in the former, this is unknown. A learning algorithm might
take advantage of this knowledge and find an extension faster. The extension problem itself is known as
the consistency problem [4, 1]; it corresponds to learning from a sample which is possibly spoiled with
inconsistent examples.
In this context, it is also interesting to know whether the pdBf given by a sample uniquely defines a
Boolean function in C; if the learner recognizes this fact, she/he has identified the function g to be learned.
This is related to the question whether a pdBf has a unique extension, which is important in the context of
teaching [32, 22, 33, 15]. There, to facilitate quicker learning, the sample is provided by a teacher rather than
randomly drawn, such that identification of the function g is possible from it (see e.g. [5, 15] for details).
Any sample which allows to identify a function in C is called a teaching sequence (or specifying sample
[5]). Thus, the issue of whether a given set of labeled examples is a teaching sequence amounts to the issue
of whether S, seen as a pdBf, has a unique extension in C. A slight variant is that the sample is known
to be consistent with some function g in C. In this case, the problem amounts to the unique extension
problem knowing that some extension exists; in general, this additional knowledge could be utilized for
faster learning.
Alternative teaching models have been considered, in which the sample given by the teacher does not
precisely describe a single function [16]. However, identification of the target function is still possible, since
the teacher knows how the learner proceeds, and vice versa, the learner knows how the teacher generates
his sample, called a teaching set in [16]. To prevent "collusion" between the two sides (the target could be
simply encoded in the sample), an adversary is allowed to spoil the teaching set by adding further examples.
Our main results on the above issues can be summarized as follows:
Recognizing 1-decision lists from a formula is tractable for a wide class of formulas, including Horn
formulas, 2-CNF and 2-DNF, while unsurprisingly intractable in the general case.
ffl We point out that the extension problem for C 1-DL is solvable in linear time. This improves on the
previous result that the extension problem for C 1-DL is solvable in polynomial time [31]. As a consequence,
a hypothesis consistent with a target function g in C 1-DL on the sample can be generated in linear time. In
particular, learning from a (possibly spoiled) teaching sequence is possible in linear time. We obtain as a
further result an improvement to [16], where it is shown that learning a function g in C 1-DL from a particular
teaching set is possible in O(m 2 n) time, where m is the length of a shortest 1-decision list for g, n is the
number of attributes, and the input size is assumed to be O(mn). Our algorithm can replace the learning
algorithm in [16], and finds the target in O(nm) time, i.e., in linear time. We mention that [8] presents the
result, somewhat related to [16], that 1-decision lists with k alternations (i.e., changes of the output value))
are PAC learnable, where the algorithm runs in O(n 2 m) time.
ffl We present an algorithm which enumerates all extensions (given by formulas) of a pdBf in C 1-DL with
polynomial delay. As a corollary, the problems of deciding whether a given set of any examples is a teaching
sequence and whether a consistent sample is a teaching sequence are both solvable in polynomial time.
Moreover, a small number of different hypotheses (in fact, even up to polynomially many) for the target
function can be produced within polynomial time.
The rest of this paper is organized as follows. The next section provides some preliminaries and fixes
notation. In Section 3, we study the relationships of 1-decision lists to other classes of functions. In Section
4, we address the recognition problem from formulas, and in Section 5, we study the extension problem.
Section 6 concludes the paper.
Preliminaries
We use x to denote Boolean variables and letters u; v; w to denote vectors in f0; 1g n . The i-th
component of a vector v is denoted by v i . Formulas are built over the variables using the connectives -;
and :. A term t is a conjunction
literals such that P (t) "
a clause c is defined dually (change - to -); t (resp., c) is Horn, if jN(t)j - 1 (resp., P (c) - 1). We use
and ? to denote the empty term (truth) and the empty clause (falsity), respectively. A disjunctive normal
are Horn. Similarly, a conjunctive normal form (CNF)
Horn, if all c i are Horn.
E.g., the term f2g, and is Horn, while the clause
thus it is not Horn.
A partially defined Boolean function (pdBf) is a mapping defined by
and denotes a set of true vectors (or positive examples), F ' f0; 1g n
denotes a set of false vectors (or negative examples), and T " ;. For simplicity, we denote a pdBf by
It can be seen as a representation for all (total) Boolean functions (Bfs)
that any such f is called an extension of
We often identify a formula ' with the Bf which it defines. A term t is an implicant of a Bf f , if t - f
holds, where - is the usual ordering defined by f - g $ T (f) ' T (g). Moreover, t is prime if no proper
subterm t 0 of t is an implicant of f . A DNF
if each term t i is a prime implicant of ' and
no term t i is redundant, i.e., removing t i from ' changes the function.
A decision list L is a finite sequence of pairs
defines a Bf f : f0; 1g
f0; 1g by )g. We call a Bf sometimes a decision list, if f is definable
by some decision list; this terminology is inherited to restricted decision lists.
A k-decision list is a decision list where each term t i contains at most k literals; we denote by C k-DL the
class of all (functions represented by) k-decision lists. In particular, C 1-DL is the class of decision lists where
each term is either a single literal or empty. A decision list is monotone [15], if each term t in it is positive,
k-DL we denote the restriction of C k-DL to monotone decision lists.
A Bf f is Horn, if F is denotes the closure of set S ' f0; 1g n of vectors
under component-wise conjunction - of vectors; by C Horn we denote the class of all Horn functions. It
is known that f is Horn if and only if f is represented by some Horn DNF. If f is also represented by a
positive DNF, i.e., a DNF in which each term is positive, then f is called positive; C pos denotes the class of
all positive functions.
For any vector w 2 f0; 1g n , we define 0g. The
renaming of an n-ary Bf f by w, denoted f w , is the Bf f(x \Phi w), i.e., T (f w
where \Phi is componentwise addition modulo 2 (XOR). For any class of Bfs C, we denote by C R the closure
of C under renamings. The renaming of a formula ' by w, denoted ' w , is the formula resulting from ' by
replacing each literal involving a variable x i with w its opposite. E.g., let
Then, the renaming of f by
3 Characterizations of 1-Decision Lists
Read-once functions. A function f is called read-once, if it can be represented by read-once formula,
i.e., a formula without repetition of variables. The class CR-1 of read-once functions has been extensively
studied in the literature, cf. [34, 24, 35, 28, 21, 17, 23, 11].
Definition 3.1 Define the class FLR-1 of linear read-once formulas by the following recursive form:
(2) if ' 2 FLR-1 and x i is a variable not occurring in ', then x i -', x i -', x i -', x i -' 2 FLR-1 .
Call a Bf f linear read-once [12], if it can be represented by a formula in FLR-1 , and let CLR-1 denote the
class of all such functions. E.g., x 1 x 2 not.
Note that two read-once formulas are equivalent if and only if they can be transformed through associativity
and commutativity into each other [21]. Hence, the latter formula does not represent a linear read-once
function.
The following is now easy to see (cf. also [5, p. 11]):
Proposition 3.1
Note that any ' 2 FLR-1 is convertible into an equivalent 1-decision list in linear time and vice versa.
Horn functions. We next give a characterization in terms of Horn functions. A Bf f is called double Horn
[13], if T (f)). The class of these functions is denoted by CDH . Note
that f is double Horn if and only if f and f are Horn. E.g.,
is double Horn, because
is Horn. Alternatively, a Bf f is double Horn if and only if it has both a Horn DNF and a Horn CNF
representation. In the previous example, this is easily seen to be the case. The class of double Horn functions
has been considered in [13, 12] for giving T (f) and F (f) a more balanced role in the process of finding a
Horn extension.
We can show the somewhat unexpected result that the classes C R
DH and CLR-1 coincide (and hence C R
This gives a precise syntactical characterization of the semantically defined class C R
and, by the previous result, a semantical characterization of C 1-DL .
The proof of this result is based on the following lemma, which can be found in [13, 12]. Let
ng and any permutation of V . Then, let \Gamma - be the set of Horn terms
ng
g.
Lemma 3.2 ([13]) Let f be a Bf on variables x i , holds if and only if f can be
represented by a DNF
t2S t for some permutation - of V and S
By algebraic transformations of the formula ', it can be rewritten to a linear read-once formula of the
if d is even
d, and the variables x 11
are all different.
Since any linear read-once formula can be transformed to such a formula by changing the polarities of
variables, we obtain the next result. Denote by C rev
the class of all reversed
double Horn functions.
This lemma can also be derived from a related result on finite distributive lattices, see [25].
Theorem 3.3 C R
1-DL . 2
Thus, there exists an interesting relationship between 1-decision lists, read-once formulas, and (disguised)
Horn functions. By means of this relationship, we are able to precisely characterize the prime DNFs of
functions in C R
DH . This is an immediate consequence of the next theorem.
Theorem 3.4 Every f 2 C R
DH (equivalently, f 2 C 1-DL , f 2 CLR-1 ) has a renaming w such that f w is
positive and represented by the unique prime DNF
are pairwise disjoint positive terms and t i for are possibly
empty. In particular, (3.2) implies Conversely, every such ' of (3.2) represents an f 2 C R
(equivalently, an f 2 C 1-DL , f 2 CLR-1 ). 2
Nested differences of concepts. In [20], learning issues for concept classes have been studied which
satisfy certain properties. In particular, learning of concepts expressed as the nested difference c 1 n
has been considered, where the c i are from a concept class which
is closed under intersection. Here, a concept can be viewed as a Bf f , a concept class C as a class of Bfs
CC , and the intersection property amounts to closedness of CC under conjunction, i.e., f
Clearly, the class of Bfs f definable by a single (possible empty) term t enjoys this
property. Let CND denote the class of nested differences where each c i is a single term. Then the following
holds.
Proposition 3.5 C
(We shall prove a more general result at the end of this section in Theorem 3.14, and also give a characterization
of C mon
.) Thus, the general learning results in [20] apply in particular to the class of 1-decision
lists, and thus also to disguised double Horn functions and linear read-once functions.
Threshold and 2-monotonic functions. Let us denote by C TH the class of threshold functions and by
C 2M the class of 2-monotonic functions.
A function f on variables x threshold (or, linearly separable) if there are weights w i ,
threshold w 0 from the reals such that f(x only if
A function is 2-monotonic, if for each assignment A of size at most 2, either f A - f A or f A - f A holds,
where A denotes the opposite assignment to A [29].
The property of 2-monotonicity and related concepts have been studied under various names in the fields of
threshold logic, hypergraph theory and game theory. This property can be seen as an algebraic generalization
of the thresholdness. Note that C R
We have the following unexpected result.
Theorem 3.6 C
Proof. It is well-known that C TH ae C 2M [29], where ae is proper inclusion; moreover, also C 1-DL ' C TH
has been shown [5, 3]. (Notice that in [12], the inclusion C R
independently shown, using
the form (3.2) and proceeding similar as in [3]; the idea is to give all the variables in t j the same weight,
decreasing by index j, and to assign x i a weight so that every term in ' has same weight;
the threshold w 0 is simply the weight of a term t.)
Thus, by the results from above, it remains to show that C 2M " CR-1 ' C R
DH holds.
Recall that a function g on x 1 regular [29], if and only if g(v) - g(w) holds for all v; w 2
by C reg the class of regular functions. The
following facts are known (cf. [29]):
(a) Every regular function is positive and 2-monotonic;
(b) every 2-monotonic function becomes regular after permuting and renaming arguments.
(c) C reg is closed under arbitrary assignments A.
From (a)-(c), it remains to show that C reg " CR-1 ' CLR-1 .
We claim that any function f 2 C reg " CR-1 can be written either as
where f 0 is a regular read-once function not depending on any x i j
induction using
Theorem 3.3 gives then the desired result and completes the proof.
Since f is read-once, it can be decomposed according to one of the following two cases:
Case 1: where the f i depend on disjoint sets of variables B i and no f i can be
decomposed similarly. We show that jB i holds for at most one i, which means that f has form (i). For
this, assume on the contrary that, without loss of generality, jB 1 2. By considering an assignment
A that kills all f 3 that the function regular. Observe that any prime
implicant of g is a prime implicant of f 1 or f 2 , and that each of them has length - 2 (since f is read-once
and by the assumption on the decomposition). Let ' be the smallest index in
assume without loss of generality that ' 2 B 1 . Let t be any prime implicant of f 2 and
is the unit vector with
k. Note that l ! h and l 2 OFF (v) by definition. Then
holds. Indeed, ON(w) 6' P
1. Consequently, the vectors
v and w with
Thus g is not
regular, which is a contradiction. This proves our claim.
Case 2: where the f i depend on disjoint sets of variables B i and no f i can be decomposed
similarly. Then, the dual function f d has the form in case 1. (Recall that a formula representing the dual
of f , f is obtained from any formula representing f by interchanging - and - and 0 and 1,
respectively.) Since the dual of a regular function is also regular [29], it follows that f d has the form (i),
which implies that f has form (ii). 2
Thus, we have established the main result of this section.
Theorem 3.7 C
A generalization of this result is an interesting issue. In particular, whether for k-decision lists and read-k
functions, where k is a constant, similar relationships hold. It appears that this is not the case.
Using a counting argument, one can show that for every k ? 1, C k-DL contains some function which is
not expressible by a read-k formula. In fact, a stronger result can be obtained.
Let for any integer function F (n) denote CR the class of Bfs f(x are
definable by formulas in which each variable occurs at most F (n) - 1 times. For any class of integer
functions F, define CR
F (n)2F CR
pos and C -k
pos the classes of positive Bfs f
such that all prime implicants of f have size k (resp., at most k), where k is a constant.
Lemma 3.8 For every k ? 1, for all but finitely many n ? k there exists an n-ary f 2 C k
pos such that
kk! log n ).
Proof. Since all prime implicants of a positive function are positive, C k
pos contains
functions on n variables. On the other hand, the number of positive functions in CR is bounded by
loss of generality, a formula ' defining some positive function does
not contain negation. Assuming that all variables occur F (n) times, the formula tree has m leaves (atoms)
nodes (connectives). Written in a post-order traversal, it is a string of
of which m denote atoms and the others connectives. There are m!
ways to place the atoms in the
string, if they were all different (this simplification will suffice), times 2 m\Gamma1 combinations of connectives.
If we allow the single use of a binary connective r(x; y), which evaluates to the right argument y, we may
assume w.l.o.g. that ' contains exactly F (n) occurrences of each variable. Thus, (3.4) is an upper bound on
positive read-F (n) functions in n variables. (Clearly, ? and ? are implicitly accounted since multiple trees
for e.g. are counted.)
us compare (3.3) with (3.4). Clearly, (3.4) is bounded by
since m!
. Take the logarithm of (3.3) and (3.5) for base
2, and consider the inequality
Since
amounts to
where p(n) is a polynomial of degree k \Gamma 1. For F
kk! log n , we obtain
kk! log n and thus
kk! log n
k log n
It is easily seen that for large enough n, this inequality holds. This proves the lemma. 2
Let f( n
kk! log n ) be the class of functions F (n) such that F (n) - n
kk! log n holds for infinitely many n.
Theorem 3.9 C -k
pos 6' CR (f( n
kk! log n )), for every k ? 1.
It is easy to see that every function in C -k
pos is in CR (n is the lowest polynomial degree
pos ' CR (n k 0
Corollary 3.10 C mon
kk! log n
kk! log n )), for every k ? 1.
Consequently, any generalization of the parts in Theorem 3.7 involving read-once functions to a characterization
of k-decision lists in terms of read-k functions fails; this remains true even if we allow a polynomial
number of repetitive variable uses, where the degree of the polynomial is smaller than k \Gamma 1.
Let us now consider a possible generalization of the characterization in terms of Horn functions. Since
C k-DL contains all functions with a k-CNF (in particular, also the parity function on k variables), it is hard
to see any interesting relationships between C k-DL and combinations or restrictions of Horn functions.
For nested differences of concepts, however, there is a natural generalization of the result in Theorem 3.7.
Let CND (C) denote the class of all functions definable as nested differences of Bfs in C, and let similarly
denote CDL (C) the class of functions definable by a C-decision list, i.e., a decision list in which each term t i
except the last (t replaced some f 2 C. Then, the following holds.
Theorem 3.11 Let C be any class of Bfs. Then, CDL
contains the complements of the functions in f .
Proof. We show by induction on d - 1 that every f represented by a C-decision list of length - d is in
CND (C   [f?g), and that each nested difference f 1 n (f 2 n are from C   [f?g,
is in CDL (C).
(Basis) For there are two C-decision lists: (?; 0) and (?; 1) respectively. They are represented by the
nested difference ? n ? and ?, respectively. Conversely, (?; 1) represents ?, and for any function f 2 C   ,
the decision list (f ; 0); (?; 1) obviously represents f ; observe that f 2 C holds.
Suppose the statement holds for d, and consider the case d + 1. First, consider a C-decision
loss of generality f 1 6j ?. By the induction hypothesis, the tail
of L can be represented by a nested difference D
defining a Bf f 0 2 CND (C). If b defines the function which can be represented by
the nested difference ? replacing f 0 by D 0 , this is a nested difference of functions in C   [ f?g.
Hence, f 2 CND (C   [f?g) holds. On the other hand, if represents the function
which is equivalent to :(f 1 - f 0 ); since the complement of any function g is represented by the nested
difference ? n g, we obtain from the already discussed scheme for disjunction that f is represented by the
nested difference
replacing f 0 with D 0 , we obtain a nested difference of functions in C   [ f?g, hence f 2 CND (C   [ f?g).
Second, let be any nested difference of functions in C   [ f?g. By the
induction hypothesis, D represents a function f 0 2 CDL (C); thus, D represents
the function
It is easy to see that for any C, CDL (C) is closed under complementation [31] (replace in a decision list
each b i by to obtain a decision list for the complement function). Hence, f 0 is represented by some C-
decision list L 0 . Now, if f otherwise, the decision list
f . Hence, f 2 CDL (C).
Consequently, the induction statement holds for d + 1. This concludes the proof of the result. 2
Proposition 3.5 is an immediate corollary of this result. Moreover, we get the following result. Let C k-cl
denote the class of functions definable by a single clause with at most k literals, plus ?.
Corollary 3.12 C
Thus, CND (C k-cl ) characterizes C k-DL . However, C k-cl is not closed under conjunction, and thus, strictly
speaking, not an instance of the schema in [20]. A characterization by such an instance is nonetheless
possible. Call a subclass C 0 ' C a disjunctive base of a class C, if every f 2 C can be expressed as a
disjunction of functions f i in C 0 .
Lemma 3.13 If C 0 is a disjunctive base for C, then CDL (C 0
Proof. Suppose an item (f; b) occurs in a C-decision list L. By hypothesis, each
Replace the item by k items (f Then, the resulting decision list is equivalent to L.
Hence each C-decision list can be converted into an equivalent C 0 -decision list. 2
Theorem 3.14 C
Proof. By Corollary 3.12 and Lemma 3.13. 2
Thus, nested differences of k-CNF functions are equivalent to k-decision lists. Observe that from the proof
of this result, linear time mappings between nested differences and equivalent k-decision do exist. A similar
equivalence C does not hold. The reason is that the class of single-term functions is
not a base for C k-CNF , which makes it impossible to rewrite a C k-CNF -decision list to a k-decision list in
general.
The classes of bounded monotone decision lists can be characterized in a similar way. Let C pos
k-DNF and
C neg
k-CNF be the subclasses of C k-DNF and C k-CNF whose members have a positive DNF and a negative CNF
(i.e., no positive literal occurs), respectively.
Theorem 3.15 C mon
k-CNF
Thus, in particular, if C Lit \Gamma denotes the class of negative literals plus ?, then we obtain the following.
Corollary 3.16 C rev
4 Recognition from a Formula
A 1-decision list, and thus also its relatives, can be recognized in polynomial time from formulas of certain
classes, which include Horn formulas. The basis for our recognition algorithm is the following lemma:
Lemma 4.1 A Bf f is in C 1-DL if and only if either (ia) x
holds for some j, and (ii) f holds for all j satisfying (ia) or (ib)
(resp., (ic) or (id)). 2
Given a formula ', the recognition algorithm proceeds as follows. It picks an index j such that one of
(ia)-(id) holds, and then recursively proceeds with ' as in (ii). The details can be found in [12]. The
following result on its time complexity is immediate from the fact that the recursion depth is bounded by
n and that at each level O(n) test (ia)-(id) are made. Let for a formula ' denoted j'j its length, i.e., the
number of symbols in '.
Theorem 4.2 Let F be a class of formulas closed under assignments, such that checking equivalence of '
to ? and ?, respectively, can be done in O(t(n; j'j)) time for any ' 2 F . 2 Then, deciding whether a given
represents an f 2 C 1-DL can be done in O(n 2 t(n; j'j)) time. 2
Hence, the algorithm is polynomial for many classes of formulas, including Horn formulas and quadratic
(2-CNF) formulas. Since testing whether and a quadratic formula is
possible in O(j'j) time (cf. [10, 14]), we obtain the following.
Corollary 4.3 Deciding whether a given Horn DNF or 2-CNF ' represents an f 2 C 1-DL can be done in
Theorem 4.2 has yet another interesting corollary.
Corollary 4.4 Deciding if an arbitrary positive (i.e., negation-free) formula ' represents an f 2 CLR-1 can
be done in polynomial time. 2
In fact, deciding whether a positive formula ' represents a read-once function is co-NP-complete [21, 11].
It turns out that the class of CLR-1 is a maximal subclass of CR-1 w.r.t. an inductive (i.e., context-free)
bound on disjunctions and conjunctions in a read-once formula such that deciding f 2 CR-1 from a positive
formula ' is polynomial. Indeed, it follows from results in [11, 21] that if in part (2) of Definition 3.1 either
disjunction with a term x 1 x 2 or conjunction with a clause x 1 - x 2 is allowed, then the recognition problem
is co-NP-hard.
In general, the recognition problem is unsurprisingly intractable.
Theorem 4.5 Deciding whether a given formula ' represents a function f 2 C 1-DL is co-NP-complete.
Proof. The recognition problem for CR-1 is in co-NP [2], and it is easy to see that it also in co-NP for C 2M .
Since co-NP is closed under conjunction, membership in co-NP follows from 3.7. The hardness part is
easy: any class C having the projection property, i.e., C is closed under assignments, contains each
arity, and does not contain all Bfs, is co-NP-hard [19]; obviously, C 1-DL enjoys this property. 2
As for k-decision lists, it turns out that the recognition problem is not harder than for 1-decision lists. In
fact, membership in co-NP follows from the result that k-decision lists are exact learnable with equivalence
queries in polynomial time (proved by Nick Littlestone, unpublished; this also derivable from results in
[20] and Theorem 3.14), and the result [2] that for classes which are exact learnable in polynomial time
with equivalence and membership queries (under minor constraints), the recognition problem is in co-NP.
Hardness holds by the same argument as in the proof of Theorem 4.5.
We conclude this section with a some remarks concerning the equivalence and the implication problem.
The problems are, given k-decision lists L 1 and L 2 representing functions f 1 and f 2 , respectively, decide
As usual, t(n; j'j) is monotonic in both arguments.
respectively. Both problems are obviously
in co-NP, and they are complete for any fixed k - 3, since they subsume deciding whether a k-DNF formula
is a tautology. On the other hand, for both problems are polynomial, and in fact solvable in linear
time. For the remaining case can be seen that the problem is also polynomial; the underlying
reason is that the satisfiability problem for 2-CNF formulas is polynomial.
5 Extension problems
The extension problem for C 1-DL has already been studied to prove the PAC-learnability of this class. It is
known [31] that it is solvable in polynomial time. We point out that the result in [31] can be further improved,
ibby showing that the extension problem for C 1-DL can be solved in linear time. This can be regarded as a
positive result, since the extension problem for the renaming closures of classes that contain C 1-DL is mostly
intractable, e.g., for C R
Horn
, C R
pos , C R
or no linear time algorithms are known.
We describe here an algorithm EXTENSION for the equivalent class CLR-1 , which uses Lemma 4.1 for
a recursive extension test; it is similar to the more general algorithm described in [31], and also a relative
of the algorithm "total recall" in [20]. Informally, it examines the vectors of T and F , respectively, to see
whether a decomposition of form L-' or L-' is possible, where L is a literal on a variable x
it discards the vectors from T and F which are covered or excluded by this decomposition, and recursively
looks for an extension at the projection of (T ; F ) to the remaining variables. Cascaded decompositions
are handled simultaneously.
Algorithm EXTENSION
Input: a pdBf (T ; F and a set I ' ng of indices.
has an extension f 2 CLR-1 , where T [I ] and
are the projections of T and F to I , respectively; otherwise, "No".
Step 1. if T [I no true vectors *)
no false vectors *)
Step 2. I
then go to Step 3 (* no extension x possible *)
else begin (* go into recursion *)
if
elseif
else (* /
Step 3. J
else begin (* go into recursion *)
if
elseif
else (* /
To find an extension of a given pdBf (T ; F ), the algorithm is called with I ng. Observe that it
could equally well consider going into the recursive calls. In particular, if
an index i is in the intersection of these sets, then both decompositions x are equally good.
Note that the execution of steps 2 and 3 alternates in the recursion. Moreover, the algorithm remains correct
if only a subset S ' I may lead to a different extension.
Proposition 5.1 Given a pdBf (T ; F ), where correctly finds an
It is possible to speed up the above algorithm by using proper data structures so that it runs in time
linear time; the technical details can be found in [12]. In particular, the data
structures assure that the same bit of the input is looked up only few times. Roughly, counters #T ij ,
record how many vectors in T have value j at component i, such that #T ij is in
a bucket BT[#T ij ]. Moreover, a list LT ij of all the vectors v in T so that v has at component i value j is
maintained, and at each component i of v a link to the entry of v in the respective list LT ij exists. For F ,
analogous data structures are used.
Theorem 5.2 The extension problem for C 1-DL (equivalently, for CLR-1 , and CND ) is solvable in time
in linear time. 2
Thus, in the learning context we obtain the following result.
Corollary 5.3 Learning a Bf f 2 C 1-DL from an arbitrary (possibly spoiled) teaching sequence for f is
possible in linear time in the size of the input.
It turns out that our algorithm can be used as a substitute for the learner in the teacher/learner model for
C 1-DL described in [16]. That algorithm is based on the idea to build a decision list by moving an item
('; b), where ' is a literal and b an output value, from the beginning of a decision list towards the end if it is
recognized that some example is misclassified by this item. Initially, all possible items are at the beginning,
and the procedure loops until no misclassification occurs (see [16] for details); it takes O(m 2 n) many steps
if the input has size O(mn), where m is the length of the shortest decision list for the target.
The method in [16] is somewhat dual to ours, and it is easily seen that the items which remain at the
beginning of the list are those whose literals are selectable for decomposition in our algorithm. Thus, by the
greedy nature of our algorithm, it constructs from the (possibly spoiled) teaching set as in [16] exactly the
target function. This shows that C 1-DL is an efficiently teachable class; since the teaching set is constructible
from the target in linear time, we have that C 1-DL is a nontrivial class of optimal order, i.e., linear time for
both teaching and learning.
5.1 Generating all extensions
For computing all extensions of a pdBf in C 1-DL , we describe an algorithm which outputs linear read-once
formulas for these extensions, employing the decomposition property of Lemma 4.1 for CLR-1 . Roughly,
the algorithm outputs recursively all extensions with common prefix fl in their linear read-once formulas. It
is a backtracking procedure similar to EXTENSION, but far more complicated.
The reason is that multiple output of the same extension must be avoided. Indeed, syntactically different
renamed forms 3.1 may represent the same linear-read once function. This corresponds to the fact that different
1-decision lists may represent the same function. E.g., both
the function In order to avoid such ambiguity, we have to single out some normal form; we adopt
for this purpose that the innermost level of the renamed form (3.1) for a linear read-once function contains
at least two literals, if the formula involves more than one level.
Our algorithm, ALL-EXTENSIONS, uses an auxiliary procedure that checks whether a given pdBf (T [I];
F [I]) has an extension in CLR-1 subject to the constraint that in a decomposition starting with a conjunction
only literals from a given set Lit - (resp., Lit - ) can be used until
a disjunction step (resp., conjunction step) is made. This constraint is used to take commutativity of the
connectives - and - into account. We make the concept of constrained extensions more precise.
For convenience, define for a set of vectors S that
v2S ON(v) and similarly that OFF
v2S OFF (v). Moreover, a literal L is -selectable (resp., -selectable) for S if either
ON(S)). The set of all
-selectable (resp., -selectable) literals for S is denoted by Sel-Lit - (S) (resp., by Sel-Lit - (S)).
Lit -constraint: An extension f 2 CLR-1 of a pdBf (T [I]; F [I]), I ' ng, is a Lit -constrained
extension, where Lit - is a set of -selectable literals for T [I], if the linear read-once formula of f
has form L 1 and ff is a disjunction
Lit -constraint: An extension f 2 CLR-1 of a pdBf (T [I]; F [I]), I ' ng, is a Lit -constrained
extension, where Lit - is a set of -selectable literals for F [I], if the linear read-once formula of f
has form L 1 and ff is a
conjunction
We use two symmetric algorithms, REST-EXT- and REST-EXT-, which handle the cases where we
look for a nontrivial (i.e., different from ? and ?) Lit -constrained (resp., Lit -constrained) extension.
The algorithm for the conjunction case is as follows.
Algorithm REST-EXT-
ng, a set Lit - of -selectable literals for T [I ].
Output: "Yes", if (T [I ]; F [I]) has a Lit -constraint extension f 2 CLR-1 and f 6= ?; ?; otherwise, "No".
Step 1. if
else output "No" (exit);
Step 2. I \Sigma := fi j x
(* try a maximal -decomposition; use first all literals not occurring opposite *)
I \Sigma
output "Yes" (exit) (* extension L 1 exists *)
output "No" (exit) ;
(* (T [I ]; F [I]) has an extension in CLR-1 , F has at least 2 jI \Sigma j vectors *)
cand := empty list; (* list of -decomp. candidates
for each subset J ' I \Sigma do begin
Lit J
insert Lit J
is -decomp.
for each L 2 Lit J
do insert Lit J
while cand is not empty do begin
remove a set A from cand;
I A := I n fV (L) j L 2 Ag;
-decompose by A *)
if some literal is -selectable for FA [I A ] then
(* test for extension
if jF A [I A ]j 6= 2 jI A j\Gamma1 then output "Yes" (exit)
else for each L 2 A do insert A n fLg into cand;
output "No" (exit). 2
The algorithm for the case of Lit -constraint extensions, REST-EXT-, is completely symmetric. There,
the roles of T and F , as well as of "-" and "-", are interchanged. Since the formulation of the algorithm is
straightforward, we omit it here.
Lemma 5.4 REST-EXT- correctly answers whether a given pdBf (T [I]; F [I]) has a Lit -constrained
extension in CLR-1 , and runs in time O(n(jT
Proof. We first prove correctness. It is easy to see that Step 1 is correct: If L 2 Lit -
L is an extension. If jT [I]j 6= 2 jIj , then some vector v 2 f0; 1g n [I] n T [I] exists; in this case,
is an extension, which is a Lit -constrained extension if jIj - 2. Thus the
algorithm correctly outputs "Yes" in Step 1. Suppose it outputs "No" in Step 1. Then Lit
which means that only one variable is eligible, or jT which means that is the
only possible extension. Thus, the algorithm correctly outputs "No".
Now consider Step 2. Observed that this step is only reached if F 6= ; holds. Suppose then the algorithm
outputs "Yes". If it does so in the first "if" statement, then Lit -
be the literals L
I \Sigma . If I holds since otherwise F 0 [I \Sigma
f;g, and hence jF 0 [I \Sigma which is a contradiction. Thus L 1 is an extension
of (T [I]; F [I]) which is clearly Lit -constrained; therefore, the output is correct. If I \Sigma 6= ;, then let
and consider the
' is a Lit -constrained extension of (T [I]; F [I]); hence, also in this case the output is correct. Otherwise,
"Yes" is output in the "while" loop. Then, some literal L   is -selectable for FA [I A ] and jF A [I A ]j 6= 2 jI A j\Gamma1 .
We claim that FA 6= ; holds. Let us assume the contrary. If which is
a contradiction. Otherwise, Lit - 6= ;, and
L2A L represents an extension in CLR-1 . It is easy to see that
A ' Lit J
L2Lit J
L is an extension in CLR-1 as well. Thus F 0 in the first
"if" statement of Step 2 satisfies jF 0 [I \Sigma ]j 6= 2 jI \Sigma j because otherwise
a contradiction. Therefore, in case of FA = ;, the "while" loop would not have been entered since the
algorithm halts in the first "if" statement of Step 2.
Now, we can say that (T [I A ]; FA [I A ]) has an extension in CLR-1 represented by a linear read-once formula
since FA 6= ; and (T [I]; F [I]) has an extension in CLR-1 (oth-
erwise, the "while" loop would not have been entered). Indeed, for I I A n fV (L   )g, we have (i)
consequently, some extension fi
of
must be different from ?; ?. Thus, it follows
that (T [I]; F [I]) has an extension
L2A L (L   - fi). Since ' is clearly Lit -constrained, the output is
correct.
On the other hand, suppose the algorithm outputs "No". Towards a contradiction, assume that (T [I];
F [I]) has a Lit -constrained extension ' in CLR-1 . Assume first that . This means
are the literals L j in ' such that V (L
I \Sigma , and that
are all other such literals in Lit - with that property. Since ' is an extension, the set
empty. Hence, also the set S
is an extension of (;; F 0 [I \Sigma ]),
which implies jF 0 [I \Sigma ]j 6= 2 jI \Sigma j . Since, as already observed, Lit - 6= ;, the algorithm outputs "Yes" in the
first "if". This is a contradiction.
Thus, ' must be of form fi). It is easy to see that L is -selectable for FA [I A ]
where either (a)
The algorithm inserts A to cand before the "while" loop. If A 6= fL then the algorithm must
find in the "while" loop jF A [I A it does not output "Yes"), and hence it inserts (among
possible others) a subset A 1 n fL   g ' fL into cand such that L is -selectable for FA 1 [I A 1 ],
and so on. Eventually, the algorithm must encounter A
and jF A k [I A k ]j 6= 2 jI A k
therefore, the algorithm outputs "Yes", which is a contradiction. This proves the
correctness of the algorithm.
Concerning the bound on the execution time, it is clear that Step 1 can be done in O(jT j) time. In Step 2,
I \Sigma is computable in O(n) time, and F 0 in O(njF time. The test jF 0 [I \Sigma ]j 6= 2 jI \Sigma j can be done in O(njF
time, by computing the set F 0 [I \Sigma ] in O(njF determining its size. The call of EXTENSION can
be evaluated in O(n(jT (Theorem 5.2). Thus, the first phase of Step 2 takes O(n(jT
time.
The remaining second phase uses the list cand, which can be easily organized such that lookup, insertion,
and removal of a set A takes O(n) time. Multiple consideration of the same set A can be avoided by
accumulating all sets A which had been inserted into cand so far in a list, for which lookup and insertion
can be done in O(n) time.
Consider the body of the outer "for" loop in the second phase. The statements before the "while" loop
take O(n 2 ) time; in order to assess the time for the "while" loop, we note the following fact.
Fact 5.1 For a fixed J ' I \Sigma , the algorithm encounters during execution of the "while" loop at most njF j
different sets A such that some literal L is -selectable for FA [I A ] and jF A [I A
To show this, let I
an evidence for A, if w 2 T (L   ) for
every L   2 A and w 2 F (L   ) for every L   2 Lit J
must have an evidence w.
The same w can serve as an evidence for at most n of the encountered A's. Indeed, suppose different such
sets
- with (unique) -selectable literals
resp. FA 2
have the same evidence w.
This implies that either L 1 2 Lit J - or L 2 2 Lit J - . In fact, both must hold. To verify this,
suppose by contradiction that w.l.o.g. L
- . This implies A g. Now (T [I]; F [I]) has the
extensions
consequently, it also
has an extension L 1;1
which is a contradiction and proves
- . It follows that A 1 [ fL 1
Obviously, at most n \Gamma 1 sets A 2 different from A 1 are possible; if T 6= ;, then both
Lit J
are impossible, and hence no A 2 different from A 1 exists. It follows that the number of encountered
sets A as in Fact 5.1 is bounded by njF j (resp., jF j).
In the body of the "while" loop, I A can be computed in O(n) time, and FA resp. FA [I A ] in O(njF
maintaining counters, the subsequent tests whether some literal is -selectable for FA [I A ] and jF A [I A ]j 6=
are straightforward in O(n) resp. constant time. The inner "for" loop can be done in O(n 2 ) time.
Thus, the body of the "while" loop takes O(n(jF A is as in Fact 5.1, and O(njF
otherwise.
Consequently, for a fixed J ' I \Sigma , in total O(njF jn(jF j +n)) time is spent in the while-loop for A's as in
Fact 5.1, and O(n 2 jF jnjF time for all other A's, since Fact 5.1 implies that there are at most n+n 2
of the latter inserted to cand. Thus, for fixed J ' I \Sigma , the "while" loop takes O(n 3 jF
time. Altogether, the body of the outer "for" loop takes O(n 3 jF
Since the "for" loop is executed at most 2 jI \Sigma j - jF j times, it follows that the second phase of Step 2 takes
takes in total O(n(jT
conclude similarly, exploiting Fact 5.1 and I that the second phase of Step 2 takes O(n 2 jF
and that Steps 1 and 2 together take O(n(jT This proves the lemma. 2
We remark that selecting a set A of maximum size for removal from cand in the while-loop of REST-
EXT- is a plausible heuristics for keeping the running time short in general. Organization of cand such
that maintenance and selection of A stay within O(n) time is straightforward.
Similarly, we obtain a symmetric result for the case of disjunction.
Lemma 5.5 REST-EXT- correctly answers whether a given pdBf (T [I]; F [I]) has a Lit -constrained
extension in CLR-1 , and runs in time O(n(n 2 jT
The main algorithm, ALL-EXTENSIONS, is described below. In the algorithm, we store prefixes of a
linear read-once formula ' in a string, in which parentheses are omitted (they are redundant and can be
reinserted unambiguously); for technical convenience, we add "x 0 -" in front of this prefix. For example,
consider the )). The string representations of the proper prefixes fl
of ' are
represented by
Algorithm ALL-EXTENSIONS
Input: A pdBf
extensions of (T ; F ) in CLR-1 .
Step 1. if special treatment of extension ? *)
special treatment of extension ? *)
Step 2. fl := "x 0 -"; I :=
Procedure ALL-AUX
Input: A pdBf (T ; F ), prefix fl of a linear read-once formula, set I of available variable indices and sets of literals
allowed for decomposition.
Output: Formulas FLR-1 for all extensions f 2 CLR-1 of (T ; F ) having fl as prefix, and the literal plus operator after
is according to Lit - ; Lit - .
Step 1. (* Expand fl by a conjunction step *)
while there is a literal L 2 Lit - do begin
I 0 := I n V (L); (* variable of L, V (L), is no longer available *)
literal L for further decomposition *)
complementary literal of L *)
output the extension "/ - L";
then begin (* expand fl by "L-" *)
endftheng
endfwhileg.
Step 2. (* Expand fl by a disjunction step *)
while there is a literal L 2 Lit - do begin
I 0 := I n V (L); (* variable of L, V (L), is no longer available *)
literal L for further decomposition *)
complementary literal of L *)
output the extension " - L";
then begin (* expand fl by "L-" *)
endftheng
endfwhileg. 2
An example is provided in the appendix.
Theorem 5.6 Algorithm ALL-EXTENSIONS correctly outputs formulas
extensions polynomial delay, where / i 6j / j for
Proof. Correctness of the algorithm can be shown by induction on jIj.
The delay between consecutive outputs is O(n 5 (jT
correctly answers in O(n(jT j and the other steps in the bodies
of the loops in Steps 1 and 2 of ALL-AUX take O(njF j) and O(njT j), respectively. There are at most O(n 2 )
subsequent calls of ALL-AUX which do not yield output, because the recursion depth is bounded by n and
recursive calls of ALL-AUX are only made if they lead to output, which is checked using REST-EXT-
and/or REST-EXT-. Hence, the delay is bounded by O(n 5 (jT the first and the last output
happen within this time bound, the result follows. 2
Observe that in [13], a similar algorithm for computing extensions in CDH has been described. However,
the problem there is simpler, since (3.1) is a unique form for each function in CDH , and, moreover, the
set Lit - of -selectable literals (resp., set Lit - of -selectable literals) may not contain both a literal x i
and its opposite x i if these conditions do not hold, solving the problem in
polynomial time is much more difficult and needs further insights. The present algorithm is thus a nontrivial
generalization of the one in [13].
Improvements to ALL-EXTENSIONS can be made by using appropriate data structures and reuse of
intermediate results. However, it remains to see whether a substantially better algorithm, in particular, a
linear time delay algorithm, is feasible.
Theorem 5.6 has important corollaries.
Corollary 5.7 There is a polynomial delay algorithm for enumerating the (unique) prime DNFs for all
extensions of a pdBf (T ; F ) in CLR-1 (resp., in C 1-DL , CND , and C R
Proof. By Theorem 3.4, the prime DNF for a linear read-once formula ' can be obtained from ' in O(n 2 )
time. 2
Denote by C(n) the class of all Bf of n variables in C. Then, if we apply the algorithm on (T ; F ), where
all members of CLR-1 (n). Hence,
Corollary 5.8 There is a polynomial delay algorithm for enumerating the (unique) prime DNFs of all
in C 1-DL (n), CND (n), and C R
Transferred to the learning context, we obtain:
Corollary 5.9 Algorithm ALL-EXTENSIONS outputs all hypotheses f 2 CLR-1 which are consistent with
a given sample S with polynomial delay. Similar algorithms exist for C 1-DL , CND , and C R
DH .
As a consequence, if the sample almost identifies the target function, i.e., there are only few (up to polynomially
many) different hypotheses consistent with the sample S, then they can all be output in polynomial
time in the size of S.
As another corollary to Theorem 5.6, checking whether a pdBf (T ; F ) uniquely identifies one linear-read
once function is tractable.
Corollary 5.10 Given a pdBf (T ; F ), deciding whether it has a unique extension f 2 CLR-1 (equivalently,
DH ) is possible in polynomial time.
For learning, this gives us the following result.
Corollary 5.11 Deciding whether a given sample S is a teaching sequence for CLR-1 (equivalently, for
C 1-DL and CND ) is possible in polynomial time.
Example 5.1 Consider the pdBf (T ; F ), where (001)g. The algorithm
ALL-EXTENSIONS outputs the single extension which corresponds to the 1-decision list
In fact, / is the unique linear-read once extension of (T ; F ). Observe that
only extensions f 2 CLR-1 of form x 3 - ' are possible, as x 3 is the only - resp. -selectable literal; since
no term x 3 x j can be an implicant of an extension and T contains two vectors, it follows that x 3
the only extension of (T ; F ) in CLR-1 . 2
6 Conclusion
In this paper, we have considered the relation between decision lists and other classes of Boolean functions.
We found that there are a number of interesting and unexpected relations between 1-decision lists, Horn
functions, and intersections of classes with read once-functions. These results provide us with syntactical
and semantical characterizations of an operationally defined class of Boolean functions, and vice versa with
an operational and syntactical characterization of intersections of well-known classes of Boolean functions.
Moreover, they allow us to transfer results obtained for one of these particular classes, the corresponding
others. In this way, the characterizations may be useful for deriving future results.
On the computational side, we have shown that some problems for 1-decision lists and their relatives
are solvable in polynomial time; in particular, finding an extension of a partially defined Boolean function
(in terms of learning, a hypothesis consistent with a sample) in this class is feasible in linear time, and
enumeration of all extensions of a pdBf in this class (in terms of learning, all hypotheses consistent with
sample) is possible with polynomial delay. Furthermore, the unique extension problem, i.e., recognition of
a teaching sequence, is polynomial.
Several issues remain for further research. As we have shown, a simple generalization of the characterizations
of 1-decision lists in terms of other classes of Boolean functions is not possible except in a single
case. It would be thus interesting to see under which conditions such a generalization could be possible.
Observe that the inclusion C k-DL ' C TH (k) is known [3], where C TH (k) denotes the functions definable as
a linearly separable function where terms of size at most k replace variables. A precise, elegant description
of the C k-DL fragment within C TH (k) would be appreciated; as we have shown, intersection with read-k
functions is not apt for this. Moreover, further classes of Boolean functions and fragments of well-known
such classes which characterize k-decision lists would be interesting to know.
Other issues concern computational problems. One is a possible extension of the polynomial-time delay
enumeration result for 1-decision list extensions do k-decision lists for k ? 1. While finding a single
extension is possible in polynomial time [31], avoiding multiple output of the same extension is rather
difficult, and a straightforward generalization of our algorithm is not at hand. Intuitively, for terms of size
role and makes checking whether items of a decision list are redundant intractable
in general. We may thus expect that in general, no such generalization of our algorithm for k ? 1 is possible.

Acknowledgments

. The authors thank Martin Anthony for pointing out the equivalence of CLR-1 and
C 1-DL . Moreover, we greatly appreciate the comments given by the anonymous STACS '98 reviewers on the
previous version of this paper. Moreover, we thank Leonid Libkin for pointing out an alternative derivation
of Lemma 3.2 and sending papers, and we thank Nick Littlestone for clarifying the source of the exact
learnability result for C k-DL .



--R

Complexity Theoretic Hardness Results for Query Learn- ing

Threshold Functions
Computational Learning Theory.
On specifying Boolean functions by labelled examples.


PAC Learning with Irrelevant Attributes.
Partial Occam's Razor and Its Applications.

Generating Boolean

Double Horn Functions.
On the Complexity of Timetable and Multicommodity Flow Problems.
On the Complexity of Teaching.
Teaching a Smarter Learner.
Criteria for Repetition-Freeness of Functions in the Algebra of Logic
Lower Bounds on Learning Decision Lists and Trees.
On the Geometric Separability of Boolean Functions.
Learning Nested Differences of Intersection-Closed Concept Classes
The Complexity of Very Simple Boolean Formulas With Applications.
A computational model of teaching.
Combinatorial Characterization of Read-Once Formulae
On Repetition-Free Contact Schemes and Repetition-Free Superpositions of the Functions in the Algebra of Logic
Separatory Sublattices and Subsemilattices.
Learning When Irrelevant Attributes Abound: A New Linear Threshold Algorithm.
Horn Extensions of a Partially Defined Boolean Function.
Functions Computed by Monotone Boolean Formulas With No Repeated Variables.
Threshold Logic and its Applications.
Induction of Decision Trees.
Learning Decision Lists.
Learning with a Helpful Teacher.
Teachability in Computational Learning.
On the Theory of Repetition-Free Contact Schemes
A Theory of the Learnable.
--TR
A theory of the learnable
On generating all maximal independent sets
Functions comuted by monotone boolean formulas with no repeated variables
The complexity of very simple Boolean formulas with applications
Cause-effect relationships and partially defined Boolean functions
Learning Nested Differences of Intersection-Closed Concept Classes
Teachability in computational learning
Computational learning theory
A computational model of teaching
Combinatorial characterization of read-once formulae
Exact transversal hypergraphs and application to Boolean MYAMPERSANDmgr;-functions
On the complexity of teaching
On specifying Boolean functions by labelled examples
Lower bounds on learning decision lists and trees
Teaching a smarter learner
and best-fit extensions of partially defined Boolean functions
Double Horn functions
Complexity theoretic hardness results for query learning
Horn Extensions of a Partially Defined Boolean Function
Learning Decision Lists
Induction of Decision Trees
Learning Quickly When Irrelevant Attributes Abound
Partial Occam''s Razor and Its Applications
polynomial delay enumeration;extension problem;boolean functions;decision lists;teaching sequence