% This is file /u/rivest/papers/ai.bib, containing Rivest's bibliography
% on MACHINE LEARNING.  Feel free to use or modify this file, following
% the style of entries already present. (But be complete and accurate!)
% See Appendix B of the LATEX manual for info on formats and required fields.
%
% The key for an entry should be the concatenation of: 
%	(1) The full last name of the first author (first letter capitalized),
%	(2) The first two characters of the last name of each following
%           author (first letter capitalized),
%	(3) The last two digits of the year of the publication, and
%	(4) [Optional] A letter from "bcdefg..." or other text (e.g. volume
%	    number) if necessary to yield unique keys.
%
% Example: AhoHoUl74 
%
% The entries in this file should be alphabetically sorted by key value.
%
% PLEASE CHECK YOUR ENTRIES FOR SYNTACTIC CORRECTNESS, SPELLING, ETC.
% ONE WAY TO TEST YOUR ENTRIES IS TO RUN bigbibtex ON /u/rivest/papers/bibtest
% THIS CHECKS ALLTHE ENTRIES IN THIS FILE FOR COMPLETENESS, ETC...
% 	swan> bigbibtex /u/rivest/papers/bibtest
% IF IT DOESN'T COMPLAIN, THEN YOU ARE OK.

@string{CACM = {Communications of the ACM}}
@string{InfCtrl = {Information and Control}}

@inproceedings{Abe89,
author = 	{Naoki Abe},
title = 	{Polynomial Learnability of Semilinear Sets (Extended
		 Abstract)},
booktitle = 	{Second Workshop on Computational Learning Theory},
address = 	{Santa Cruz, Cal.\ },
year = 		{1989}
}


@inproceedings{AbeWa90,
author = 	{Abe, N. and M. Warmuth},
title = 	{On the computational complexity of approximating
		distributions by probabilistic automata},
booktitle = 	{Third Workshop on Computational Learning Theory},
year = 		1990,
pages = 	{52--66},
publisher = 	{Morgan Kaufmann},
comment = 	{Hidden Markov Model}
}

@article{AbeWa92,
author = 	{Abe, Naoki and Osamu Watanabe},
title = 	{Polynomially Sparse Variations and Reducibility among
		prediction problems},
journal = 	{IEICE Trans. Inf. \& Syst.},
year = 		1992,
month = 	Jul,
volume = 	{E75-D},
number = 	4,
pages = 	{449--458},
comment = 	{Gives an example to distinguish Turing-reducibility and
		prediction-preserving reducibility}
}

@mastersthesis{Adams90,
author = 	{Robert T. Adams},
title = 	{Inference of {LISP} Programs from Examples},
type = 		{Bachelor's thesis},
school = 	{MIT EECS Department},
year = 		1990,
month = 	Jun
}


@techreport{Ahmad88,
author=   	{Ahmad, Subutai},
title=    	{A Study of Scaling and Generalization in Neural Networks},
institution= 	{University of Illinois at Urbana-Champaign},
year=     	1988,
month=    	Sep,
number=   	{UIUCDCS-R-88-1454},
comment=	{UILU-ENG-88-1759.}
}


@article{AhnCoCoFr88,
author = 	{Ahn, S. and A. Cooper and G. Cornuejols and A. Frieze},
title = 	{Probabilistic Analysis of a Relaxation for the $K$-Median 
		Problem},
journal = 	{Mathematics of Operations Research},
year = 		1988,
month = 	Feb,
volume = 	13,
pages = 	{1--31}
}


@inproceedings{AielloMi91,
author=   	{Aiello, William and Milena Mihail},
title=    	{Learning the fourier spectrum of probabilistic lists and trees},
booktitle=	{Proceedings SODA 91},
publisher = 	{AAAI Press/The MIT Press},
address=	{Boston, MA},
year=     	{1991},
month = 	Jan,
pages = 	{291--299}
}



@inproceedings{AleliunasKaLiLoRa79,
author=   	{Aleliunas, Romas and Richard M. Karp and Richard J. Lipton and
          	Laszlo Lov\'asz and Charles Rackoff},
title=    	{Random Walks, Universal Traversal Sequences, and the 
		Complexity of Maze Problems},
booktitle= 	{20th Annual Symposium on Foundation of Computer Science},
address=  	{San Juan, Puerto Rico},
year=     	1979,
month=    	Oct,
pages=    	{218--223}
}


@techreport{AmaldiKa93,
author=   	{Edoardo Amaldi and Viggo Kann},
title=    	{The Complexity and Approximability of Finding
		Maximum Feasible Subsystems of Linear Relations},
institution= 	{Ecole Polytechnique Federale de Lausanne},
year=     	1993,
month=    	Aug,
number=   	{ORWP 93/11}
}


@article{AmariFuSh92, 
author = 	{Shun-ichi Amari and Naotake Fujita and Shigeru Shinomoto},
title =		{Four Types of Learning Curves},
journal =	{Neural Computation},
volume =	4,
number =	4,
year = 		1992,
pages = 	{605--618}
}


@mastersthesis{Amsterdam88,
author=   	{Amsterdam, Jonathan},
title=    	{The Valiant Learning Model:  Extensions and Assessment},
school=   	{MIT Department of Electrical Engineering and Computer 
		Science},
year=     	1988,
month=    	Jan
}

@inproceedings{Amsterdam88b,
author = 	{Amsterdam, Jonathan},
title = 	{Some Philosophical Problems with Formal Learning Theory},
booktitle = 	{Proceedings AAAI-88},
year = 		{1988},
pages = 	{580--584},
organization = 	{American Association for Artificial Intelligence},
address = 	{Saint Paul, Minn.},
month = 	{aug},
comment = 	{A philosophical attack on computational learning theory}
}

@book{AndersonRo88,
editor=   	{Anderson, James A. and Rosenfeld, Edward},
title=    	{Neurocomputing: Foundations of Research},
publisher=	{MIT Press},
year=     	1988
}


@techreport{Andreae85,
author=   	{Andreae, Peter Merrett},
title=    	{Justified Generalization: Acquiring Procedures from Examples},
institution= 	{MIT Artificial Intelligence Laboratory},
year=     	1985,
month=    	Jan,
number=   	{AI-TR-834},
comment=  	{Ph.D. thesis.  Examines traces of a correct procedure 
		(physical motion procedure) to infer loops, etc.}
}

@article{Angluin78,
author=   	{Angluin, Dana},
title=    	{On the complexity of minimum inference of regular sets},
journal=  	{Information and Control},
volume=   	39,
year=     	1978,
pages=    	{337--350}
}

@article{Angluin80,
author=   	{Angluin, Dana},
title=    	{Inductive Inference of Formal Languages from Positive Data},
journal=  	InfCtrl,
year=     	1980,
month=    	May,
volume=   	45,
number=   	2,
pages=    	{117--135},
comment=  	{Can be done iff each language Li contains a finite subset Ti 
		such that Ti is a subset of Li and if i!=j and Ti is a subset 
		of Lj, then Lj is not a proper subset of Li; and Ti is 
		computable from i.}
}

@article{Angluin80b,
author=   	{Angluin, Dana},
title=    	{Finding patterns common to a set of strings},
journal=  	jcss,
number=		1,
volume=  	21,
month=		aug,
year=     	1980,
pages=    	{46--62}
}

@article{Angluin81,
author=   	{Angluin, Dana},
title=    	{A note on the number of queries needed to identify regular 
		languages},
journal=  	{Information and Control},
volume=   	51,
year=     	1981,
pages=    	{76--87}
}

@article{Angluin82,
author=   	{Angluin, Dana},
title=    	{Inference of Reversible Languages},
journal=  	{Journal of the ACM},
year=     	1982,
volume=  	29,
number=   	3,
month=    	Jul,
pages=    	{741--765}
}

@techreport{Angluin86a,
author=   	{Angluin, Dana},
title=    	{Learning Regular Sets from queries and counter-examples},
institution= 	{Yale University Department of Computer Science},
number=   	{YALEU/DCS/TR-464},
year=     	1986,
month=    	Mar,
comment=  	{Learning regular sets from a teacher who answers membership 
		queries, and responds to false conjectures with 
		counterexamples.  Based on Gold's approach.  Also learning
		context-free languages from teacher.}
}

@article{Angluin87,
author = 	{Angluin, Dana},
title =		{Learning Regular Sets from Queries and Counterexamples},
journal = 	{Information and Computation},
year = 		1987,
month = 	Nov,
volume = 	75,
pages = 	{87--106},
comment=  {Learning regular sets from a teacher who answers membership queries,
	  and responds to false conjectures with counterexamples.  Based on
	  Gold's approach.  Also learning context-free languages from teacher.}
}

@techreport{Angluin86b,
author=   	{Angluin, Dana},
title=    	{Types of queries for concept learning},
institution=  	{Yale University Department of Computer Science},
number=   	{YALEU/DCS/TR-479},
year=     	1986,
month=    	Jun,
comment=  	{Surveys kinds of learning possible with equivalence, 
		membership, subset, superset, and disjointness queries, and 
		with random samplying.  See Angluin88c.}
}

@unpublished{Angluin87b,
author=   	{Angluin, Dana},
title=    	{A Note on Diversity},
month=    	Dec,
year=     	1987,
note=     	{Unpublished}
}

@techreport{Angluin87c,
author=   	{Angluin, Dana},
title=    	{Learning $k$-Term {DNF} Formulas Using Queries and
                 Counterexamples},
institution=   	{Yale University Department of Computer Science},
number=   	{YALEU/DCS/RR-559},
year=     	1987,
month=   	Aug
}

@techreport{Angluin88,
author=   	{Angluin, Dana},
title=    	{Negative results for equivalence queries},
institution=   	{Yale University Department of Computer Science},
number=   	{YALEU/DCS/RR-648},
year=     	1988,
month=   	Sep
}

@techreport{Angluin88b,
author = 	{Angluin, Dana},
title = 	{Equivalence Queries and {DNF} formulas},
institution=   	{Yale University Department of Computer Science},
number=   	{YALEU/DCS/RR-659},
year=     	1988,
month=   	Nov
}

@article{Angluin88c,
author = 	{Angluin, Dana},
title = 	{Queries and Concept Learning},
journal = 	{Machine Learning},
volume = 	2,
number = 	4,
month = 	Apr,
year = 		1988,
pages = 	{319--342}
}

@inproceedings{Angluin92,
author = 	{Angluin, Dana},
title = 	{Computational Learning Theory: Survey and Selected
                 Bibliography},
booktitle = 	{Proceedings of the Twenty-Fourth Annual {ACM} Symposium on
		 Theory of Computing},
year = 		1992,
month = 	May,
pages = 	{351--369}
}

@inproceedings{AngluinFrPi90,
author = 	{Angluin, Dana and Michael Frazier and Leonard Pitt},
title = 	{Learning Conjunctions of {H}orn Clauses}, 
booktitle = 	{Proceedings of IEEE FOCS Conference},
publisher = 	{IEEE},
year = 		1990,
address = 	{St. Louis, Missouri},
month = 	Oct,
pages = 	{186--192}
}

@techreport{AngluinGaSm87,
author=		{Angluin, Dana and William I. Gasarch and Carl H. Smith},
title=		{Training Sequences},
institution =	{University of Maryland Institute for Advanced Computer
		Studies},
number=		{UMIACS-TR-87-37},
year=		1987,
month=		Aug,
comment =	{Shows how to learn hard total functions by being taught 
		relevant other functions first.}
}

@techreport{AngluinHeKa89,
author = 	{Angluin, Dana and Hellerstein, Lisa and Karpinski, Marek},
title = 	{Learning Read-Once Formulas with Queries},
institution = 	{University of California}, 
number = 	{UCB/CSD 89/528},
year = 		1989,
comment = 	{To appear in JACM}
}


@inproceedings{AngluinKh91,
author = 	{Angluin, Dana and Michael Kharitonov},
title = 	{When Won't Membership Queries Help?},
booktitle = 	{Proceedings of the Twenty-Third Annual ACM Symposium on
		 Theory of Computing},
address = 	{New Orleans, Louisiana},
year = 		1991,
month = 	May,
pages = 	{444--454}
}

@techreport{AngluinLa86,
author=  	{Angluin, Dana and P. D. Laird},
title=    	{Identifying k-CNF formulas from noisy examples},
institution=  	{Yale University Department of Computer Science},
number=   	{YALEU/DCS/TR-478},
year=     	1986,
month=    	Jun,
comment=  	{Error model assumes random error rate < 1/2 in classifications
		provided for examples. Algorithm tries to minimize number of 
		examples which are misclassified by chosen hypothesis.
		Published as AngluinLa88.}
}

@article{AngluinLa88,
author=   	{Angluin, Dana and Philip Laird},
title=    	{Learning from noisy examples},
journal=  	{Machine Learning},	
year=     	1988,
volume=   	2,
number=   	4,
pages=    	{343--370},
comment=  	{Error model assumes random error rate < 1/2 in classifications
		provided for examples. Algorithm tries to minimize number of 
		examples which are misclassified by chosen hypothesis.}
}

@inproceedings{AngluinSl91,
author = 	{Angluin, Dana and Donna K. Slonim},
title =		{Learning Monotone {DNF} with an Incomplete Membership Oracle},
booktitle = 	{Proceedings of COLT '91},
publisher = 	{Morgan Kaufmann},
year = 		1991,
pages = 	{139--146},
tag=		{TOC-display},
}

@article{AngluinSl94,
author = 	{Angluin, Dana and Donna K. Slonim},
title =		{Randomly Fallible Teachers: 
		Learning Monotone {DNF} with an Incomplete Membership Oracle},
journal=  	{Machine Learning},
year=     	1994,
month=    	Jan,
volume=   	14,
number=   	1,
pages=    	{7--26},
tag=		{TOC-display},
note= 		{A preliminary version of this paper appeared in 	
		COLT '91}
}

@article{AngluinSm83,
author=   	{Angluin, Dana and Carl H. Smith},
title=    	{Inductive Inference: Theory and Methods},
journal=  	{Computing Surveys},
year=     	1983,
month=    	Sep,
volume=   	15,
number=   	3,
pages=    	{237--269},
comment=  	{Comprehensive survey of inductive inference a la Gold [Go67].}
}

@article{AngluinVa79,
author=    	{Angluin, Dana and Leslie G. Valiant},
title=     	{Fast probabilistic algorithms for {H}amiltonian circuits and 
		matchings},
journal=   	{Journal of Computer and System Sciences},
volume=    	18,
number=    	2,
pages=     	{155--193},
year=      	1979,
month=     	Apr,
comment=   	{States nice form of Chernoff bounds.}
}

@book{AnthonyBi92,
author = 	{Anthony, Martin and Norman Biggs},
title = 	{Computational Learning Theory},
publisher = 	{Cambridge University Press},
year = 		1992,
series = 	{Cambridge Tracts in Theoretical Computer Science (30)}
}


@article{ArapostathisMa90,
author=    	{Arapostathis, Aristotle and Steven I. Marcus},
title=     	{Analysis of an Identification Algorithm Arising in the
		Adaptive Estimation of Markov Chains},
journal=   	{Math. Control Signals Systems},
volume=    	3,
pages=     	{1--29},
year=      	1990
}


@mastersthesis{Aslam92,
author = 	{Aslam, Javed A.},
title = 	{Inferring Graphs from Walks},
school = 	{Massachusetts Institute of Technology},
month =		Jan,
year =		1992
}


@techreport{Aslam95,
author=		{Aslam, Javed A.},
title=		{Noise Tolerant Algorithms for Learning and Searching},
year=		1995,
institution=	{Massachusetts Institute of Technology},
number=		{MIT-LCS-TR-657}
}


@inproceedings{AslamDe93,
author = 	{Aslam, Javed A. and Scott E. Decatur},
title = 	{General Bounds on Statistical Query Learning and {PAC}
		 Learning with Noise via Hypothesis Boosting},
booktitle = 	{Proceedings of the 34th Annual Symposium on
		 Foundations of Computer Science},
month = 	Nov,
year = 		1993,
pages = 	{282--291}
}



@techreport{AslamDe94,
author=		{Aslam, Javed and Scott Decatur},
title=		{Improved Noise-Tolerant Learning and Generalized
		Statistical Queries},
month=		jul,
year=		1994,
institution=	{Harvard University},
number=		{TR-17-94}
}

@inproceedings{AslamDe95,
  author = 	 "Aslam, Javed and Scott Decatur",
  title = 	 "Specification and Simulation of Statistical Query
		  Algorithms for Efficiency and Noise Tolerance",
  booktitle =	 "Proceedings of the Eighth Annual {ACM} Workshop on
		  Computational Learning Theory",
  year =	 1995,
  publisher =	 "ACM Press",
  month =	 jul,
  pages =        {437--453}
}


@techreport{AslamDh90,
author = 	{Aslam, Javed A. and Aditi Dhagat},
title = 	{On-line Algorithms for 2-coloring Hypergraphs via Chip Games},
institution = 	{MIT Laboratory for Computer Science},
number = 	{MIT/LCS/TM-439},
month =		Dec,
year = 		1990
}

@inproceedings{AslamDh91,
author = 	{Aslam, Javed A. and Aditi Dhagat},
title = 	{Searching in the Presence of Linearly Bounded Errors},
booktitle = 	{Proceedings of the Twenty-Third Annual {ACM} Symposium on
		Theory of Computing},
month = 	May,
year = 		1991,
pages = 	{486--493}
}

@article{AslamDh93,
author = 	{Aslam, Javed A. and Aditi Dhagat},
title = 	{On-line Algorithms for 2-coloring Hypergraphs via Chip Games},
journal = 	{Theoretical Computer Science},
volume =	{112},
number =	{2},
month = 	May,
year = 		1993,
pages = 	{355--369}
}

@inproceedings{AslamRi90,
author = 	{Aslam, Javed A. and Ronald L. Rivest},
title =		{Inferring Graphs from Walks},
booktitle = 	{Proceedings of the Third Annual Workshop on Computational
		Learning Theory},
publisher = 	{Morgan Kaufmann},
year = 		{1990},
pages = 	{359--370},
tag=		{TOC-display}
}

@inproceedings{AspnesBeFuRu91,
author = 	{Aspnes, James and Richard Beigel and Merrick Furst 
		and Steven Rudich},
title = 	{The expressive power of polynomials},
booktitle = 	{23rd Annual Symposium on Foundations of Computer Science},
year = 		{1982},
month =		May,
pages = 	{402--409}
}


@article{Assouad83,
author = 	{Assouad, Patrick},
title = 	{Densit\'e et Dimension},
journal = 	{Ann. Inst. Fourier},
address = 	{Grenoble},
year = 		1983,
pages = 	{233--282},
comment = 	{In French. Survey of properties of VC classes.}
}

@incollection{Atkeson89,
author = 	{Atkeson, Christopher G.},
title = 	{Learning Arm Kinematics and Dynamics},
booktitle = 	{Annual Review of Neuroscience},
publisher = 	{Annual Reviews},
volume = 	12,
year = 		1989,
pages = 	{157--183}
}

@article{AwerbuchBeRiSi99,
author =	{Awerbuch, Baruch and Margrit Betke and Ronald L.
		 Rivest and Mona Singh},
title =		{Piecemeal Graph Exploration by a Mobile Robot},
journal =       {Information and Computation},
volume=         152,
number =        2,
pages  =	{155--172}
month =         Aug,
year =		1999,
}

@incollection{AwerbuchBeRiSi95,
author = 	{Baruch Awerbuch and Margrit Betke and Ronald L. Rivest and
                 Mona Singh},
title =	 	{Piecemeal Graph Exploration by a Mobile Robot},
booktitle = 	{Proceedings of COLT '95},
publisher = 	{ACM},
year = 		1995,
pages = 	{321--328}
}

@phdthesis{Bachrach92,
author = 	{Jonathan Richard Bachrach},
title = 	{Connectionist Modeling and Control of Finite-State
		Environments},
school = 	{University of Massachusetts},
year = 		1992,
month = 	Feb
}

@incollection{Bainbridge77,
author=		{E. S. Bainbridge},
title=		{The fundamental duality of system theory},
booktitle=	{Systems:  Approaches, Theories, Applications},
editor=		{W. E. Hartnett},
publisher=	{D. Reidel Publishing Company},
year=		1977,
pages=		{45--61}
}


@inproceedings{Bar-EliBeFiYa92,
author=   	{Bar-Eli, E. and P. Berman and A. Fiat and P. Yan},
title=    	{On-line Navigation in a Room},
booktitle = 	{Symposium on Discrete Algorithms},
year = 		{1992},
pages = 	{237--249}
}

@article{Barron93,
author=   	{Andrew R. Barron}, 
title=    	{Universal Approximation Bounds for Superpositions of 
		a Sigmoidal Function},
journal=  	{IEEE Transactions on Information Theory},
year=     	1993,
month=    	May,
volume=   	{39},
number=   	3,
pages=    	{930--945}
}

@article{Bartlett52,
author=   	{Bartlett, M. S.},
title=    	{The Statistical Significance of Odd Bits of Information},
journal=  	{Biometrika},
year=     	1952,
volume=   	39,
pages=    	{228--237},
comment=  	{Variation on likelihood measure proposed.}
}

@article{BarzdinFr72,
author = 	{J. M. Barzdin and R. V. Frievald},
title = 	{On the prediction of general recursive functions},
journal = 	{Soviet Mathematics Doklady},
year = 		{1972},
volume = 	{13},
pages = 	{1224--1228},
comment = 	{Introduces the on-line mistake bound learning model
		 (although in a Gold-style framework)}
}

@article{Battiti89,
author = 	{Roberto Battiti},
title = 	{Accelerated Backpropagation Learning: Two
		 Optimization Methods},
journal = 	{Complex Systems},
volume = 	3,
number = 	4,
year = 		1989,
month = 	Aug,
pages = 	{331--342},
comment = 	{Gets one order of magnitude improvement over ordinary
		backpropagation using variable step size and a version
		of the conjugate gradient method.}
} 

@inproceedings{BaumHa89,
author = 	{Baum, Eric B. and David Haussler},
title = 	{What Size Net Gives Valid Generalization?},
booktitle = 	{Advances in Neural Information Processing Systems I},
publisher = 	{Morgan Kaufmann},
year = 		{1989},
pages = 	{81--90},
comment = 	{VC-dimension arguments}
}

@article{Baum72,
author=   	{Baum, Leonard E. and J. A. Eagon},
title=    	{An Inequality with Applications to Statistical Estimation for
  	  	Probabilistic Functions of Markov Processes and to a Model for 
		Ecology},
journal=  	{Bulletin of the American Mathematical Society},
year=     	1967,
volume=   	73,
pages=    	{360--363},
comment=  	{Gives a technique for maximizing a polynomial with 
		nonnegative coefficients and homogeneous of degree d.}
}

@article{Baum90,
author=		{Baum, Eric B.},
title=		{On Learning a Union of Half Spaces},
journal = 	{Journal of Complexity},
year=		1990,
volume = 	6,
number = 	1,
month=		Mar,
pages = 	{67--101}
}

@article{BahlJeMe83,
author=   	{Bahl, Lalit R. and Frederick Jelinek and Robert L. Mercer},
title=    	{A Maximum Likelihood Approach to Continuous Speech 
		Recognition},
journal=  	{IEEE Transactions on Pattern Analysis and Machine 
		Intelligence},
year=     	1983,
month=    	Mar,
volume=   	{PAMI-5},
number=   	2,
pages=    	{179--190},
comment=  	{Describes Markov modeling and analysis techniques.}
}

@article{BearCoEb87,
author = 	{Mark F. Bear and Leon N. Cooper and Ford F. Ebner},
title = 	{A Physiological Basis for a Theory of Synapse Modification},
journal = 	{Science},
volume = 	237,
year = 		1987,
month = 	{Jul 3},
pages = 	{42--48},
comment = 	{Proposes that change in weight w_ij from i to j goes as
			 d(w_ij)/dt = \phi(a_i,avg(a_i)) a_j where \phi 
		is negative below (say) avg(a_i)**2, and positive  above it.}
}

@phdthesis{Beer89,
author = 	{Randall Dean Beer},
title = 	{Intelligence as Adaptive Behavior: An Experiment in
		 Computational Neuroethology},
school = 	{Case Western Reserve University},
year = 		1989,
month = 	Aug,
comment = 	{Simulates a cockroach using specially-designed neural
		circuitry}
}

@inproceedings{Bellare92,
author=   	{Mihir Bellare},
title = 	{A technique for upper bounding the spectral norm with
		 applications to learning},
booktitle = 	{Fifth Workshop on Computational Learning Theory},
address = 	{Santa Cruz, Cal.\ },
year = 		1992,
month=          Jul,
pages=          {62--70}
}


@techreport{Ben-DavidBe91,
author =        {Ben-David, Shai and Gyora M. Benedek},
title  =        {Measurability Constraints on PAC Learnability},
institution =   {Technion, Haifa},
year   =	1991,
comment   =	{The year listed here may be incorrect.}
}

@inproceedings{Ben-DavidBeMa89,
author =	{Ben-David, Shai and Gyora M. Benedek and Yishay Mansour},
title = 	{A Parametrization Scheme for Classifying Models of 
		Learnability},
booktitle = 	{Proceedings of COLT '89},
publisher = 	{Morgan Kaufmann},
year = 		{1989},
pages=		{285--302},
tag=		{TOC-display}
}

@inproceedings{BenderSl94,
author = 	{Bender, Michael A. and Donna K. Slonim},
title = 	{The power of team exploration: two robots can learn
unlabeled directed graphs},
booktitle = 	{Proceedings of the Thirty-Fifth Annual Symposium on
		Foundations of Computer Science},
year = 		{1994},
month = 	Nov,
pages = 	{75--85}
}

@unpublished{Benedek88,
author=   	{Benedek, Gyora M.},
title=    	{Ph.D. dissertation, in preparation},
year=     	1988,
note = 	  	{(To appear.)}
}

@inproceedings{BenedekIt88,
author=   	{Benedek, Gyora M. and Alon Itai},
title=    	{Nonuniform Learnability},
booktitle=	{ICALP},
month=    	Jul,
year=     	1988,
pages=    	{82--92}
}

@inproceedings{BenedekIt88b,
author = 	{Benedek, G. M. and A. Itai},
title = 	{Learnability by fixed distribution},
booktitle = 	{Proceedings of the First Workshop on Computational 
		Learning Theory},
year = 		1988,
publisher = 	{Morgan Kaufmann},
pages = 	{82--92}
}

@InProceedings{BergmanRivest95,
  year =	1995,
  title =	"Picking the Best Expert from a Sequence",
  author =	"Ruth Bergman and Ronald L. Rivest",
  booktitle =	"Proceedings of the Fifth International Workshop on
		 Artificial Intelligence and Statistics",
  address =	"Fort Lauterdale, FL",
  month =	"January",
  pages =	{219--228}
}

@techreport{BerlinerGo84,
author=   	{Berliner, Hans and Gordon Goetsch},
title=    	{A Quantitative Study of Search Methods and the Effect of
	  	Constraint Satisfaction},
institution= 	{CMU Computer Science Department},
year=     	1984,
month=    	Jul,
number=   	{CMU-CS-84-147},
comment=  	{Empirical comparative study of search heuristics for 
		Superpuzz, a card solitaire game.}
}


@book{BerryFr85,
author = 	{D. A. Berry and B. Fristedt},
title = 	{Bandit Problems--Sequential Allocation of Experiments},
year = 		1985,
publisher = 	{Chapman and Hall},
address = 	{New York}
}

@article{Berwick87,
author=   	{Berwick, Robert C.},
title=    	{Language Learning by Automata Induction},
journal = 	{Machine Learning},
volume = 	2,
year = 		1987,
month = 	{Jul 3},
pages = 	{9--38},
tag=		{TOC-display}
}

@mastersthesis{Betke92,
author = 	{Margrit Betke},
title = 	{Algorithms for Exploring an Unknown Graph},
school =	{MIT Department of Electrical Engineering and Computer 
		Science},
year =		1992,
month =		Feb,
note = 		{(Published as MIT Laboratory for Computer Science
		  Technical Report MIT/LCS/TR-536, March, 1992)}
}

@inproceedings{BetkeRiSi93,
author=   	{Betke, Margrit and Ronald L. Rivest and Mona Singh},
title=    	{Piecemeal Learning of an Unknown Environment},
booktitle=	{Proceedings of the 1993 Conference on Computational
		 Learning Theory},
address=	{Santa Cruz, CA},
month=    	Jul,
year=     	1993,
pages = 	{277--286},
note=           {(Published as MIT AI-Memo 1474, CBCL-Memo 93; and in
Machine Learning, Feb/Mar 1995.)}
}

@article{BetkeRiSi95,
author=   	{Betke, Margrit and Ronald L. Rivest and Mona Singh},
title=    	{Piecemeal Learning of an Unknown Environment},
journal=	{Machine Learning},
volume=		18,
number=		{2/3},
publisher=	{Kluwer Academic Publishers, Boston},
month=    	{Feb/Mar},
year=     	1995,
pages = 	{231--254}
}

@mastersthesis{Blum89,
author=   	{Blum, Avrim},
title=    	{On the Computational Complexity of Training Simple
		Neural Networks},
school=   	{MIT Department of Electrical Engineering and Computer 
		Science},
year=     	1989,
month=    	May,
note = 		{(Published as Laboratory for Computer Science Technical
		  Report MIT/LCS/TR-445 (May, 1989))}
}

@inproceedings{Blum90,
author =	{Blum, Avrim},
title = 	{Learning Boolean Functions in an Infinite Attribute Space},
booktitle = 	{Proceedings of the Twenty-Second Annual ACM Symposium
		on Theory of Computing},
address=  	{Baltimore, Maryland},
year=     	1990,
pages=		{64-72},
month=    	May,
tag=		{TOC-display}
}


@inproceedings{Blum90a,
author =	{Blum, Avrim},
title = 	{Separating {PAC} and Mistake-Bound Learning Models
		over the {B}oolean Domain},
booktitle = 	{Proceedings of COLT '90},
publisher = 	{Morgan Kaufmann},
year = 		{1990},
note=		{Abstract only},
pages =   	{393},
tag=		{TOC-display}
}

@inproceedings{Blum90b,
author =	{Blum, Avrim},
title = 	{Separating Distribution-Free and Mistake-Bound Learning Models
		over the {B}oolean Domain},
booktitle = 	{Proceedings of the Thirty-First Annual Symposium on
		Foundations of Computer Science},
publisher = 	{IEEE},
year = 		{1990},
pages = 	{211-218},
volume = 	{I},
tag=		{TOC-display}
}

@article{Blum92,
author = 	{Blum, Avrim},
title = 	{Learning Boolean Functions in an Infinite Attribute Space},
journal = 	{Machine Learning},
volume = 	9,
number = 	4,
month = 	Oct,
year = 		1992,
pages = 	{373--386}
}

@inproceedings{BlumCh93,
author = 	{Blum, Avrim and P. Chalasani},
title = 	{An on-line algorithm for improving performance in
navigation},
booktitle = 	{Proceedings of the Thirty-Fourth Annual Symposium on
		Foundations of Computer Science},
year = 		1993,
month = 	Nov,
pages =		{2--11}
}

@inproceedings{BlumRaSc91,
author = 	{Blum, Avrim and Raghavan, Prabhakar and Schieber, Baruch},
title = 	{Navigating in Unfamiliar Geometric Terrain},
booktitle = 	{Proceedings of Twenty-Third ACM Symposium on Theory of
		Computing},
publisher = 	{ACM},
year = 		1991,
pages = 	{494--504}
}

@inproceedings{BlumRu92,
author = 	{Blum, Avrim and Steven Rudich},
title = 	{Fast Learning of $k$-term {DNF} Formulas with Queries},
booktitle = 	{Proceedings of Twenty-Fourth ACM Symposium on Theory of
		Computing},
publisher = 	{ACM},
year = 		1992,
pages = 	{382--389}
}

@inproceedings{BlumSi90,
author =	{Blum, Avrim and Mona Singh},
title = 	{Learning Functions of $k$ Terms},
booktitle = 	{Proceedings of COLT '90},
publisher = 	{Morgan Kaufmann},
year = 		{1990},
pages=		{144--153},
tag=		{TOC-display}
}

@inproceedings{BlumSa77,
author =	{Blum, M. and W. J. Sakoda},
title = 	{On the capability of finite automata in 
		2 and 3 dimensional space},
booktitle = 	{18th Annual Symposium on Foundations of Computer Science},
publisher = 	{IEEE},
year = 		{1977},
pages=		{147--161},
}

@inproceedings{BlumKo78,
author =	{Blum, Manuel and Dexter Kozen}, 
title = 	{On the Power of the Compass (or, Why Mazes are 
		Easier to Search than Graphs)}, 
booktitle = 	{19th Annual Symposium on Foundations of Computer Science},
publisher = 	{IEEE},
year = 		{1978},
pages=		{132--142},
}

@article{BlumBl75,
author=   	{Blum, Lenore and Manuel Blum},
title=    	{Toward a Mathematical Theory of Inductive Inference},
journal=  	InfCtrl,
year=     	1975,
month=   	Jun,
volume=   	28,
number=   	2,
pages=    	{125--155},
comment=  	{Recursion-theoretic, a la Gold [Go67].}
}

@inproceedings{BlumFuJaKeMaRu94,
author=		{Blum, Avrim and Merrick Furst and Jeffery Jackson and
		Michael Kearns and Yishay Mansour and Steven Rudich},
title=		{Weakly Learning {DNF} and Characterizing Statistical
		Query Learning Using Fourier Analysis},
booktitle=	"Proceedings of the Twenty-Sixth Annual ACM Symposium on
		the Theory of Computing",
year=		1994,
note=		{To Appear}
}

@incollection{BlumRi89,
author =	{Blum, Avrim and Ronald L. Rivest},
title = 	{Training a 3-node neural net is {NP-Complete}},
booktitle = 	{Advances in Neural Information Processing Systems I},
publisher = 	{Morgan Kaufmann},
year = 		1989,
editor = 	{David S. Touretzky},
pages = 	{494--501},
tag=		{TOC-display}
}

@article{BlumRi92,
author =	{Blum, Avrim and Ronald L. Rivest},
title = 	{Training a 3-node neural net is {NP-Complete}},
journal=  	{Neural Networks},
volume=   	5,
year=     	1992,
pages=    	{117-127},
tag=		{TOC-display}
}


@inproceedings{BlumerEhHaWa86a,
author=   	{Blumer, Anselm and Andrzej Ehrenfeucht and David Haussler and
	   	Manfred K. Warmuth},
title=    	{Classifying Learnable Geometric Concepts with the 
	  	{V}apnik-{C}hervonenkis Dimension},
booktitle= 	{Proceedings of the Eighteenth Annual ACM Symposium on Theory
           	of Computing},
address=  	{Berkeley, California},
year=     	1986,
month=    	May,
pages=    	{273--282},
comment=  	{Shows equivalence between finite VC dimension and 
		learnability of geometric concepts.}
}

@techreport{BlumerEhHaWa86b,
author=   	{Blumer, Anselm and Andrzej Ehrenfeucht and David Haussler and
	   	Manfred K. Warmuth},
title=    	{Occam's Razor},
institution= 	{U.C. Santa Cruz Computer Science Laboratory},
number=  	{UCSC-CRL-86-2},
year=     	1986,
month=    	Feb,
comment=  	{Defines `Occam-algorithm' which may produce a hypothesis of
	   	complexity $n^c m^\alpha$ for fixed $c$ and $\alpha < 1$, and
	   	shows that Occam-algorithms need only polynomially many 
		samples.}
}

@article{BlumerEhHaWa87,
author=   	{Blumer, Anselm and Andrzej Ehrenfeucht and David Haussler and
	   	Manfred K. Warmuth},
title=    	{Occam's Razor},
journal=  	{Information Processing Letters},
volume=   	24,
year=     	1987,
month=    	Apr,
pages=    	{377--380},
comment=  	{Defines `Occam-algorithm' which may produce a hypothesis of
	   	complexity $n^c m^\alpha$ for fixed $c$ and $\alpha < 1$, and
	   	shows that Occam-algorithms need only polynomially many 
		samples.}
}

@article{BlumerEhHaWa89,
author=   	{Blumer, Anselm and Andrzej Ehrenfeucht and David Haussler and
	   	Manfred K. Warmuth},
title=    	{Learnability and the {V}apnik-{C}hervonenkis Dimension},
journal= 	{Journal of the ACM},
year = 		1989,
volume = 	36,
number = 	4,
pages = 	{929--965},
comment=	{An earlier version is available as
		U. C. Santa Cruz Computer Science Laboratory Tech.\ Report
		UCSC-CRL-87-20 (Nov.\ 1987).}
}


@article{BlumerLi89,
author = 	{Anselm Blumer and Nick Littlestone},
title = 	{Learning Faster than Promised by the {V}apnik-{C}hervonenkis
		 Dimension},
journal = 	{Discrete Applied Mathematics},
year = 		1989,
volume = 	24,
pages = 	{47--53}
}


@article{BoardPi92,
author=		{Board, Raymond and Leonard Pitt},
title=		{On the Necessity of {O}ccam Algorithms},
year=		{1992},
journal= 	{Theoretical Computer Science},
volume=		100,
pages = 	{157--184}
}


@book{Bongard70,
author=   	{Bongard, M.},
title=    	{Pattern Recognition},
publisher= 	{Spartan Books},
year=      	{1970}
}

@unpublished{Boucheron88,
author = 	{St\'ephane Boucheron},
title = 	{Learnability from positive examples in the {V}aliant 
		framework},
note = 		{Unpublished manuscript},
year = 		{1988}
}

@inproceedings{BoucheronSa88,
author=   	{Boucheron, St\'ephane and Jean Sallantin},
title=    	{Some remarks about space-complexity of learning, and
		 circuit complexity of recognizing},
booktitle=	{Proceedings of the 1988 Workshop on Computational
		 Learning Theory},
address=	{Cambridge, MA},
month=    	Aug,
year=     	1988,
pages = 	{125--138}
}

@article{BoultonWa73,
author=   	{Boulton, D. M. and C. S. Wallace},
title=    	{An information measure for hierarchic classification},
journal=  	{The Computer Journal},
volume=   	16,
number=   	3,
year=     	1973,
month=    	Aug,
pages=    	{254--261}
}

@article{BoultonWa75,
author=   	{Boulton, D. M. and C. S. Wallace},
title=    	{An information measure for single-link classification},
journal=  	{The Computer Journal},
volume=   	18,
number=   	3,
year=     	1973,
month=    	Aug,
pages=    	{236--238}
}

@book{Braitenberg84,
author = 	{Valentino Braitenberg},
title = 	{Vehicles -- Experiments in Synthetic Psychology},
year = 		1984,
publisher = 	{MIT Press}
}


@article{BrandmanHeOr90,
author=   	{Brandman, Y. and J. Hennessy and A. Orlitsky},
title=    	{A spectral lower bound technique for the size of 
		 decision trees and two level circuits},
journal=  	{IEEE Transactions on Computers},
year=     	1990,
volume=   	{39},
number=   	2,
pages=    	{282--287}
}


@book{BreimanFrOlSt84,
author=   	{Breiman, Leo and Jerome H. Friedman and Richard A. Olshen and
		Charles J. Stone},
title=    	{Classification and Regression Trees},
publisher= 	{Wadsworth International Group},
year=      	1984,
comment=   {Review of procedures for inferring decision trees from data.}
}


@article{Brooks91,
author = 	{Rodney A. Brooks},
title = 	{New Approaches to Robotics},
journal = 	{Science},
year = 		1991,
month = 	Sep,
volume = 	{253},
number = 	{5025},
pages = 	{1227--1232}
}


@article{Bruck90,
author=   	{Bruck, J.},
title=    	{Harmonic analysis of polynomial threshold functions},
journal=  	{SIAM J. on Disc. Math},
volume=   	3,
number =	2,
year=     	1990,
month =		May,
pages=    	{168--177}
}


@inproceedings{BruckSm90,
author=   	{Bruck, J. and R. Smolensky},
title = 	{Polynomial threshold functions, {$AC^0$} functions 
		 and spectral norms},
booktitle = 	{31st Annual Symposium on Foundations of Computer Science},
year = 		{1990},
month =		Oct,
pages = 	{632--641}
}


@unpublished{BshoutyHaHeKa91,
author=   	{Bshouty, Nader and Lisa Hellerstein and Thomas Hancock and 
		Marek Karpinski},
title=    	{Read-once threshold formulas, justifying assignments,
		and transformations},
month=    	Dec,
year=     	{1991},
note=     	{To appear in the Journal of Complexity Theory, 93}
}


@incollection{Buehler70,
author=   	{Buehler, Robert J.},
title=    	{Measuring Information and Uncertainty},
booktitle=  	{Foundations of Statistical Inference},
editor=   	{V. P. Godambe and D. A. Sprott},
year=     	1970,
publisher=  	{Holt, Rinehard, and Winston},
comment=  	{General study of payoff functions that encourage honesty for
           	someone making probabilistic predictions (e.g. a weatherman).}
}

@book{Campbell90,
author = 	{Jeremy Campbell},
title = 	{The Improbable Machine},
year = 		1990,
publisher = 	{Simon \& Schuster}
}

@inproceedings{CarbonellG87,
author=   	{Carbonell, Jaime G. and Yolanda Gil},
title=    	{Learning by Experimentation},
booktitle=	{Proceedings of the Fourth International Workshop on Machine
		Learning},
month=    	Jun,
year=     	1987,
editor=   	{Pat Langley},
pages=    	{256--266},
publisher=	{Morgan Kaufmann}
}

@inproceedings{CesaFrHeHaScWa93,
author=	   	{Cesa-Bianchi, N.  and  Freund, Y. and  Helmbold, D. and  Haussler, D. and  Schapire, R. and Warmuth, M.},
title=	   	{How to Use Expert Advice},
booktitle= 	{Proceedings of the Eighteenth Annual ACM Symposium on Theory
           	of Computing},
address=   	{San Diego, CA},
year=	   	1993,
month=	   	may,
pages=	   	{382--391}
}

@inproceedings{CestnikKoBr87,
author=	   	{B. Cestnik and I. Kononenkko and I. Bratko},
title=	   	{Assistant 86: A Knowledge-Elicitation Tool for Sophisticated 
	   	Users},
booktitle= 	{Progress in Machine Learning--Proceedings of EWSL 87: 
	   	2nd European Working Session on Learning},
address=   	{Bled, Yogoslavia},
year=	   	1987,
editor=	   	{Bratko, I. and N. Lavrac},
month=	   	may,
pages=	   	{31--45}
}

@article{ChangLa87,
author = 	{Fu Chang and Tze Leung Lai},
title = 	{Optimal Stopping and Dynamic Allocation},
journal = 	{Advances in Applied Probability},
volume = 	19,
year = 		1987,
pages = 	{829--853},
comment = 	{Bandit problem}
}

@unpublished{Charniak??,
author=   	{Charniak, Eugene},
title=    	{The Bayesian Basis of Common Sense Medical Diagnosis},
year=     	{??},
comment=  	{Where was this published??.
	   	Argues in favor of Bayesian approach for medical diagnosis.},
note = 		{~}
}

@inproceedings{Cheeseman83,
author=   	{Cheeseman, Peter C.},
title=    	{A Method of Computing Generalized Bayesian Probability Values
	   	for Expert Systems},
booktitle= 	{Proceedings Eighth International Conference on Artificial 
	   	Intelligence (Karlruhe, West Germany)},
year=      	1983,
month=     	Aug,
pages=     	{198--202},
comment=   	{Describes iterative graph-oriented method for computing 
	   	a maximum-entropy distribution subject to constraints.}
}

@inproceedings{Cheeseman84,
author=   	{Cheeseman, Peter C.},
title=    	{Learning of Expert Systems from Data},
booktitle= 	{Proceedings of the Workshop on Principles of Knowledge-Based
	   	Systems},
year=      	1984,
month=     	Dec,
pages=     	{115--122},
comment=   	{Describes a `message-length' approach to inferring significant
	   	contingencies in a contingency table.}
}

@inproceedings{Cheeseman85,
author=   	{Cheeseman, Peter C.},
title=    	{In Defense of Probability},
booktitle= 	{Proceedings of the Ninth International Joint Conference on
	   	Artificial Intelligence},
year=     	1985,
pages=    	{1002--1009},
comment=  	{Argues in favor of subjective Bayesianism by refuting some
	  	common misconceptions.}
}

@article{Cheeseman88,
author = 	{Cheeseman, Peter C.},
title = 	{An inquiry into computer understanding},
journal = 	{Computational Intelligence},
year = 		1988,
month = 	Feb,
volume = 	4,
number = 	1,
pages = 	{58--66},
comment = 	{More defense of Bayesian inference}
}

@inbook{CheesemanKeSeStTaFr90,
author = 	{Cheeseman, Peter and James Kelly and Matthew Self and
		John Stutz and Will Taylor and Don Freeman},
title = 	{Autoclass: A Bayesian Classification System},
booktitle = 	{Readings in Machine Learning},
year =		1990,
pages = 	{206--306},
address = 	{San Mateo, California},
publisher = 	{Morgan Kaufmann},
comment = 	{edited by Jude W. Shavlik and Thomas G. Dietterich}
}

@inproceedings{CheesemanSeKeTaFrSt88,
author = 	{Cheeseman, Peter C. and Matthew Self and
		Jim Kelly and Will Taylor and Don Freeman and
		John Stutz},
title = 	{Bayesian Classification},
booktitle = 	{AAAI 88 Proceedings},
year = 		1988,
pages = 	{607--611}
}

@article{Chernoff52,
author = 	{H. Chernoff},
title = 	{A measure of asymptotic efficiency for tests of a hypothesis
		based on the sum of observations},
journal = 	{Annals of Math. Stat.},
year = 		1952,
volume = 	23,
pages = 	{493--509},
comment = 	{Contains foundations for ``Chernoff bounds''}
}

@unpublished{ClarkNi87,
author=   	{Peter Clark and Tim Niblett},
title=    	{The CN2 Induction Algorithm},
year=     	1987,
institution= 	{The Turing Institute},
comment=  	{Experimental study of rule induction, with accomodation for 
		noise.},
note = 		{~}
}

@inproceedings{ClarkNi87b,
author=	   	{Clark, P. and T. Niblett},
title=	   	{Induction in Noisy Domains},
booktitle= 	{Progress in Machine Learning--Proceedings of EWSL 87: 
	   	2nd European Working Session on Learning},
address=   	{Bled, Yogoslavia},
year=	   	1987,
editor=	   	{Bratko, I. and N. Lavrac},
month=	   	may,
pages=	   	{11--30}
}

@inbook{CohenFe68,
editor=   	{Cohen, Paul R. and Edward A. Feigenbaum},
title=    	{The Handbook of Artificial Intelligence},
volume=   	3,
year=     	1968,
chapter=  	{XIV: {\em Learning and Inductive Inference}},
publisher= 	{William Kaufman, Inc.},
address=   	{Los Altos, California},
pages=     	{324--511}
}

@techreport{Connell89,
author = 	{Jonanthan Connell},
title = 	{A Colony Architecture for an Artificial Creature},
institution = 	{MIT AI Laboratory},
number = 	{AI-TR 1151},
year = 		1989,
comment = 	{Design of Herbert, who collects soda cans from desks.}
}



@article{CookRa80,
author = 	{Cook, Stephen A. and Charles W. Rackoff},
title = 	{Space lower bounds for maze threadability on 
		restricted machines},
journal = 	{SIAM Journal on Computing},
year = 		1980,
volume = 	9,
pages = 	{636--652}
}

@article{Cooper62,
author = 	{P. Cooper},
title = 	{The hypersphere in pattern recognition},
journal = 	{Information and Control},
year = 		1962,
volume = 	5,
pages = 	{324--346}
}


@book{CormenLeRi90,
author = 	{Cormen, Thomas H. and Charles E. Leiserson and 
		 Ronald L. Rivest},
title = 	{Introduction to Algorithms},
publisher = 	{MIT Press/McGraw-Hill},
year = 		{1990}
}


@article{CornuejolsFiNe77,
author = 	{Cornuejols, G. and M.L. Fisher and G.L. Nemhauser},
title = 	{Location of Bank Accounts to Optimize Float: An Analytical 
		Study of Exact and Approximate Algorithms},
journal = 	{Management Science},
year = 		{1977},
volume = 	{23},
pages = 	{789--810}
}

G. Cornuejols


@article{Cover65,
author = 	{Cover, Thomas M.},
title = 	{Geometrical and Statistical Properties of Systems of
		 Linear inequalities with applications to pattern
		 recognition},
journal = 	{IEEE Transactions on Electronic Computers},
volume = 	{EC-14},
year = 		1965,
number = 	3,
pages = 	{326--334}
}

@incollection{Cover69,
author=   	{Cover, Thomas M.},
title=    	{Learning in Pattern Recognition},
booktitle=  	{Methodologies of Pattern Recognition},
publisher=  	{Academic Press},
year=     	1969,
pages=    	{111--132},
comment=  	{Bayesian classification procedures. Learning with finite 
		memory.}
}

@article{Cover67,
author=	  	{Cover, T.M. and P.E. Hart},
title=	  	{Nearest Neighbor Pattern Classification},
journal=  	{IEEE Transactions in Information Theory},
year=     	1967,
month=    	jan,
volume=   	{IT-13},
number=   	1,
pages=    	{21--27}
}

@article{Cover73,
author = 	{Cover, Thomas M.},
title = 	{On Determining the Irrationality of the Mean of
                a Random Variable},
journal = 	{The Annals of Statistics},
year = 		1973,
volume = 	1,
number = 	5,
pages = 	{862--871}
}


@incollection{CoverWa76,
author=   	{Cover, T. M. and T. J. Wagner},
title=    	{Topics in Statistical Pattern Recognition},
booktitle=  	{Communication and Cybernetics: Digital Pattern Recognition},
chapter=  	2,
editor=   	{K. S. Fu},
year=    	1976,
volume=   	10,
publisher=  	{Springer-Verlag},
comment=  	{Learning classifiers. Distribution-free techniques. Modelling
		by gambling games.  Finite memory learning.}
}


@article{Cox46,
author=   	{Cox, R.T.},
title=    	{Probability, Frequency and Reasonable Expectation},
journal=  	{American Journal of Physics},
year=     	1946,
volume=   	14,
number=   	1,
pages=    	{1--13}
}

@book{CoxeterMo72,
author= 	{H. S. M. Coxeter and W. O. J. Moser},
title= 		{Generators and Relations for Discrete Groups},
publisher= 	{Springer-Verlag},
year= 		{1972},
address= 	{New York},
edition= 	{third},
comment= 	{high-powered book on groups with, among other things,
		good discussion of Cayley graphs.}
}

@book{Coxeter73,
author= 	{H. S. M. Coxeter},
title= 		{Regular Polytopes},
publisher= 	{Dover Publications, Inc.},
year= 		{1973},
address= 	{New York},
edition= 	{second},
comment= 	{}
}

@article{Csiszar75,
author=   	{Csisz\`ar, I.},
title=    	{I-Divergence Geometry of Probability Distributions and
	   	Minimization Problems},
journal=  	{The Annals of Probability},
year=     	1975,
volume=   	3,
number=   	1,
pages=    	{146--158},
comment=  	{Generalized proof of iterative techniques for computing
	   	maximum-entropy distributions.}
}

@article{Cybenko89,
author = 	{G. Cybenko},
title = 	{Approximation by Superpositions of a Sigmoidal Function},
journal =	{Mathematics of Control},
year = 		1989,
volume=   	2,
pages=    	{303--314}
}

@unpublished{Cybenko88b,
author = 	{G. Cybenko},
title = 	{Continuous-Valued Neural Networks with Two Hidden
		 Layers are Sufficient},
institution=  	{Tufts University, Department of Computer Science},
year = 		{1988},
note = 		{(unpublished)}
}

@inproceedings{DaleyPiVeWi91,
author =	{Daley, Robert and Leonard Pitt and Mahendran Velauthapillai 
			and Todd Will},
title = 	{Relations Between Probabilistic and Team One-Shot Learners},
booktitle = 	{Proceedings of COLT '91},
publisher = 	{Morgan Kaufmann},
year = 		{1991},
pages = 	{228--239},
}

@techreport{Dalkey85,
author=   	{Dalkey, Norman C.},
title=    	{Prior Probabilities Revisited},
institution=  	{UCLA Computer Science Department},
number=   	{CSD-850007},
year=     	1985,
comment=  	{Justification of maximum-entropy via proper scoring rules for
		probability distributions.  Some consequences.}
}

@book{Darwin59,
author = 	{Charles R. Darwin},
title = 	{The Origin of Species},
year = 		1859,
publisher = 	{John Murray},
address = 	{London}
}

@book{Dawkins89,
author = 	{Richard Dawkins},
title = 	{The Selfish Gene},
year = 		1989,
edition = 	{New},
publisher = 	{Oxford University Press}
}


@techreport{DeanBaKaKoMa92,
author=   	{Dean, Thomas and Kenneth Basye and Leslie Kaelbling
		and Evangelos Kokkevis and Oded Maron},
title=    	{Inferring Finite Automata with Stochastic Output
		Functions and an Application to Map Learning},
institution=	{Brown University},
number=		{CS-92-27},
month=    	Feb,
year=     	1992,
note=		{An extended abstract version also appears in Proceedings
		of the Tenth National Conference on Artificial Intelligence,
		San Jose, CA, 1992}
}

@inproceedings{Decatur93,
author = 	{Decatur, Scott E.},
title =		{Statistical Queries and Faulty {PAC} Oracles},
booktitle = 	{Proceedings of the Sixth Annual {ACM} Workshop on Computational
		Learning Theory},
publisher = 	{{ACM} Press},
year = 		{1993}
}

@techreport{Dechter90,
author =        {Dechter, Rina},
title  =        {On the Design of Networks with Hidden Variables},
institution =   {Technion, Haifa},
year   =	1990,
month = 	Jul
}


@article{DeJong90,
author = 	{Kenneth De Jong},
title = 	{Special Issue on Genetic Algorithms},
journal = 	{Machine Learning},
volume = 	5,
number = 	4,
year = 		1990,
month = 	Oct,
publisher = 	{Kluwer Academic Publishers}
}

@article{DemingSt40,
author=   	{Deming, W. Edwards and Frederick F. Stephan},
title=    	{On a Least Squares Adjustment of a Sampled Frequency Table 
		when the Expected Marginal Totals are Known},
journal=  	{Annals Mathematical Statistics},
year=     	1940,
volume=   	11,
pages=    	{427--444},
comment=  	{Introduces iterative updating procedure; useful for 
	   	computing maximum-entropy solution.}
}

@inproceedings{DengKaPa91,
author = 	{Xiaotie Deng and Tiko Kameda and Christos H. Papadimitriou},
title = 	{How to learn an unknown environment},
booktitle = 	{Proceedings of the 32nd Symposium on Foundations of
		 Computer Science},
year = 		1991,
publisher = 	{IEEE},
pages = 	{298--303}
}

@inproceedings{DengPa90,
author = 	{Xiaotie Deng and Christos H. Papadimitriou},
title = 	{Exploring an Unknown Graph},
booktitle = 	{Proceedings of the 31st Symposium on Foundations of
		 Computer Science},
year = 		1990,
volume = 	{I},
pages = 	{355--361}
}

@article{Dennis84,
author=   	{Dennis, J.E., Jr.},
title=    	{A User's Guide to Nonlinear Optimization Algorithms},
journal=  	{Proceedings of the IEEE},
year=     	1984,
month=    	Dec,
volume=   	72,
number=   	12,
pages=    	{1765--1776},
comment=  	{Brief survey with bibliography.}
}

@article{Devroye88,
author = 	{Luc Devroye},
title = 	{Automatic Pattern Recognition: A Study of the Probability
	 	 of Error},
journal = 	{IEEE Trans.\ Pattern Analysis and Machine Intelligence},
volume = 	10,
number = 	4,
year = 		1988,
month = 	Jul,
pages = 	{530--543}
}

@inproceedings{Dietterich84,
author=   	{Dietterich, Thomas G.},
title=    	{Learning About Systems That Contain State Variables},
booktitle= 	{Proceedings of the National Conference on Artificial
           	Intelligence},
year=     	1984,
month=   	Aug,
pages=    	{96--100}
}

@phdthesis{Dolan89,
author = 	{Charles Patrick Dolan},
title = 	{Tensor Manipulation Networks: Connectionist and Symbolic
		 Approaches to Comprehension, Learning, and Planning},
school = 	{UCLA Computer Science Department},
month = 	Jun,
year = 		1989
}

@techreport{Drescher80,
author=   	{Drescher, Gary L.},
title=    	{Suggestions for Genetic {A.I.}},
institution= 	{MIT Artificial Intelligence Laboratory},
year=     	1980,
number=   	198,
month=    	Feb
}

@mastersthesis{Drescher85,
author=   	{Drescher, Gary L.},
title=    	{The Schema Mechanism: A Conception of Constructivist 
		Intelligence},
school=   	{MIT Department of Electrical Engineering and Computer 
		Science},
year=     	1985,
month=    	Feb,
comment=  	{Constructivist version of Piagetian theory.}
}

@techreport{Drescher86,
author=   	{Drescher, Gary L.},
title=    	{Genetic {AI}---Translating {P}iaget into {L}isp},
institution= 	{MIT Artificial Intelligence Laboratory},
year=     	1986,
number=   	890,
month=    	Feb
}

@inproceedings{Drescher87,
author = 	{Gary L. Drescher},
title = 	{A Mechanism for Early {Piagetian} Learning},
booktitle = 	{Proceedings of AAAI-87: Sixth National Conference on
		 Artificial Intelligence},
address = 	{Seattle, Washington},
month = 	Jul,
year = 		1987,
pages = 	{290--294}
}

@phdthesis{Drescher89,
author = 	{Gary L. Drescher},
title = 	{Made-up Minds: A Constructivist Approach to Artificial
		Intelligence},
school = 	{MIT EECS Department},
year = 		1989,
month = 	Sep,
note = 	{(Reprinted by MIT Press.)}
}

@incollection{DruckerScSi92,
author =        {Drucker, Harris and Robert Schapire and Patrice Simard},
title =         {Improving Performance in Neural Networks Using a
                Boosting Algorithm},
booktitle =     {Advances in Neural Information Processing Systems},
publisher =     {Morgan Kaufmann},
year =          1992
}

@book{DudaHa73,
author = 	{Richard O. Duda and Peter E. Hart},
title = 	{Pattern Classification and Scene Analysis},
publisher = 	{Wiley},
year = 		{1973}
}

@article{Dudley78,
author=   	{Dudley, R. M.},
title=    	{Central Limit Theorems for Empirical Measures},
journal=  	{The Annals of Probability},
year=     	1978,
volume=   	6,
number=   	6,
pages=    	{899--929},
comment=  	{Generalization and proofs of Vapnik-Chervonenkis results.}
}

@techreport{DudleyKuRiZe92,
author = 	{Dudley, R. and S. Kulkarni and T. Richardson and
		O. Zeituni},
title = 	{A metric entropy bound is not sufficient for
		learnability},
institution = 	{MIT LIDS},
year = 		1992,
month = 	Oct,
number = 	{LIDS-P-2144}
}

@book{Edelman87,
author = 	{Gerald M. Edelman},
title = 	{Neural Darwinism -- The Theory of Neuronal Group Selection},
year = 		1987,
publisher = 	{Basic Books}
}

@article{EdmondsJo73,
author = 	{Jack Edmonds and Ellis L. Johnson},
title = 	{Matching, {E}uler Tours and the {C}hinese {P}ostman},
journal = 	{Mathematical Programming},
year = 		1973,
volume = 	5,
pages = 	{88-124},
comment = 	{Shows how to solve Chinese postman problem via matching.
		 Describes algorithms for finding Euler tours.}
}

@inproceedings{EhrenfeuchtHa88,
author=   	{Ehrenfeucht, Andrzej and David Haussler},
title=    	{Learning Decision Trees from Random Examples},
booktitle=	{Proceedings of the 1988 Workshop on Computational
		 Learning Theory},
address=	{Cambridge, MA},
month=    	Aug,
year=     	1988,
pages = 	{182--194}
}

@article{EhrenfeuchtHa89,
author=   	{Ehrenfeucht, Andrzej and David Haussler},
title=    	{Learning Decision Trees from Random Examples},
journal = 	{Information and Computation},
year = 		1989,
month=    	Sep,
volume = 	82,
number = 	3,
pages = 	{231--246}
}

@techreport{EhrenfeuchtHaKeVa87,
author = 	{A. Ehrenfeucht and D. Haussler and M. Kearns and L. Valiant},
title = 	{A General Lower Bound on the Number of Examples Needed
		 for Learning},
institution = 	{U.C. Santa Cruz Computer Science Department},
year = 		1987,
number = 	{UCSC-CRL-87-26}
}

@inproceedings{EhrenfeuchtHaKeVa88,
author = 	{A. Ehrenfeucht and D. Haussler and M. Kearns and L. Valiant},
title = 	{A General Lower Bound on the Number of Examples Needed
		 for Learning},
booktitle = 	{First Workshop on Computational Learning Theory},
year = 		{1988},
address = 	{Cambridge, Mass.\ },
month = 	aug,
pages = 	{139--154},
publisher = 	{Morgan Kaufmann}
}

@article{EhrenfeuchtHaKeVa89,
author = 	{Andrzej Ehrenfeucht and David Haussler and Michael Kearns 
		 and Leslie Valiant},
title = 	{A General Lower Bound on the Number of Examples Needed
		 for Learning},
journal = 	{Information and Computation},
year = 		1989,
month = 	Sep,
volume = 	82,
number = 	3,
pages = 	{247--251}
}

@mastersthesis{Eisenberg92,
author = 	{Bronwyn Bonnie Eisenberg},
title = 	{On the sample complexity of {PAC}-learning using
		random and chosen examples},
school = 	{MIT EECS Department},
year = 		1992,
note =		{(LCS Technical report MIT/LCS/TR-535, March 1992.)}
}

@inproceedings{EisenbergRi90,
author =	{Eisenberg, Bonnie and Ronald Rivest},
title = 	{On the Sample Complexity of {PAC}-Learning Using Random 
		 and Chosen Examples},
booktitle = 	{Proceedings of COLT '90},
publisher = 	{Morgan Kaufmann},
year = 		{1990},
pages = 	{154--162},
tag=		{TOC-display}
}

@article{Euler36,
author = 	{L. Euler},
title = 	{Solutio problematis ad geometriam situs pertinentis},
journal = 	{Commentarii Academiae Petropolitanae},
year = 		1736,
volume = 	8,
pages = 	{128--140},
comment = 	{Original reference for "Euler tours"}
}

@techreport{FahlmanLe90,
author=   	{Fahlman, Scott E. and Christian Lebiere},
title=    	{The Cascade-Correlation Learning Architecture},
institution= 	{Carnegie-Mellon Computer Science Department},
year=     	1990,
month=    	Feb,
number=   	{CMU-CS-90-100}
}

@inproceedings{FahlmanLe90a,
author = 	{Fahlman, Scott E. and Christian Lebiere},
title = 	{The Cascade-Correlation Learning Architecture},
booktitle = 	{Advances in Neural Information Processing Systems 2},
publisher = 	{Morgan Kaufmann},
year = 		{1990}
}

@article{FaragoLu93,
author =	{Farag\'{o}, Andr\'{a}s and G\'{a}bor Lugosi},
title = 	{Strong Universal Consistency of Neural Network Classifiers},
journal=	{IEEE Transactions on Information Theory},
year = 		1993,
month = 	Jul,
volume=		{IT-39},
number=		4,
pages=		{1146--1151}
}

@techreport{FarmerSi88,
author=	  	{Farmer, J. Doyne and John J. Sidorowich},
title=	  	{Exploiting Chaos to Predict the Future and Reduce Noise},
institution= 	{Los Alamos National Laboratory},
year=	  	1988,
month=	  	mar,
number=	  	{LA-UR-88-901}
}

@book{Feller68,
author=   	{Feller, William},
title=    	{An Introduction to Probability and its Applications},
publisher=	{John Wiley and Sons},
year=     	1968,
edition=  	{third},
volume=   	1
}

@book{Feller71,
author=   	{Feller, William},
title=    	{An Introduction to Probability and its Applications},
publisher=	{John Wiley and Sons},
year=     	1971,
edition=  	{second},
volume=   	2
}

@book{Feyerabend81,
author=   	{Feyerabend, P. K.},
title=    	{Philosophical Papers: Realism, Rationalism, \& 
           	Scientific Method},
publisher=	{Cambridge University Press},
year=     	1981,
volume=   	1
}

@inproceedings{FiatFo91,
author = 	{A. Fiat and D. P. Foster and H. Karloff and Y. Rabani
                and Y. Ravid and S. Vishwanathan},
title = 	{Competitive Algorithms for Layered Graph Traversal},
booktitle = 	{Proceedings of the 32nd Symposium on Foundations of
		 Computer Science},
publisher = 	{IEEE},
year = 		1991,
pages = 	{288-297}
}

@article{Fiedler72,
author=   	{Fiedler, Miroslav},
title=    	{Bounds for Eigenvalues of Doubly Stochastic Matrices},
journal=   	{Linear Algebra and its Applications},
year=      	1972,
month=     	Jul,
volume=    	5,
number=    	3,
pages=     	{299--310}
}

@article{Fienberg70,
author=   	{Fienberg, Stephen E.},
title=    	{An Iterative Procedure for Estimation in Contingency Tables},
journal=  	{Journal of Mathematical Statistics},
year=     	1970,
volume=   	41,
number=   	3,
pages=    	{907--917},
comment=  	{Proves convergence of Deming/Stephan iterative procedure for
	   	finding maximum entropy solution}
}


@article{FischerSi92,
author = 	{Paul Fischer and Hans Ulrich Simon},
title = 	{On Learning Ring-Sum-Expansions},
journal = 	{SIAM J. Computing},
year = 		{1992},
month = 	Feb,
volume = 	21,
number = 	1,
pages = 	{181--192}
}


@article{FischhoffBM83,
author=   	{Fischhoff, Baruch and Ruth Beyth-Marom},
title=    	{Hypothesis Evaluation from a Bayesian Perspective},
journal=  	{Psychological Review},
year=     	1983,
volume=   	90,
number=   	3,
pages=    	{239--260},
comment=  	{Taxonomy of ways people might deviate from Bayesianism.}
}


@article{FisherHo86,
author=  	{Fisher, M.L. and D.S.Hochbaum},
title=   	{Probabilistic Analysis of the Planar $K$-Median Problem},
journal= 	{Mathematics of Operations Research},
year=    	1980,
month=		Feb,
volume=  	5,
pages=   	{27--34}
}


@article{FlannaganFrHo86,
author=  	{Flannagan, Michael J. and Lisbeth S. Fried and Keith J. 
		Holyoak},
title=   	{Distributional Expectations and the Induction of Category 
		Structure},
journal= 	{Journal of Experimental Psychology: Learning, Memory, and 
		Cognition},
year=    	1986,
volume=  	12,
number=  	2,
pages=   	{241--256},
comment= 	{Experimental evidence in favor of idea that people expect 
		exemplars of a category to follow the normal distribution}
}

@inproceedings{Floyd89,
author=   	{Floyd, Sally},
title=    	{Space-bounded learning and the {V}apnik-{C}hervonenkis
		 Dimension},
booktitle=	{Proceedings of the Second Annual Workshop on Computational
		 Learning Theory},
address=	{Santa Cruz, CA},
month=    	Jul,
year=     	1989,
pages = 	{349--364}
}

@phdthesis{Floyd89b,
author=   	{Floyd, Sally},
title=    	{Space-bounded learning and the {V}apnik-{C}hervonenkis
		 Dimension},
school = 	{U.C. Berkeley},
year=     	1989,
month = 	Dec,
note = 		{ICSI Tech Report TR-89-061}
}


@article{Freeman92,
author=  	{Freeman, James A.},
title=   	{Neural Networks in Mathematica},
journal= 	{AI Expert: the Magazine of Aritificial Intelligence in Practice},
year=    	1992,
month =		Nov,
volume=  	7,
number=  	11,
pages=   	{26--35}
}



@inproceedings{Freund90,
author = 	{Yoav Freund},
title =		{Boosting a Weak Learning Algorithm by Majority},
booktitle = 	{Proceedings of the Third Annual Workshop on Computational
		Learning Theory},
publisher = 	{Morgan Kaufmann},
year = 		{1990},
pages = 	{202--216},
}

@inproceedings{Freund92,
author = 	{Yoav Freund},
title =		{An Improved Boosting Algorithm and Its Implications on
		Learning Complexity},
booktitle = 	{Proceedings of the Fifth Annual {ACM} Workshop on Computational
		Learning Theory},
publisher = 	{{ACM} Press},
year = 		{1992},
pages = 	{391--398},
}

@inproceedings{FreundKeRoRuScSe93,
author = 	{Yoav Freund and Michael Kearns and Dana Ron and 
		Ronitt Rubenfeld and Robert Schapire and Linda Sellie},
title = 	{Efficient Learning of Typical Finite Automata from 
		Random Walks},
booktitle = 	{Proceedings of the Twenty-Fifth Annual {ACM} Symposium on
		 Theory of Computing},
year = 		1993,
month = 	May,
pages = 	{315--324}
}


@article{FriedmanBeFi77,
author = 	{Jerome J. Friedman and Jon Louis Bentley and Raphael Ari Finkel},
title = 	{An Algorithm for Finding Best Matches in Logarithmic 
		 Expected Time},
journal = 	{ACM Transactions on Mathematical Software},
year = 		{1977},
month = 	Sep,
volume = 	3,
number = 	3,
pages = 	{209--226}
}

@article{FriedmanSt81,
author = 	{Friedman, Jerome H. and Werner Stuetzle},
title = 	{Projection Pursuit Regression},
journal = 	{J. American Statistical Association},
year = 		1981,
month = 	Dec,
volume =	76,
number = 	376,
pages = 	{817--823},
comment = 	{Good description of projection pursuit},
}

@article{Frobenius80,
author = 	{Frobenius},
title = 	{~},
journal = 	{Journ. f\"{u} Math.},
year = 		1880,
volume = 	89,
pages = 	{262}
}

@article{FuBo75a,
author=   	{Fu, King-Sun and Taylor L. Booth},
title=    	{Grammatical Inference: Introduction and Survey -- Part I},
journal= 	{IEEE Transactions on Systems, Man, and Cybernetics},
year=     	1975,
month=    	Jan,
volume=   	{SMC-5},
number=   	1,
pages=    	{95--111},
comment=  	{Inference of finite-state and context-free grammars reviewed.}
}

@article{FuBo75b,
author=   	{Fu, King-Sun and Taylor L. Booth},
title=    	{Grammatical Inference: Introduction and Survey -- Part II},
journal= 	{IEEE Transactions on Systems, Man, and Cybernetics},
year=     	1975,
month=    	Jul,
volume=   	{SMC-5},
number=   	4,
pages=    	{409--423},
comment=  	{Inference of stochastic finite-state and context-free 
		grammars.}
}

@techreport{FurstJaSm90,
author = 	{Merrick Furst and Jeffrey Jackson and Sean Smith},
title = 	{Learning {$AC^0$} Functions Sampled Under Mutually
		Independent Distributions},
institution = 	{Carnegie Mellon University School of Computer Science},
number =	{CMU-CS-90-183},
year = 		1990,
month = 	Oct
}

@inproceedings{FurstJaSm91,
author = 	{Merrick Furst and Jeffrey Jackson and Sean Smith},
title = 	{Improved Learning of {$AC^0$} Functions},
booktitle = 	{Proceedings of the Fourth Annual Workshop on
		Computational Learning Theory},
address = 	{Santa Cruz, California},
year = 		1991,
month = 	Aug,
pages = 	{317--325}
}

@article{Gaines79,
author=   	{Gaines, B.R.},
title=    	{Maryanski's Grammatical Inferencer},
journal=  	{IEEE Transactions on Computers},
year=     	1979,
month=    	Jan,
volume=   	{C-27},
number=   	1,
pages=    	{62--66},
comment=  	{Corrects some typographical errors in the Maryanski-Booth
		algorithm for inferring a probabilistic finite-state grammar
	  	from a given set of strings.}
}

@inproceedings{GalperinRi93,
author=   	{Galperin, Igal and Ronald L. Rivest},
title=    	{Scapegoat Trees},
booktitle = 	{Proceedings of SODA '93},
year = 		1993,
month=     	Jan,
pages =		{165-174}
}

@book{GareyJo79,
author=   	{Garey, M. and D. Johnson},
title=    	{Computers and Intractability: A Guide to the Theory of
	  	NP-Completeness},
publisher=	{W. H. Freeman},
year=     	1979,
address=  	{San Francisco}
}

@inproceedings{GamsLa87,
author=	   	{Gams, M. and N. Lavrac},
title=	   	{Review of Five Empirical Learning Systems Within a  
		Proposed Schemata},
booktitle= 	{Progress in Machine Learning--Proceedings of EWSL 87: 
	   	2nd European Working Session on Learning},
address=   	{Bled, Yogoslavia},
year=	   	1987,
editor=	   	{Bratko, I. and N. Lavrac},
month=	   	may,
pages=	   	{46--66}
}

@inproceedings{Geisser70,
author=   	{Geisser, Seymour},
title=    	{The Inferential Use of Predictive Distributions},
booktitle=  	{Foundations of Statistical Inference},
editor=   	{Godambe, V. P. and D. A. Sprott},
year=     	1970,
publisher=  	{Holt, Rinehart, and Winston},
comment=  	{Argues for deriving probability density of future observations
		(a predictive distribution) from prior observations.}
}

@article{George57,
author=   	{George, F. H.},
title=    	{Logical Networks and Probability},
journal=  	{Bulletin of Mathematical Biophysics},
year=     	1957,
volume=   	19,
pages=    	{187--199},
comment=  	{Extends McCulloch-Pitts networks with counters for 
		probabilities.}
}

@article{George59,
author=   	{George, F. H.},
title=    	{Inductive machines and the problem of learning},
journal=  	{Cybernetica},
year=     	1959,
volume=   	{II},
pages=    	{109--126},
comment=  	{Discussion of learning; machines which learn associations.}
}

@article{Geman84,
author = 	{Stuart Geman and Donald Geman},
title = 	{Stochastic Relaxation, Gibbs Distributions, and the
		 Bayesian Restoration of Images},
journal = 	{IEEE Transactions on Pattern Analysis and Machine 
		 Intelligence},
year = 		1984,
month = 	Nov,
volume = 	{PAMI-6},
number = 	6,
pages = 	{721--741},
comment = 	{Uses Markov random fields and edge models.}
}

@incollection{Geman86,
author=   	{Geman, Stuart},
title=    	{Stochastic Relaxation Methods for Image Restoration and
	   	Expert Systems},
booktitle=  	{Automated Image Analysis: Theory and Experiments},
editor=   	{D.B. Cooper and R.L.Launer and D.E. McClure},
publisher=  	{Academic Press},
year=     	1986,
comment=  	{Describes stochastic relaxation technique for maximum entropy
	   	computations and for image restoration.}
}

@incollection{GeorgeffWa84,
author=   	{Georgeff, M. P. and C. S. Wallace},
title=    	{A General Selection Criterion for Inductive Inference},
booktitle=	{ECAI 84: Advances in Artificial Intelligence},
publisher=	{Elsevier Science Publishers},
year=     	1984,
pages=    	{473--482}
}


@inproceedings{GibsonHeKarKatPa89,
author=   	{Gibson, G. and L. Hellerstein and R.M. Karp and R.H. Katz and 
		D.A. Patterson},
title=    	{Coding techniques for handling failures in large disk arrays},
booktitle= 	{Proceedings of the Third Annual Conference on Architectural
	   	Support for Programming Languages and Operating Systems (ASPLOS III)},
address=   	{},
year=      	1989,
note = 		{(To appear)}
}


@unpublished{GillmanSi91,
author=   	{Gillman, D. and M. Sipser},
title=    	{Colored Markov Chains},
note=		{Unpublished Manuscript},
year=     	1992
}

@book{Gittins89,
author = 	{J. C. Gittins},
title = 	{Multi-armed Bandit Allocation Indices},
year = 		1989,
publisher = 	{Wiley},
comment = 	{``the book'' on allocation indices for bandit problems}
}

@techreport{Goetsch86,
author=   	{Goetsch, Gordon J.},
title=    	{CONSENSUS: A Statistical Learning Procedure in a Connectionist
	  	Network},
institution= 	{Carnegie-Mellon Computer Science Department},
year=     	1986,
month=    	May,
number=   	{CMU-CS-86-131},
comment=  	{Layered network built out of communities of units, each with a
	  	supervisor.}
}

@article{Gold67,
author=   	{Gold, E. Mark},
title=    	{Language Identification in the Limit},
journal=  	InfCtrl,
year=     	1967,
volume=   	10,
pages=    	{447--474},
comment=  	{Classic paper, introducing computer science theory into 
		learning.}
}

@article{GoldbergHo88,
author = 	{D. E. Goldberg and J. H. Holland},
title = 	{Special Issue on Genetic Algorithms},
journal = 	{Machine Learning},
year = 		1988,
month = 	Oct,
volume = 	3,
number = 	{2/3},
publisher = 	{Kluwer Academic Publishers}
}

@book{Goldberg89,
author = 	{David E. Goldberg},
title = 	{Genetic Algorithms in Search, Optimization, and Machine 
		 Learning},
year = 		1989,
publisher = 	{Addison-Wesley}
}

@mastersthesis{Goldman87,
author = 	{Sally A. Goldman},
title = 	{Efficient Methods for Calculating Maximum Entropy Distributions},
school = 	{MIT EECS Department},
year = 		1987,
month = 	May
}

@phdthesis{Goldman90,
author = 	{Goldman, Sally},
title = 	{Learning Binary Relations, Total Orders, and Read-Once
		Formulas},
school = 	{MIT Dept.\ of Electrical Engineering and Computer Science},
month = 	Sep,
year = 		1990,
note = 		{(MIT Laboratory for Computer Science Technical Report
		  MIT/LCS/TR-483, July 1990)}
}


GoldmanMa92

@techreport{GoldmanSl91,
author=   	{Goldman, Sally and Sloan, Robert},
title=    	{The Difficulty of Random Attribute Noise},
institution= 	{Washington University Department of Computer Science},
year=     	1991,
month=    	Jun,
number=   	{WUCS-91-92}

}


@inproceedings{GoldmanKeSc90,
author=		{Goldman, Sally A. and Kearns, Michael J. and 
		Schapire, Robert E.},
title=		{Exact Identification of Circuits Using Fixed Points of 
		Amplification Functions},
booktitle= 	{Proceedings of the 31st Symposium on Foundations of
		 Computer Science},
publisher = 	{IEEE},
year = 		{1990},
month = 	Oct,
pages = 	{193--202},
tag=		{TOC-display}
}


@inproceedings{GoldmanKeSc90a,
author=		{Goldman, Sally A. and Kearns, Michael J. and 
		Schapire, Robert E.},
title=		{On the Sample Complexity of Weak Learning},
booktitle = 	{Proceedings of COLT '90},
publisher= 	{Morgan Kaufmann},
year = 		{1990},
pages = 	{217--231},
tag=		{TOC-display}
}

@inproceedings{GoldmanKe91,
author=		{Goldman, Sally A. and Kearns, Michael J.},
title=		{On the Complexity of teaching},
booktitle = 	{Proceedings of COLT '91},
publisher = 	{Morgan Kaufmann},
year = 		{1991},
pages =         {303--314}
}

@incollection{GoldmanRi88,
author = 	{Sally A. Goldman and Ronald L. Rivest},
title = 	{Making Maximum Entropy Computations Easier by Adding Extra Constraints
		 (Extended Abstract)},
booktitle = 	{Maximum--Entropy and Bayesian Methods in Science and Engineering},
volume = 	{2},
editor = 	{G. J. Erickson and C. R. Smith},
publisher = 	{Kluwer Academic Publishers},
year = 		1988,
pages = 	{323--340}
}
		 
@incollection{GoldmanRi88b,
author = 	{Sally A. Goldman and Ronald L. Rivest},
title =	 	{A Non--Iterative Maximum Entropy Algorithm},
booktitle = 	{Uncertainty in Artificial Intelligence},
volume = 	2,
editor = 	{J. F. Lemmer and L. N. Kanal},
publisher = 	{Elsevier Science Publishers B.V. North-Holland},
year = 		1988,
pages = 	{133--148}
}

@inproceedings{GoldmanRiSc89,
author=   	{Goldman, Sally and Ronald L. Rivest and  Robert E. Schapire},
title=    	{Learning Binary Relations and Total Orders},
booktitle=	{Proceeding of the 30th IEEE Symposium on the Foundations 
		of Computer Science},
publisher=   	{IEEE Computer Society Press},
address=  	{Research Triangle Park, NC},
month=    	Oct,
pages=    	{46--51},
year=     	1989,
tag=		{TOC-display}
}

@article{GoldmanRiSc93,
author=   	{Goldman, Sally and Ronald L. Rivest and  Robert E. Schapire},
title=    	{Learning Binary Relations and Total Orders},
journal=	{SIAM J. Computing},
volume = 	22,
number = 	5,
year = 		1993,
month = 	Oct,
pages = 	{1006--1034}
}

@techreport{GoldmanSl92,
author=   	{Goldman, Sally A. and Sloan, Robert H.},
title=    	{The Power of Self-Directed Learning},
institution=  	{Washington University in St. Louis},
year=     	1992,
month=    	Nov,
number=   	{WUCS-92-49},
}

@article{GoldreichGoMi86,
author=   	{Goldreich, Oded and Shafi Goldwasser and Silvio Micali},
title=    	{How to Construct Random Functions},
journal = 	{Journal of the ACM},
volume = 	33,
number = 	4,
year=     	1986,
month=    	Oct,
pages=    	{792--807}
}

@article{GoldszmidtMoPe93,
author=   	{Moises Goldszmidt and Paul Morris and Judea Pearl},
title=    	{A Maximum Entropy Approach to Nonmonotonic Reasoning},
journal=  	{IEEE Transactions on Pattern Analysis and Machine 
		Intelligence},
year=     	1993,
month=    	Mar,
volume=   	{15},
number=   	3,
pages=    	{220--232}
}

@article{Good59,
author=   	{Good, I. J.},
title=    	{Kinds of Probability},
journal=  	{Science},
year=     	1959,
month=    	Feb,
volume=   	129,
number=   	3347,
pages=    	{443--447}
}

@article{Good63,
author=   	{Good, I.J.},
title=    	{Maximum entropy for hypothesis formulation, especially for
	   	multidimensional contingency tables},
journal=  	{Annals of Mathematical Statistics},
year=     	1963,
volume=   	34,
pages=    	{911-934},
comment=  	{Uses maximum entropy to judge order of interactions, and the
	   	order of a Markov chain.}
}

@article{Good66,
author=   	{Good, I.J.},
title=    	{A Derivation of the Probabilistic Explication of Information},
journal=  	{Journal of the Royal Statistical Society (Series B)},
year=     	1966,
volume=   	28,
pages=    	{578--581},
comment=  	{Argues from an axiomatic framework that I(H:E|G), the 
		information concerning H provided by E given G, should be 
		log( P(H.E|G) / (P(H|G)P(E|G)) ) or some monotonic variation 
		of this.}
}

@inproceedings{Good70,
author=   	{Good, I. J.},
title=    	{The Probabilistic Explication of Information, Evidence, 
		Surprise, Causality, Explanation, and Utility},
booktitle= 	{Foundations of Statistical Inference},
year=     	1971,
publisher= 	{Holt, Reinhart, and Winston},
editor=    	{V. P. Godame and D. A. Sprott},
pages=    	{108--141}
}

@article{Gold72,
author=   	{Gold, E. Mark},
title=    	{System Identification via State Characterization},
journal=  	{Automatica},
volume=   	8,
year=     	1972,
pages=    	{621--636}
}


@article{Gold78,
author=   	{Gold, E. Mark},
title=    	{Complexity of Automaton Identification from Given Data},
journal=  	{Information and Control},
year=     	1978,
volume=   	37,
pages=    	{302--320},
comment=  	{Proves that finding an automaton of $n$ or fewer states 
		which agrees with a given list of input/output pairs.}
}

@article{GordonSh85,
author=   	{Gordon, Jean and Edward H. Shortliffe},
title=    	{A Method for Managing Evidential Reasoning in a Hierarchical
		Hypothesis Space},
journal=  	{Artificial Intelligence},
year=     	1985,
month=    	Jul,
volume=   	26,
number=   	3,
pages=    	{323--357},
comment=  	{Dempster-Shafer theory explained and generalized.}
}

@article{GormanSe88,
author = 	{R. Paul Gorman and Terrence J. Sejnowski},
title = 	{Analysis of Hidden Units in a Layered Network Trained
	         to Classify Sonar Targets},
journal = 	{Neural Networks},
volume = 	1,
year = 		1988,
pages = 	{75--89}
}

@book{GradshteynRy80,
author = 	{I. S. Gradshteyn and I. M. Ryzhik},
title = 	{Table of Integrals, Series, and Products},
publisher = 	{Academic Press},
year = 		1980
}

@book{Grenander81,
author=   	{Grenander, Ulf},
title=    	{Abstract Inference},
publisher=	{John WIley \& Sons, Inc.},
year=     	1981
}

@book{GrossmanMa64,
author = 	{Israel Grossman and Wilhelm Magnus},
title = 	{Groups and Their Graphs },
publisher = 	{Mathematical Association of America},
year = 		{1964},
volume = 	{14},
series = 	{New Mathematical Library},
address = 	{Washington},
comment = 	{A low level introduction to group theory via Cayley graphs}
}

@inproceedings{GyorgyiTi89,
author = 	{G. Gy\"orgi and N. Tishby},
title = 	{Statistical Theory of Learning a Rule},
booktitle = 	{Proceedings of the STATPHYS-17 Workshop on Neural Networks
		 and Spin Glasses},
year = 		1989,
editor = 	{W. K. Theumann and R. K\"oberle},
publisher = 	{World Scientific Publishing Co.},
address = 	{Singapore, Teaneck NJ, Hong Kong},
pages = 	{???}
}



@article{HagerupR90,
author=   	{Torben Hagerup and Christine R\"{u}b},
title=    	{A Guided Tour of Chernoff Bounds},
journal=  	{Information Processing Letters},
volume=   	33,
year=     	1990,
month=    	Feb,
pages=    	{305--308}
}


@inbook{Halmos73,
author = 	{Paul R. Halmos},
title = 	{How to Write Mathematics},
pages = 	{19--48},
publisher = 	{American Mathematical Society},
year = 		1973,
note = 		{In book entitled {\sl How to Write Mathematics}, by
		N.E. Steenrod, Paul R. Halmos, M.M. Schiffer, and
		J.A. Dieudonn\'e}
}

@book{Hamming80,
author =        {Hamming, Richard W.},
title =         {Coding and Information Theory},
publisher =     {Prentice-Hall},
year =          1980
}

@inproceedings{Hancock91,
author = 	{Hancock, Thomas},
title = 	{Learning {$2\mu$} {DNF} Formulas and
		$k\mu$ Decision Trees},
booktitle = 	{Proceedings of the Fourth Annual Workshop on
		Computational Learning Theory},
address = 	{Santa Cruz, California},
publisher = 	{Morgan Kaufmann},
year = 		1991,
month = 	Aug,
pages = 	{199--209}
}

@inproceedings{HancockMa91,
author = 	{Hancock, Thomas and Mansour, Yishay},
title = 	{Learning Monotone {$k\mu$} {DNF} Formulas on Product
		Distributions},
booktitle = 	{Proceedings of the Fourth Annual Workshop on
		Computational Learning Theory},
address = 	{Santa Cruz, California},
year = 		1991,
month = 	Aug,
pages = 	{179--183}
}

@book{HansonReRi93,
editor = 	{S. J. Hanson and W. Remmele and R. L. Rivest},
title = 	{Machine Learning: From Theory to Applications; 
		Cooperative Research at Siemens and MIT},
year = 		1993,
publisher = 	{Springer-Verlag},
series = 	{Lecture Notes in Computer Science, 661}
}

@book{Hardy49,
author = 	{G. H. Hardy},
title = 	{Divergent Series},
year = 		1949,
publisher = 	{Oxford at the Clarendon Press}
}

@book{HardyWr60,
author =  	{G. H. Hardy and E. M. Wright},
title=	  	{An Introduction to the Theory of Numbers},
edition=  	{4th},
year =    	1960,
publisher= 	{Oxford University Press}
}

@book{HartmanisSt66,
author=   	{Hartmanis, J.\ and R. E. Stearns},
title=    	{Algebraic Structure Theory of Sequential Machines},
publisher=	{Prentice-Hall},
year=     	1966
}

@techreport{Hart85,
author=   	{Hart, George W.},
title=    	{Prototype Nonintrusive Appliance Load Monitor},
institution=  	{MIT Energy Laboratory},
year=     	1985,
month=    	Sep,
number=   	{Progress Report \#2},
comment=  	{Finite-state automaton inference to determine appliances 
		present.}
}

@phdthesis{Hart87,
author=   	{Hart, George W.},
title=    	{Minimum Information Estimation of Structure},
school=   	{MIT Dept.\ of Electrical Engineering and Computer Science},
year=     	1987,
month=    	Apr,
note=     	{Appears as LIDS-TH-1664.},
comment=  	{Studies and applies Rissanen's MDLP.}
}

@inproceedings{Haussler86,
author=   	{Haussler, David},
title=    	{Quantifying the inductive bias in concept learning},
booktitle=  	{Proceedings  AAAI-86},
organization= 	{American Association for Artificial Intelligence},
year=     	1986,
month=		aug,
pages=		{485--489},
comment=  	{Defines bias=  Vapnik-Chervonenkis dimension. Algorithms for
		learning k-CNF, k-DNF. Many ideas for extensions, 
		generalizations.}
}

@inproceedings{Haussler87a,
author=   	{Haussler, David},
title=    	{Bias, Version Spaces and {Valiant's} Learning Framework},
booktitle=	{Proceedings of the Fourth International Workshop on
           	Machine Learning},
address=  	{University of California, Irvine},
year=     	1987,
month=    	Jun,
pages=	  	{324--336}
}

@techreport{Haussler87b,
author=   	{Haussler, David},
title=    	{Learning Conjunctive Concepts in Structural Domains},
institution= 	{Computer Research Laboratory, University of Santa Cruz},
year=     	1987,
month=    	Feb,
number=   	{UCSC-CRL-87-1}
}

@article{Haussler88,
author = 	{Haussler, David},
title = 	{Quantifying Inductive Bias: {AI} Learning Algorithms and
		 {V}aliant's Learning Framework},
journal = 	{Artificial Intelligence},
year = 		1988,
volume = 	36,
pages = 	{177--221}
}

@techreport{Haussler88b,
author=   	{Haussler, David},
title=    	{Space Efficient Learning Algorithms},
institution= 	{University of California Santa Cruz},
number=   	{UCSC-CRL-88-2},
year=     	1985,
month=    	Sep,
note=		{(revised March 1988)}
}

@techreport{Haussler89,
author = 	{Haussler, David},
title = 	{Generalizing the PAC Model for Neural Net and
		 Other Learning Applications},
institution= 	{University of California Santa Cruz},
number=   	{UCSC-CRL-89-30},
year=     	1989,
month=    	Sep
}

@inproceedings{Haussler89b,
author=   	{Haussler, David},
title=    	{Generalizing the PAC Model: Sample Size Bounds from Metric 
		Dimension-Based Uniform Convergence Results},
booktitle=	{Proceedings of the 30th Annual Symposium
		 on Foundations of Computer Science},
year=     	1989,
pages = 	{40--45}
}

@techreport{Haussler90,
author = 	{Haussler, David},
title = 	{Probably Approximately Correct Learning},
institution= 	{University of California Santa Cruz},
number=   	{UCSC-CRL-90-16},
year=     	1990,
month=    	May
}

@article{Haussler92,
author = 	{Haussler, David},
title = 	{Decision Theoretic Generalizations of the {PAC} Model
		for Neural Net and Other Learning Applications},
journal = 	{Information and Computation},
volume = 	100,
number = 	1,
month = 	Sep,
year = 		1992,
pages = 	{78--150}
}


@article{Haussler94,
author = 	{D. Haussler and N. Littlestone and M. K. Warmuth},
title = 	{Predicting $\{0,1\}$-Functions on Randomly Drawn Points},
journal = 	{Information and Computation},
volume = 	115,
number = 	2,
month = 	Dec,
year = 		1994,
pages = 	{248--292}
}


@inproceedings{HausslerKeLiWa88,
author=   	{Haussler, David and Michael Kearns and Nick Littlestone and
	   	Manfred K. Warmuth},
title=    	{Equivalence of Models for Polynomial Learnability},
booktitle=	{Proceedings of the 1988 Workshop on
		 Computational Learning Theory},
address=	{Cambridge, MA},
month=    	Aug,
year=     	1988,
publisher = 	{Morgan-Kaufmann},
pages = 	{42--55}
}

@article{HausslerKeLiWa91,
author=   	{Haussler, David and Michael Kearns and Nick Littlestone and
	   	Manfred K. Warmuth},
title=    	{Equivalence of Models for Polynomial Learnability},
journal = 	{Information and Computation},
year=     	1991,
volume=  	{95},
number=  	{2},
month=   	Dec,
pages=   	{129--161}
}

@unpublished{HausslerLiWa87,
author = 	{Haussler, David and Nick Littlestone and
	   	Manfred K. Warmuth},
title = 	{Expected mistake bounds for on-line learning algorithms},
month=		Apr,
year=		1987,
note=		{(Unpublished)}
}

@inproceedings{HausslerLiWa88,
author = 	{Haussler, David and Nick Littlestone and
	   	Manfred K. Warmuth},
title = 	{Predicting $\{0,1\}$-Functions on Randomly Drawn Points},
booktitle = 	{Proceedings of the Twenty-Ninth Annual Symposium
		 on Foundations of Computer Science},
year = 		{1988},
pages = 	{100--109},
address = 	{White Plains, NY}
}

@inproceedings{HausslerLiWa89,
author = 	{Haussler, David and Nick Littlestone and
	   	Manfred K. Warmuth},
title = 	{Predicting $\{0,1\}$-Functions on Randomly Drawn Points},
booktitle = 	{Proceedings of COLT 89},
publisher= 	{Morgan Kaufmann},
year = 		{1989},
pages = 	{280--296}
}

@techreport{HausslerLiWa90,
author = 	{Haussler, David and Nick Littlestone and
	   	Manfred K. Warmuth},
title = 	{Predicting $\{0,1\}$-Functions on Randomly Drawn Points},
institution = 	{U.C. Santa Cruz Computer Research Laboratory},
year = 		{1990},
month = 	Dec,
number = 	{UCSC-CRL-90-54}
}

@techreport{HausslerLo90,
author = 	{Haussler, D. and P.Long},
title = 	{A generalization of Sauer's Lemma},
institution = 	{U.C. Santa Cruz Computer Research Laboratory},
year = 		{1990},
month = 	Apr,
number = 	{UCSC-CRL-90-15}
}


@incollection{Hellerstein87,
author=   	{Hellerstein, Lisa},
title=    	{A Concurrent Prolog based region finding algorithm},
booktitle=  	{Concurrent Prolog: Collected Papers},
year=    	{1987},
volume=		{I},
publisher=  	{MIT Press},
pages=  	{291--317}
}


@unpublished{Hellerstein92,
author = 	{Hellerstein, Lisa},
title = 	{Functions that are read-once on a subset of their inputs},
year=		1992,
note=		{(To appear in Discrete Applied Mathematics)}
}

@unpublished{HellersteinGibKarKatPa89,
author=   	{L. Hellerstein and G. Gibson and R.M. Karp and R.H. Katz and 
		D.A. Patterson},
title = 	{Coding techniques for handling failures in large disk arrays},
note = 		{(Preliminary version appeared in ASPLOS III, 1989)}
}

@article{HellersteinKlWi90,
author=   	{Hellerstein, Lisa and Philip Klein and Robert Wilber},
title=    	{On the time-space complexity of reachability queries for
		preprocessed graphs},
journal=  	{Information Processing Letters},
volume=   	35,
year=     	1990,
pages=    	{261--267}
}


@article{HellersteinSaShTa87,
author = 	{Hellerstein, Lisa and Shmuel Safra and Ehud Shapiro 
		 and Stephen Taylor},
title = 	{Commutative One-Counter Languages Are Regular},
journal = 	{J. Parallel and Distributed Computing},
year = 		{1987},
volume = 	{4},
pages = 	{250--265}
}

@article{HellersteinSh85,
author = 	{Hellerstein, Lisa and Ehud Shapiro},
title = 	{Implementing parallel algorithms in Concurent Prolog:
		 The MAXFLOW experience},
journal = 	{Journal of Logic Programming},
year = 		{1985},
volume = 	{3},
pages = 	{157--184}
}

@article{Hellman77,
author=  	{Martin E. Hellman},
title=   	{An Extension of the Shannon Theory Approach to Cryptography},
journal= 	{IEEE Transactions on Information Theory},
volume=  	{IT-23},
number=  	{3},
month=   	May,
year=    	1977,
pages=   	{289--294}
}

@inproceedings{HelmboldLiLo92,
author = 	{Helbold, David P. and Nicholas LIttlestone and Philip M. Long},
title = 	{Apple Tasting and Nearly One-Sided Learning}, 
booktitle = 	{Proceedings of IEEE FOCS Conference},
publisher = 	{IEEE},
year = 		1992,
address = 	{St. Louis, Missouri},
month = 	Oct,
pages = 	{493--502}
}


@inproceedings{HelmboldLo91,
author = 	{Helmbold, David P. and Philip M. Long},
title = 	{Tracking Drifting Concepts Using Random Examples},
booktitle = 	{Proceedings of the Fourth Annual Workshop on Computational
		Learning Theory},
address = 	{Santa Cruz, California},
publisher = 	{Morgan Kaufmann},
year = 		1991,
pages = 	{13--23}
}

@inproceedings{HelmboldSlWa89,
author=   	{Helmbold, David and Robert Sloan and Manfred K. Warmuth},
title=    	{Learning Nested Differences of Intersection-Closed
		 Concept Classes},
booktitle=	{Proceedings of the Second Annual Workshop on Computational
		 Learning Theory},
address=	{Santa Cruz, CA},
month=    	Jul,
year=     	1989,
pages = 	{41--56}
}

@inproceedings{HelmboldSlWa90,
author=   	{Helmbold, David and Robert Sloan and Manfred K. Warmuth},
title=    	{Learning Integer Lattices},
booktitle = 	{Proceedings of COLT '90},
publisher= 	{Morgan Kaufmann},
year = 		{1990},
pages=          {288--302},
tag=		{TOC-display}
}

@article{HelmboldSlWa92,
author=   	{Helmbold, David and Robert Sloan and Manfred K. Warmuth},
title=    	{Learning Integer Lattices},
journal = 	{{SIAM} Journal on Computing},
year = 		{1992},
volume = 	{21},
number = 	{2},
pages = 	{240--266}
}

@book{Hennie68,
author=   	{Hennie, Frederick C.},
title=    	{Finite-State Models for Logical Machines},
publisher=	{John Wiley and Sons},
year=     	1968
}

@techreport{HintonSeAc84,
author=   	{Hinton, Geoffrey E. and Terrence J. Sejnowski and David H. 
		Ackley},
title=    	{Boltzmann Machines: Constraint Satisfaction Networks that 
		Learn},
institution= 	{CMU Computer Science Department},
number=   	{CMS-CS-84-119},
year=     	1984,
month=    	May,
comment=  	{Uses simulated annealing to update propositional states in
	  	a connectionist Hopfield-like neural network.}
}

@inproceedings{Hinton86,
author=   	{Hinton, Geoffrey E.},
title=    	{Learning Distributed Representations of Concepts},
booktitle= 	{Proceedings of the Eighth Annual Conference of the Cognitive
	   	Science Society},
address=   	{Amherst, Mass},
year=      	1986,
month=     	Aug,
pages=     	{???--???},
comment=   	{Uses a back-propagation learning procedure to learn relational
	   	data items.}
}

@article{Hoeffding63,
author = 	{Wassily Hoeffding},
title = 	{Probability inequalities for sums of bounded random  
		variables},
journal = 	{Journal of the American Statistical Association},
year = 		{1963},
volume = 	{58},
number = 	{301},
pages = 	{13--30},
month = 	mar
}

@book{Holland75,
author = 	{John H. Holland},
title = 	{Adaptation in Natural and Artificial Systems},
year = 		1975,
publisher = 	{The University of Michigan Press}
}


@article{Hong85,
author=    	{Hong, I.J.},
title=     	{An extension matrix approximate method for the general 
		 covering problem},
journal=   	{Int. Journal of Computer Information Science},
volume=    	14,
number=    	6,
pages=     	{421--437},
year=      	1985
}


@incollection{Hopcroft71,
author=    	{Hopcroft, John},
title=     	{An $n\log(n)$ Algorithm for Minimizing States in a Finite 
	   	Automaton},
booktitle= 	{Theory of Machines and Computations},
editor=    	{Zvi Kohavi and Azaria Paz},
publisher= 	{Academic Press},
year=      	1971,
pages=     	{189--196}
}

@book{HopcroftUl79,
author = 	{John Hopcroft and Jeffrey Ullman},
title = 	{Introduction to Automata Theory, Languages, and Computation},
publisher = 	{Addison-Wesley},
year = 		{1979},
address = 	{Reading, Mass.\ }
}

@article{Huber85,
author = 	{Peter J. Huber},
title = 	{Projection Pursuit},
journal = 	{Annals of Statistics},
year =		1985,
volume = 	13,
number = 	2,
pages = 	{435--475}
}

@article{HyafilRi76,
author=    	{Hyafil, Laurent and Ronald L. Rivest},
title=     	{Constructing Optimal Binary Decision Trees is {NP}-Complete},
journal=   	{Information Processing Letters},
year=      	1976,
month=     	May,
volume=    	5,
number=    	1,
pages=     	{15--17},
comment=   	{Proof based on exact-cover by 3-subsets.}
}

@article{IrelandKu68,
author=   	{Ireland, C.T. and S. Kullback},
title=    	{Contingency tables with given marginals},
journal=  	{Biometrika},
year=     	1968,
volume=   	55,
number=   	1,
pages=    	{179--188},
comment=  	{Proves geometric convergence of Deming/Stephan procedure for
	   	computing maximum entropy solution.}
}

@book{IsaacsonMa76,
author =        {Isaacson, Dean L. and Richard W. Madsen},
title =         {Markov Chains: Theory and Applications},
publisher =     {John Wiley \& Sons},
year =          1976
}

@article{ItoAmKo92,
author = 	{H. Ito and S.-I. Amari and K. Kobayashi},
title =	 	{Identifiability of Hidden {M}arkov Information Sources
		 and their Minimum Degrees of Freedom},
journal = 	{IEEE Trans. Information Theory},
year = 		1992,
month = 	Mar,
volume = 	{38},
number = 	2,
pages = 	{324--333}
}

@inproceedings{Jackson94,
author = 	{Jackson, Jeffrey},
title = 	{An Efficient Membership-Query Algorithm for Learning
		{DNF} with Respect to the Uniform Distribution},
booktitle = 	{Proceedings 35th Annual Symposium on Foundations of
		Computer Science},
publisher = 	{IEEE},
year = 		1994,
month = 	Nov,
address = 	{Santa Fe, New Mexico},
pages = 	{42--53}
}

@inproceedings{JacksonTo92,
author=   	{Jackson, Jeffrey and Tomkins, Andrew},
title=    	{A Computational Model of Teaching},
booktitle = 	{Proceedings of COLT '92},
publisher = 	{Morgan Kaufmann},
year = 		1992,
pages =         {319--326},
}

@techreport{JacobsJoBa90,
author=   	{Jacobs, Robert A. and Michael A. Jordan and Andrew G. Barto},
title=    	{Task decomposition through competition in a modular 
		connectionist architecture: The what and where vision tasks},
institution= 	{COINS},
number=   	{90-27},
year=     	1990,
month=    	Mar,
tag=		{TOC-display}
}

@book{Jacobson74,
author=		{Jacobson, Nathan},
title=		{Basic Algebra},
year=	  	1974,
volume=	  	1,
publisher= 	{W. H. Freeman and Company},
comment = 	{Classic abstract algebra text}
}

@inproceedings{Jantke84,
author=   	{Jantke, K. P.},
title=    	{Polynomial-time inference of general pattern languages},
booktitle=	{Proceedings of the Symposium of Theoretical Aspects of 
		Computer Science; Lecture Notes in Computer Science},
year=     	1984,
volume=   	166,
pages=    	{314-325},
publisher=	{Springer}
}

@article{Jaynes68,
author=   	{Jaynes, Edwin T.},
title=    	{Prior Probabilities},
journal=  	{IEEE Transactions on Systems Science and Cybernetics},
year=     	1968,
month=    	Sep,
volume=   	{SSC-4},
number=   	3,
pages=    	{227--241},
comment=  	{Presentation and justification for maximum-entropy procedure}
}

@article{Jaynes82,
author=   	{Jaynes, Edwin T.},
title=    	{On the Rationale of Maximum-Entropy Methods},
journal=  	{Proceedings of the IEEE},
volume=   	70,
number=  	9,
year=     	1982,
month=    	Sep,
pages=    	{939--952},
comment=  	{Justification for maximum-entropy methods, and comparison with
	   	full Bayesian and autoregressive models.}
}

@techreport{Jelinek83,
author=   	{Jelinek, Frederick},
title=    	{Markov Source Modeling of Text Generation},
institution=  	{IBM T.J. Watson Research Center},
year=     	1983,
comment=  	{Interpolates 1-, 2-, and 3-gram transistion probabilities.}
}

@article{Johnson79,
author=   	{Johnson, Rodney W.},
title=    	{Axiomatic Characterization of the Directed Divergences and 
		their Linear Combinations},
journal=  	{IEEE Transactions on Information Theory},
volume=   	{IT-25},
number=   	6,
year=     	1979,
month=    	Nov,
pages=    	{709--716},
comment=  	{Characterized by positivity, additivity, and finiteness.
	   	Directed divergence also called expected weight of evidence,
	   	cross-entropy, and discrimination information.}
}

@article{JohnsonSh83,
author=   	{Johnson, Rodney W. and John E. Shore},
title=    	{Comments on and Corrections to `Axiomatic Derivation of the
	   	Principle of Maximum Entropy and the Principle of Minimum
	   	Cross-Entropy},
journal=  	{IEEE Transactions on Information Theory},
year=     	1983,
month=    	Nov,
volume=   	{IT-29},
number=   	6,
pages=    	{942--943},
comment=  	{Corrects error in previous paper regarding discrete case.}
}


@unpublished{Jones90,
author = 	{Lee K. Jones},
title = 	{A Simple Lemma on Greedy Approximation in Hilbert Space
	 	 and Convergence Rates for Projection Pursuit Regression
		 and Neural Network Training},
year = 		1990,
note = 		{To appear in Annals of Statistics.}
}

@techreport{Jordan88,
author=   	{Jordan, Michael I.},
title=    	{Supervised learning and systems with excess degrees of 
		freedom},
institution=  	{COINS},
number=		{88-27},
year=     	1988,
month=		{May},
comments=	{Working paper},
tag=		{TOC-display}
}


@incollection{JordanRo88,
author=   	{Jordan, Michael I. and Rosenbaum, David A.},
title=    	{Action},
booktitle=  	{Handbook of Cognitive Science},
year=    	1988,
publisher=  	{MIT Press},
comment=  	{COINS Technical Report 88-26.},
tag=		{TOC-display}
}

@unpublished{Jordanru90,
author=		{Michael Joardan and David Rumelhart},
title=		{Forward models: Supervised learning with a distal teacher},
year=		1990,
month=		{Jul},
note=		{(Unpublished)},
tag=		{TOC-display}
}


@article{Juang84,
author=   	{Juang, B.-H.},
title=    	{On the Hidden Markov Model and Dynamic Time Warping for Speech
		Recognition -- A Unified View},
journal=  	{AT\&T Bell Laboratories Technical Journal},
year=     	1985,
month=    	Sep,
volume=   	63,
number=   	7,
pages=    	{1213--1242},
comment=  	{Gaussian autoregressive models; Markov models.  Baum's 
		forward-backward algorithm.  Computing all paths versus
		computing best path.}
}

@techreport{Judd87,
author=   	{Judd, J. Stephen},
title=    	{Complexity of Connectionist Learning with Various Node 
		Functions},
institution=	{Department of Computer and Information Science, 
	     	University of Massachusetts at Amherst},
month=     	Jul,
year=     	1987,
number=    	{87-60},
note=      	{Also presented at the First IEEE International Conference on 
		Neural Networks, June 21--24, 1987, San Diego, California}
}

@phdthesis{Judd88,
author=   	{Judd, J. Stephen},
title=    	{Neural Network Design and the Complexity of Learning},
school=   	{University of Massachussets at Amherst, Department of
	   	Computer and Information Science},
year=     	1988
}

@book{Judd90,
author = 	{Judd, J. Stephen},
title = 	{Neural Network Design and the Complexity of Learning},
publisher = 	{MIT Press},
year = 		1990
}


@inproceedings{KahnKaLi88,
author = 	{Kahn, J and G. Kalai and N. Linial},
title = 	{The influence of variables on boolean functions},
booktitle = 	{Proceedings of the Twenty-Ninth Annual Symposium
		 on Foundations of Computer Science},
year = 		{1988},
month =		Oct,
pages = 	{68--80},
address = 	{White Plains, NY}
}


@techreport{KahnLi88,
author = 	{Kahn, Jeff and Nathan Linial},
title = 	{Balancing Extensions via {Brunn-Minkowski}},
institution = 	{Rutgers Center for Operations Research},
year = 		1988,
month = 	Nov,
number = 	{RRR 57-88},
note = 		{To appear in {\em Combinatorica}},
comment = 	{Proves that in a partial order you can find two elements
		x,y such that 1/2e < Prob(x>y) < 1-1/2e.}
}

@book{Kanerva88,
author = 	{Pentti Kanerva},
title = 	{Sparse Distributed Memory},
year = 		1988,
publisher = 	{MIT Press},
comment = 	{Discusses nearest-neighbor techniques for learning.}
}

@inproceedings{KaoReTa93,
author=   	{Kao, Ming-Yang and Reif, John H. and Tate, Stephen R.},
title=    	{Searching in an Unknown Environment: An Optimal 
                 Randomized Algorithm for the Cow-Path Problem},
booktitle =     {Proceedings SODA 93},
year =          1993,
month =		Jan,
pages = 	{441--447}
}

@techreport{Kapur91,
author = 	{Kapur, Shyam},
title = 	{Balancing Extensions via {Brunn-Minkowski}},
institution = 	{Cornell University},
year = 		1991,
month = 	Sep,
number = 	{91-1234.}
}

@inproceedings{KearnsLiPiVa87,
author=   	{Kearns, Michael and Ming Li and Leonard Pitt and Leslie 
		Valiant},
title=    	{On the Learnability of Boolean Formulae},
booktitle=	{Proceedings of the Nineteenth Annual ACM Symposium on Theory
           	of Computing},
address=  	{New York, New York},
year=     	1987,
month=    	May,
pages=    	{285--295},
comment = 	{To appear in JACM.}
}

@inproceedings{KearnsLiPiVa87b,
author=   	{Kearns, Michael and Ming Li and Leonard Pitt and Leslie 
		Valiant},
title=    	{Recent Results on Boolean Concept Learning},
booktitle=	{Proceedings of the Fourth International Workshop on
           	Machine Learning},
address=  	{University of California, Irvine},
year=     	1987,
month=    	Jun,
pages=    	{337--352}
}

@inproceedings{KearnsLi88,
author=   	{Kearns, Michael and Ming Li},
title=    	{Learning in the Presence of Malicious Errors},
booktitle= 	{Proceedings of the Twentieth Annual ACM Symposium on Theory
           	of Computing},
address=  	{Chicago, Illinois},
year=     	1988,
month=    	May,
pages=		{267--280},
comment=  	{Studies pac learning in the presence of worst sort of errors.
		Submitted to SIAM J. Computing.}
}

@inproceedings{KearnsPi89,
author=   	{Kearns, Michael and Leonard Pitt},
title=    	{A Polynomial-time Algorithm for Learning $k$-variable
           	Pattern Languages from Examples},
booktitle= 	{Proceedings of the Second Annual Workshop on
            	Computational Learning Theory},
address=   	{Santa Cruz, California},
year=      	1989,
month=     	Jul,
pages=     	{57--71}
}


@inproceedings{KearnsSc90,
author=   	{Kearns, Michael J. and Robert E. Schapire},
title=    	{Efficient Distribution-free Learning of 
		Probablistic Concepts},
booktitle = 	{Proceedings of COLT '90},
publisher= 	{Morgan Kaufmann},
year = 		{1990},
pages=          {389},
note=		{Abstract only},
tag=		{TOC-display}
}

@inproceedings{KearnsSc90b,
author=   	{Kearns, Michael J. and Robert E. Schapire},
title=    	{Efficient Distribution-free Learning of 
		Probablistic Concepts},
booktitle = 	{Proceedings of the Thirty-First Annual Symposium on
		Foundations of Computer Science},
publisher = 	{IEEE},
year = 		{1990},
pages = 	{382--391},
volume = 	{I},
tag=		{TOC-display}
}


@inproceedings{KearnsSe93,
author=   	{Kearns, Michael J. and H. Sebastian Seung},
title=    	{Learning from a Population of Hypotheses},
booktitle = 	{Proceedings of COLT '93},
year = 		{1993},
pages=          {101--110},
}

@techreport{KearnsVa88,
author = 	{Michael Kearns and Leslie G. Valiant},
title = 	{Learning Boolean Formulae or Finite Automata is as
		 Hard as Factoring},
institution = 	{Harvard University Aiken Computation Laboratory},
year = 		1988,
number = 	{TR 14-88}
}

@inproceedings{KearnsVa89,
author = 	{Michael Kearns and Leslie G. Valiant},
title = 	{Cryptographic Limitations on Learning Boolean
                 Formulae and Finite Automata},
booktitle=      {Proceedings of the Twenty-First Annual ACM
                 Symposium on Theory of Computing},
address=        {Seattle, Washington},
month=          May,
year = 		1989,
pages = 	{433--444},
comment=	{To appear in JACM.}
}

@unpublished{KearnsVa92,
author = 	{Michael Kearns and Umesh Vazirani},
title = 	{Topics in Learning Theory},
year = 		1992,
note = 		{(Prelinary draft)}
}

@unpublished{Kearns88,
author=		{Michael Kearns},
title=		{Thoughts on Hypothesis Boosting},
year=		1988,
month=		Dec,
note=		{(Unpublished)}
}

@phdthesis{Kearns89,
author=   	{Michael Kearns},
title=    	{The Computational Complexity of Machine Learning},
school=   	{Harvard University Center for Research in Computing 
		Technology},
year=     	1989,
month=    	may,
note=     	{Technical Report TR-13-89. Also published by MIT Press as
		an ACM Distinguished Dissertation.}
}

@inproceedings{Kearns93,
author=		{Michael Kearns},
title=		{Efficient Noise-Tolerant Learning from Statistical Queries},
booktitle = 	{Proceedings of the Twenty-Fifth Annual {ACM} Symposium on
		Theory of Computing},
year = 		{1993},
pages = 	{392--401}
}

@techreport{KellyGl89,
author = 	{Kevin T. Kelly and Clark Glymour},
title = 	{Inductive Inference from Theory Laden Data},
institution = 	{CMU Laboratory for Computational Linguistics},
month = 	Oct,
year = 		1989,
number = 	{CMU-LCL-89-5}
}

@article{KesavanKa89,
author = 	{H. K. Kesavan and J. N. Kapur},
title = 	{The Generalized Maximum Entropy Principle},
journal = 	{IEEE Transactions on Systems, Man, and Cybernetics},
volume = 	19,
number = 	5,
year = 		1989,
month = 	{September/October},
pages = 	{1042--1052},
comment = 	{Generalizes to include a prior distribution, using 
		Kullback/Leibler Minimum Discrimination Information metric}
}

@article{Keshner82,
author = 	{Marvin S. Keshner},
title = 	{$1/f$ Noise},
journal = 	{Proceedings of the IEEE},
volume = 	70,
number = 	3,
year = 		1982,
month = 	Mar,
pages = 	{212--218},
comment = 	{Nice introduction and overview.}
}

@article{Khacian79,
title=    	{A Polynomial Algorithm for Linear Programming},
author=   	{Khacian, L. G.},
journal=  	{Soviet Math. Doklady},
volume=   	20,
pages=    	{191--194},
year=     	1979
}

@phdthesis{Kim83,
author=   	{Kim, Jin Hyung},
title=    	{CONVINCE: A Conversational Inference Consolidation Engine},
school=   	{University of California, Los Angeles},
year=     	1983,
comment=  	{Interactive decision support system using Pearl's Bayesian 
	   	networks}
}


@inproceedings{KimberLo92,
author=   	{Kimber, Don and Philip M. Long},
title=    	{The learning complexity of smooth functions of a single variable},
booktitle = 	{Proceedings of COLT '92},
month=    	Jul,
year=		1992,
pages = 	{153--159}
}

@inproceedings{Kleinberg94,
author = 	{Kleinberg, Jon M.},
title = 	{The localization problem for mobile robots},
booktitle = 	{Proceedings of the Thirty-Fifth Annual Symposium on
Foundations of Computer Science},
year = 		1994,
pages = 	{521--531},
month = 	May,
}

@book{Knuth68,
author=   	{Knuth, Donald E.},
title=    	{The Art of Computer Programming: Fundamental Algorithms},
publisher=	{Addison-Wesley},
year=     	1968,
volume=   	1
}

@book{Knuth73,
author=   	{Knuth, Donald E.},
title=    	{The Art of Computer Programming: Sorting and Searching},
publisher=	{Addison-Wesley},
year=     	1973,
volume=   	3
}

@techreport{KnuthLaRo88,
author = 	{Donald E. Knuth and Tracy Larrabee and Paul M. Roberts},
title = 	{Mathematical Writing},
institution = 	{Stanford University Computer Science Department},
month = 	Jan,
year = 		1988,
number = 	{STAN-CS-88-1193}
}

@article{KoHu87,
author=   	{Ko, K. and Hua, C.},
title=    	{A note on the two-variable pattern-finding problem},
journal=  	{Journal of Computer and System Science},
year=     	1987,
volume=   	34,
pages=    	{75--86}
}

@book{KodratoffMi90,
editor = 	{Yves Kodratoff and Ryszard S. Michalski},
title = 	{Machine Learning: An Artificial Intelligence Approach},
publisher = 	{Morgan Kaufmann},
year = 		1990,
address = 	{Los Altos, California},
volume = 	{III}
}

@book{Kohavi78,
author=   	{Kohavi, Zvi},
title=    	{Switching and Finite Automata Theory},
publisher=	{McGraw-Hill},
year=     	{1978},
edition=  	{second},
comment=  	{Chapter on State-Identification and Fault-Detection 
		Experiments}
}

@article{KohaviBe,
author=   	{Kohavi, Zvi and Benson, Scott},
title=		{Research Note On Decision Lists},
journal=  	{to appear in IPL},
year=     	1992
}


@article{Kolmogorov68,
author=   	{Kolmogorov, Andrei N.},
title=    	{Logical Basis for Information Theory and Probability Theory},
journal=  	{IEEE Transactions on Information Theory},
volume=   	{IT-14},
number=   	5,
year=     	1968,
month=    	Sep,
pages=    	{662--664},
comment=  	{Definition of `Kolmogorov' complexity; analogy to information-
	   	theoretic entropy; notion of random sequences}
}


@article{KuceraMaPr94,
author = 	{Ludek Kucera and Alberto Marchetti-Spaccamela and 
		 Marco Protasi},
title = 	{On Learning Monotone DNF Formulae under Uniform
		 Distributions},
journal = 	{Information and Computation},
volume = 	110,
number =	1,
month = 	Apr,
year = 		1994,
pages = 	{84--95}
}


@article{Kugel77,
author=   	{Kugel, Peter},
title=    	{Induction, Pure and Simple},
journal=  	{Information and Control},
volume=   	35,
year=     	1977,
pages=    	{276--336}
}

@inproceedings{KuhPeRi90,
title = 	{Learning Time-Varying Concepts},
author = 	{Anthony Kuh and Thomas Petsche and Ronald L. Rivest},
booktitle = 	{Advances in Neural Information Processing Systems 3},
publisher = 	{Morgan Kaufmann},
year = 		1991,
pages= 		{183--189}
}

@inproceedings{KuhPeRi91,
author = 	{Anthony Kuh and Thomas Petsche and Ronald L. Rivest},
title = 	{Incrementally Learning Time-Varying Half-planes},
booktitle = 	{Advances in Neural Information Processing Systems 4},
publisher = 	{Morgan Kaufmann},
year = 		1992,
pages= 		{920--927}
}

@phdthesis{Kulkarni91,
author = 	{S. R. Kulkarni},
title = 	{Problems of computational and information complexity
		in machine vision and learning},
school = 	{MIT EECS},
year = 		1991,
note = 		{(Also CICS report CICS-TH-298.)}
}

@article{Kullback68,
author=   	{Kullback, S.},
title=    	{Probability Densities with Given Marginals},
journal=  	{Annals of Mathematical Statistics},
year=     	1968,
volume=   	39,
number=   	4,
pages=    	{1236--1243},
comment=  	{Extension of Ireland/Kullback results to continuous 
		densities.}
}

@article{Kullback71,
author=   	{Kullback, S.},
title=    	{Marginal Homogeneity of Multidimensional Contingency Tables},
journal=  	{Annals of Mathematical Statistics},
year=     	1971,
volume=   	42,
number=   	2,
pages=    	{594--606},
comment=  	{Uses maximum entropy solution to derive minimum discrimination
	   	information statistic.}
}

@inproceedings{KushilevitzMa91,
author = 	{Eyal Kushilevitz and Yishay Mansour},
title = 	{Learning Decision Trees using the Fourier Spectrum},
booktitle = 	{Proceedings of the Twenty-Third Annual ACM Symposium
		on Theory of Computing},
year = 		1991,
month = 	May,
address = 	{New Orleans, Louisiana},
publisher = 	{ACM},
pages = 	{455--464}
}


@techreport{Kyburg85,
author=   	{Kyburg, Henry E. Jr},
title=    	{Bayesian and Non-Baysian Evidential Updating},
institution= 	{University of Rochester Computer Science Department},
year=     	{1985},
month=    	Jul,
number=   	{TR 139}
}



@article{Lai87,
author = 	{Tze Leung Lai},
title = 	{Adaptive Treatment Allocation and the Multi-armed Bandit
		 Problem},
journal = 	{Annals of Statistics},
year = 		1987,
volume = 	15,
number = 	3,
pages = 	{1091--1114}
}

@incollection{Lai88,
author = 	{T. L. Lai},
title = 	{Asymptotic Solutions of Bandit Problems},
booktitle = 	{Stochastic Differential Systems, Stochastic Control Theory
		 and Applications},
publisher = 	{Springer-Verlag},
year = 		1988,
editor = 	{W. Fleming and P. L. Lions},
comment = 	{survey paper}
}

@article{LaiRo84,
author = 	{T. L. Lai and Herbert Robbins},
title = 	{Optimal sequential sampling from two populations},
journal = 	{Proceedings National Academy Science USA},
volume = 	81,
year = 		1984,
month = 	Feb,
pages = 	{1284--1286}
}

@article{LaiRo85,
author = 	{T. L. Lai and Herbert Robbins},
title = 	{Asymptotically Efficient Adaptive Allocation Rules},
journal = 	{Advances in Applied Mathematics},
year = 		1985,
volume = 	6,
pages = 	{4--22},
comment = 	{asymptotically optimal result for bandit problems}
}

@article{LaiYi88,
author = 	{Tze Leung Lai and Zhiliang Ying},
title = 	{Open Bandit Processes and Optimal Scheduling of 
		 Queueing Networks},
journal =	{Advances in Applied Probability},
volume = 	20,
year = 		1988,
pages = 	{447--472}
}

@book{Laird88,
author = 	{Philip D. Laird},
title = 	{Learning from Good and Bad Data},
publisher = 	{Kluwer Academic Publishers},
year = 		{1988},
series = 	{Kluwer international series in engineering and computer 
		science},
address = 	{Boston},
comment = 	{His PhD thesis in book form}
}


@techreport{Laird88b,
author=  	{Laird, Philip},
title=   	{A survey of computational learning theory},
institution= 	{NASA Ames Research Center},
address =       {Moffett Field, California},
year=		1988
}

@techreport{LairdGa88,
author=  	{Laird, Philip and Evan Gamble},
title=   	{Learning a Probability Distribution Efficiently and Reliably},
institution= 	{NASA Ames Research Center},
month=  	oct,
year=		1988
}

@article{LairdNeRo87,
author = 	{Laird, J.E. and A. Newell and P.S. Rosenbloom},
title = 	{SOAR: An architecture for General Intelligence},
journal = 	{Artificial Intelligence},
year = 		1987,
month = 	Sep,
volume = 	33,
number = 	1,
pages = 	{1--64}
}

@inproceedings{LairdRoNe84,
author=		{Laird, John and Paul Rosenbloom and Allen Newell},
title=		{Towards Chunking as a General Learning Mechanism},
booktitle=	{Proceedings  AAAI-84},
orgainzation=	{American Association for Artificial Intelligence},
year=		1984,
month=		aug,
pages=		{188--192}
}

@article{LairdRoNe86,
author=		{Laird, John and Paul Rosenbloom and Allen Newell},
title=		{Chunking in {S}oar: the anatomy of a general learning 
		mechanism},
journal=	{Machine Learning},
volume=		1,
number=		1,
pages=		{11--46},
year=		1986
}

@phdthesis{Lathrop90,
author = 	{Richard H. Lathrop},
title = 	{Efficient Methods for Massively Parallel Symbolic Induction:
		 Algorithms and Implementation},
school = 	{MIT Department of Electrical Engineering and Computer 
		Science},
year = 		1990,
month = 	Jun
}

@article{LatteuxRo84,
author = 	{M. Latteux and G. Rozenberg},
title = 	{Commutative One-Counter Languages Are Regular},
journal = 	jcss,
year = 		{1984},
volume = 	{29},
number = 	{1},
pages = 	{54--57},
month = 	aug,
comment = 	{Gives a nice characteriztion of commutative regular languages}
}

@article{LauritzenSp88,
author=   	{S.L. Lauritzen and D.J. Spiegelhalter},
title=    	{Local Computations with Probabilities on Graphical Structures
		and their Application to Expert Systems},
journal=  	{Journal of the Royal Statistical Society (Series B)},
year=     	1988,
volume=   	50,
pages=    	{157--224}
}


@incollection{Lechner71,
author = 	{Robert J. Lechner},
title = 	{Harmonic Analysis of Switching Functions},
booktitle = 	{Recent Developments in Switching Theory},
chapter = 	{V},
pages = 	{121--228},
publisher = 	{Academic Press},
year = 		{1971}
}

@article{Lemmer83,
author=   	{Lemmer, John F.},
title=    	{Generalized Bayesian updating of incompletely specified
	   	distributions},
journal=  	{Large Scale Systems},
year=     	1983,
volume=   	5,
pages=    	{51--68},
comment=  	{Derives sufficient conditions for when marginals are 
		consistent with some underlying distribution.}
}

@techreport{Levin80,
author=   	{Levin, Leonid, A.},
title=    	{A Concept of Independence with Applications in Various Fields
		of Mathematics},
institution=	{MIT Laboratory for Computer Science},
year=     	1980,
month=    	Apr,
number=   	{MIT/LCS/TR-235}
}

@phdthesis{Lee88,
author=	  	{Lee, Kai-Fu},
title=	  	{Large-Vocabulary Speaker-Independent Continuous
	  	Speech Recognition: The SPHINX System},
school=	  	{Carnegie Mellon University Computer Science Dept.},
year=	  	1988,
month=	  	apr,
note=	  	{Tech report number CMU-CS-88-148}
}

@incollection{Lee89,
author=		{Lee, Kai-Fu},
title=		{Automatic Speech Recognition},
booktitle=	{1988/1989 Computer Science Research Review},
publisher=	{School of Computer Science, {C}arnegie {M}ellon {U}niversity},
year=		{1989},
pages=		{7--16}
}

@article{LeeEtAl90,
author = 	{Lee, Y.C. and S. Qian and R.D. Jones and C. W. Barnes and
		 G. W. Flake and M.K. O'Rourke and K. Lee and H. H. Chen
		 and G. Z. Sun and Y.Q. Zhang and D. Chen and C. L. Giles},
title = 	{Adaptive Stochastic Cellular Automata: Theory},
journal = 	{Phyisca D},
volume = 	666,
year = 		1990,
pages = 	{???--???},
comment = 	{Nice survey of convergence results for stochastic learning
		 automata.}
}

@article{LeeEtAl90b,
author = 	{Qian, S. and Y.C. Lee and R.D. Jones and C. W. Barnes and
		 G. W. Flake and M.K. O'Rourke and K. Lee and H. H. Chen
		 and G. Z. Sun and Y.Q. Zhang and D. Chen and C. L. Giles},
title = 	{Adaptive Stochastic Cellular Automata: Theory},
journal = 	{Phyisca D},
volume = 	666,
year = 		1990,
pages = 	{???--???},
comment = 	{Application of previous article to pole-balancing.}
}

@article{LeeMa88,
author=	  	{Kai-Fu Lee and Sanjoy Mahajan},
title=    	{A Pattern Classification Approach to Evaluation Function 
		Learning},
journal=  	{Artificial Intelligence},
year=     	1988,
month=    	Aug,
volume=   	36,
number=   	1,
pages=    	{1--26},
comment=  	{Learns Othello evaluation function based on four features and
           	multivariate normal distribution assumption.}
}


@article{LenstraLeLo82,
author = 	{A. K. Lenstra and H. W. Lenstra and L. Lov\'{a}sz},
title = 	{Factoring Polynomials with Rational Coefficients},
journal = 	{Mathematische Annalen},
year = 		{1982},
volume = 	{261},
pages = 	{515--534}
}


@phdthesis{Leung89,
author=	  	{Leung, Hong Chung},
title=	  	{The Use of Artificial Neural Networks for Phonetic Recognition},
school=	  	{MIT Dept.\ of Electrical Engineering and Computer Science},
year=	  	1989,
month=	  	may
}


@article{LevinsonRaSo83,
author=   	{S. E. Levinson and L. R. Rabiner and M. M. Sondhi},
title=    	{An Introduction to the Application of the Theory of 
		Probabilistic Functions
           	of a Markov Process to Automatic Speech Recognition},
journal=  	{Bell System Technical Journal},
year=     	1983,
month=    	Apr,
volume=   	62,
number=   	4,
pages=    	{1035--1074},
comment=  	{Analysis of implementation of Hidden Markov models and the 
		Baum-Welch algorithm}
}


@techreport{Lin90,
author = 	{Long-Ji Lin},
title = 	{Self-improving reactive agents: case studies of 
		 Reinforcement Learning Frameworks},
year = 		1990,
month = 	Aug,
number = 	{CMU-CS-90-109},
institution = 	{Carnegie Mellon Computer Science Department}
}


@inproceedings{LinVi92a,
author=   	{Jyh-Han Lin and Jeffrey Scott Vitter},
title=    	{$\epsilon$-Approximation with Minimum Packing Constraint Violation},
booktitle = 	{Proc.\ $24$th ACM Symposium on Theory of Computing},
month=    	May,
year=		1992,
pages = 	{771--782},
tag=		{TOC-display}
}


@inproceedings{LinVi92b,
author=   	{Jyh-Han Lin and Jeffrey Scott Vitter},
title=    	{A Theory for Memory-Based Learning},
booktitle = 	{Proceedings of COLT '92},
month=    	Jul,
year=		1992,
pages = 	{103--115},
tag=		{TOC-display}
}


@inproceedings{LinialMaNi89,
author =  	{Nathan Linial and Yishay Mansour and Noam Nisan},
title=		{Constant depth circuits, Fourier Transform, and 
		 Learnability},
booktitle = 	{Proceedings of the Thirtieth Annual Symposium
		 on Foundations of Computer Science},
address=	{Research Triangle Park, North Carolina},
month=    	Oct,
year=		1989,
pages = 	{574--579},
tag=		{TOC-display}
}


@inproceedings{LinialMaRi88,
author =  	{Nathan Linial and Yishay Mansour and Ronald L. Rivest},
title = 	{Results on Learnability and the {V}apnik-{C}hervonenkis
		Dimension}, 
booktitle = 	{Proceedings of the Twenth-Ninth Annual Symposium
		on Foundations of Computer Science},
year = 		1988,
month =		Oct,
pages = 	{120--129},
tag=		{TOC-display}
}

@inproceedings{LinialMaRi88b,
author =  	{Nathan Linial and Yishay Mansour and Ronald L. Rivest},
title = 	{Results on Learnability and the {V}apnik-{C}hervonenkis
		Dimension}, 
booktitle = 	{Proceedings of the 1988 Workshop on Computational 
		Learning Theory},
publisher = 	{Morgan-Kaufmann},
year = 		1988,
pages = 	{56--68},
tag=		{TOC-display}
}

@article{LinialMaRi91,
author =  	{Nathan Linial and Yishay Mansour and Ronald L. Rivest},
title = 	{Results on Learnability and the {V}apnik-{C}hervonenkis
		Dimension}, 
journal = 	{Information and Computation},
year = 		1991,
month = 	Jan,
volume = 	90,
number = 	1,
pages = 	{33--49},
tag=		{TOC-display}
}

@article{Lippmann87b,
author=   	{Lippmann, Richard P.},
title=    	{An Introduction to Computing with Neural Nets},
journal=  	{IEEE ASSP Magazine},
year=     	1987,
month=    	Apr,
pages=    	{4--22},
comment=  	{Good survey article}
}

bebebebe

@article{LippmannKuSi93,
author =  	{Lippmann, Richard P. and LInda Kukolich 
		and Elliot Singer},
title = 	{LNKnet: Neural Network, Machine-Learning, and 
		Statistical Software for Pattern Classification}, 
journal = 	{The Lincoln Laboratory Journal},
year = 		1993,
volume = 	6,
number = 	2,
pages = 	{249--268}
}


@inproceedings{Littlestone87,
author=   	{Littlestone, Nick},
title=    	{Learning When Irrelevant Attributes Abound},
booktitle=	{Proceedings of the Twenty-Eighth
           	Annual Symposium on Foundations of Computer Science},
year=     	1987,
month=    	Oct,
pages=    	{68--77}
}

@article{Littlestone88,
author=   	{Littlestone, Nick},
title=    	{Learning Quickly When Irrelevant Attributes Abound: 
		A New Linear-threshold Algorithm},
journal=  	{Machine Learning},
volume=   	2,
pages=    	{285--318},
year=     	1988
}

@phdthesis{Littlestone88b,
author = 	{Nick Littlestone},
title  = 	{Mistake bounds and logarithmic linear-threshold 
		learning algorithms},
school = 	{U. C. Santa Cruz},
year = 		{1989},
month = 	mar
}

@phdthesis{Littlestone89,
author = 	{Nick Littlestone},
title  = 	{Mistake bounds and logarithmic linear-threshold 
		learning algorithms},
school = 	{U. C. Santa Cruz},
year = 		{1989},
month = 	mar
}

@unpublished{Littlestone89p,
author = 	{Nick Littlestone},
title = 	{private communication},
note = 		{~},
year = 		{1989}
}



@inproceedings{LittlestoneLW,
author = 	{Nick Littlestone and Philip M. Long and Manfred K. Warmuth},
title = 	{On-line learning of linear functions},
booktitle = 	{Proceedings of the Twenty-third Annual ACM Symposium
		 on Theory of Computing},
publisher = 	{ACM},
address = 	{New Orleans, Louisiana},
year = 		1991,
month = 	May,
pages = 	{465--475},
}


@article{LittlestoneWa94,
author = 	{Nick Littlestone and Manfred K. Warmuth},
title = 	{The weighted majority algorithm},
journal = 	{Information and Computation},
volume = 	108,
year = 		1994,
number = 	2,
month = 	Feb,
pages = 	{212-261}
}


@unpublished{LittlestoneWa89,
author = 	{Manfred Warmuth and Nick Littlestone},
title = 	{Learning from an adversary},
note = 		{In preparation},
year = 		{1989}
}

@techreport{LittlestoneWa89b,
author = 	{Nick Littlestone and Manfred K. Warmuth},
title = 	{The Weighted Majority Algorithm},
year = 		1989,
month = 	Jul,
number = 	{UCSC-CRL-89-16},
institution = 	{Computer Research Laboratory, University of California
		at Santa Cruz}
}

@inproceedings{LittlestoneWa89c,
author = 	{Nick Littlestone and Manfred K. Warmuth},
title = 	{The Weighted Majority Algorithm},
booktitle = 	{Proceedings of IEEE FOCS Conference},
publisher = 	{IEEE},
year = 		1989,
month = 	Oct,
pages = 	{256--261},
note = 		{(Extended abstract only.)}
}

@article{LiVi92,
author = 	{Ming Li and Paul M. B. Vit\'{a}nyi},
title = 	{Inductive Reasoning and Kolmogorov Complexity},
journal = 	{JCSS},
volume = 	44,
year = 		1992,
pages = 	{343--384}
}

@book{Lovasz79,
author=		{L. Lov\'asz},
title=		{Combinatorial Problems and Exercises},
publisher=	{North-Holland Publishing Company},
year=		{1979}
}


@inproceedings{MaassTu90,
author = 	{Wolfgang Maass and Gy\"{o}gy Tur\'{a}n},
title = 	{On the complexity of learning from counterexamples and membership queries},
booktitle= 	{Proceedings of IEEE FOCS Conference},
publisher=      {IEEE},
year = 		1990,
month = 	Oct,
pages = 	{203--210},
}

@incollection{MaassTu92,
author = 	{Wolfgang Maass and Gy\"{o}gy Tur\'{a}n},
title = 	{How Fast Can a Threshold Gate Learn?},
booktitle= 	{Computational Learning Theory and Natural Learning Systems: Constraints and Prospects},
editor=         {Drastal and Hanson and Rivest},
publisher=      {MIT Press},
year = 		1992,
note = 		{(To appear.)}
}


@article{Maes90,
author=   	{Maes, Pattie},
title=    	{How to do the Right Thing},
journal=  	{Connection Science Journal, Special Issue on Hybrid Systems},
volume=   	1,
year=     	1990
}

@inproceedings{MaesBr90,
author=   	{Maes, Pattie and Brooks, Rodney A.},
title=    	{Learning to Coordinate Behaviors},
booktitle=	{Proceedings of AAAI-90},
publisher = 	{AAAI Press/The MIT Press},
address=	{Boston, MA},
month=    	Jul,
year=     	1990,
volume = 	2,
pages = 	{796--802},
tag=		{TOC-display}
}

@book{MagnusKaSo66,
author = 	{Wilhelm Magnus and Abraham Karrass and Donald Solitar},
title = 	{Combinatorial Group Theory:  Presentation of Groups in
		Terms of Generators and Relations},
publisher = 	{John Wiley \& Sons},
year = 		{1966},
address = 	{New York},
comment= 	{Discusses word problem and Cayley graph of a group}
}

@techreport{MahadevanCo90,
author = 	{Sridhar Mahadevan and Jonathan Connell},
title = 	{Automatic Programming of Behavior-Based Robots using
		Reinforcement Learning},
institution = 	{IBM Research at Yorktown Heights},
year = 		1990,
month = 	Dec
}


@article{MakhoulRoGi85,
author=   	{Makhoul, John and Salim Roucos and Herbert Gish},
title=    	{Vector Quantization in Speech Coding},
journal=  	{Proceedings of the IEEE},
volume=   	73,
number=   	11,
month=    	Nov,
year=     	1985,
pages=    	{1551--1588},
comment=  	{Excellent overview and introduction to vector 
		 quantization.}
}


@unpublished{Mansour90,
author=		{Mansour, Yishay},
title=		{Learning via Fourier Transform},
year=		1990,
month=		Apr,
note=		{(see KushilevitzMa91)},
tag=		{TOC-display}
}


@inproceedings{Mansour92,
author = 	{Mansour, Yishay92},
title = 	{An $o(n^{loglogn})$ learning algorithm for DNF under the
		uniform distribution},
booktitle = 	{Proceedings of the Fifth Annual Workshop on
		Computational Learning Theory},
year = 		1992,
month = 	Jul,
pages = 	{53--61}
}


@techreport{Marroquin85,
author=   	{Marroquin, Jose Luis},
title=    	{Probabilistic Solution of Inverse Problems},
institution=  	{MIT AI Laboratory},
year=     	1985,
month=    	Sep,
number=   	{AI-TR-860},
comment=  	{Vision problems, Markov Random Fields, simulation techniques 
		similar to simulated annealing used for Bayesian estimation.}
}

@article{Marron87,
author=   	{Marron, Assaf and Ker-I Ko},
title=    	{Identification of Pattern Languages from Examples and 
		Queries},
journal=  	{Information and Computation},
volume=   	74,
number=   	2,
year=     	1987,
month=    	Aug,
pages=    	{91--112}
}


@techreport{MaruyamaMi91,
author = 	{Osamu Maruyama and Satoru Miyano},
title = 	{Inferring a Tree from Walks},
institution = 	{Kyushu University},
year = 		1991,
month=		Dec,
number = 	{RIFIS-TR-CS-51}
}


@techreport{MaruyamaMi94,
author =       {Osamu Mruyama and Satoru Miyano},
title = 	{Graph Inference from a Walk for Trees of Bounded
		 Degree 3 is {NP}-Complete},
institution = 	{Kyushu University},
year = 		1994,
month=		Sep,
number = 	{RIFIS-TR-CS-94}
}


@article{MaschlerShPe72,
author=   	{Maschler, M.B. and B. Peleg and L.S. Shapley},
title=    	{The Kernel and Bargaining Set for Convex Games},
journal=  	{International Journal of Game Theory},
year=     	1972,
volume=   	1,
number=		2,
pages=    	{73--93}
}

@article{McCarthy56,
author=   	{McCarthy, John},
title=    	{Measures of the Value of Information},
journal=  	{Proceedings of the National Academy of Sciences},
year=     	1956,
volume=   	42,
pages=    	{654--655},
comment=  	{How to pay a weatherman to make honest predictions. 
		Generalizes rule that pays him log(Pi) if event predicted with 
		prob Pi happens.}
}

@inproceedings{McCarthy58,
author=   	{McCarthy, John},
title=    	{Programs with common sense},
booktitle=	{Proceedings of the Symposium on the Mechanization of Thought
           	Processes},
organization=	{National Physical Laboratory},
year=     	1958,
volume=   	1,
pages=    	{77-84},
note=     	{Reprinted in Minsky's (ed.) {\em Semantic Information 
		Processing}, MIT Press(1968), 403--409}
}

@book{McClellandRuPDP86,
author = 	{James L. McClelland and David E. Rumelhart and the
		PDP Research Group},
title = 	{Parallel Distributed Processing ---
		Explorations in the Microstructure of Cognition},
year = 		1986,
publisher = 	{MIT Press},
volume = 	2
}

@book{McClellandRu88,
editor=   	{McClelland, James L. and Rumelhart, David E.},
title=    	{Explorations in Parallel Distributed Processing: A Handbook
		of Models, Programs, and Exercises},
publisher=	{MIT Press},
year=     	1988,
comment=  	{Contains example of back-prop never converging on 1:1:1 
		network}
}

@book{McFarland87,
editor = 	{David {McFarland}},
title = 	{The Oxford Companion to Animal Behavior},
year = 		1987,
publisher = 	{Oxford University Press}
}

@techreport{Megiddo86,
author=   	{Megiddo, Nimrod},
title=    	{On The Complexity of Polyhedral Separability},
institution= 	{IBM Almaden Research Center},
year=     	1986,
month=    	Aug,
number=   	{RJ 5252}
}

@article{MegiddoVi88,
author=		{Megiddo, Nimrod and Uzi Vishkin},
title=		{On Finding a Minimum Dominating Set in a Tournament},
journal=	{Theoretical Computer Science},
year=		1988,
month=          Nov,
volume=		61,
number=		{2-3},
pages=		{307--316},
comment=  	{A problem that is equiv. to CNF with log**2 n variables}
}

@book{MichalskiCaMi83,
editor = 	{Ryszard S. Michalski and Jaime G. Carbonell and Tom M. Mitchell},
title = 	{Machine Learning: An Artificial Intelligence Approach},
publisher = 	{Morgan Kaufmann},
year = 		1983,
volume = 	{I},
address = 	{Los Altos, California}
}

@book{MichalskiCaMi86,
editor = 	{Ryszard S. Michalski and Jaime G. Carbonell and Tom M. Mitchell},
title = 	{Machine Learning: An Artificial Intelligence Approach},
publisher = 	{Morgan Kaufmann},
year = 		1986,
address = 	{Los Altos, California},
volume = 	{II}
}

@incollection{Michalski86,
author=   	{Michalski, Ryszard},
title=    	{Understanding the Nature of Learning: Issues and Research 
		Directions},
booktitle=	{Machine Learning, An Artificial Intelligence Approach 
		(Volume II)},
publisher=	{Morgan Kaufman},
year=     	1986,
pages=    	{3--25}
}

@article{Miller56,
author=		{Miller, G.},
title=		{The magic number seven, plus or minus two:  Some limits on
		our capacity for processing information},
journal=	{Psychology Review},
volume=		63,
year=		1956,
pages=		{81--97},
comment=	{The classic paper that says humans can hold 7 +/- 2 'chunks'
		in short term memory.}
}

@article{MillierGlKr87,
author = 	{W. Thomas Miller and Filson H. Glanz and L. Gordon Kraft},
title = 	{Application of a General Learning Algorithm to the Control
		of Robotic Manipulators},
journal = 	{International Journal of Robotics Research},
volume = 	6,
number = 	2,
year = 		1987,
month = 	{Summer},
pages = 	{84--98},
comment = 	{experimental study of CMAC variation}
}

@article{Minsky61,
author = 	{Marvin Minsky},
title = 	{Steps toward {Artificial} {Intelligence}},
journal =	{Proceedings of the Institute of Radio Engineers},
volume = 	49,
year = 		1961,
month = 	Jan,
pages = 	{8--30},
note = 		{(Reprinted in {\em Computers and Thought}, ed. by Feigenbaum
		and Feldman, (McGraw-Hill, 1963).)}
}

@book{MinskyPa69,
author = 	{Minsky, Marvin and Seymour Papert},
title = 	{Perceptrons: An Introduction to Computational Geometry},
publisher = 	{The MIT Press},
year = 		1969,
comment = 	{Classic analysis of the capabilities of the perceptron.}
}

@inproceedings{Mitchell77,
author=   	{Mitchell, Thomas M.},
title=    	{Version Spaces: A Candidate Elimination Approach to Rule 
		Learning},
booktitle=	{Proceedings IJCAI-77},
address=  	{Cambridge, Mass.},
year=     	1977,
month=    	Aug,
organization=	{International Joint Committee for Artificial Intelligence},
pages=    	{305--310}
}

@mastersthesis{Mohtashemi92,
author = 	{Mojdeh Mohtashemi},
title = 	{On Breaking A {H}uffman Code},
school = 	{MIT EECS Department},
year = 		1992,
note = 		{MIT Laboratory for Computer Science Technical Report
                 MIT/LCS/TR-617 (May 1992)}
}

@inproceedings{Moody89,
author = 	{Moody, John},
title = 	{Fast Learning in Multi-Resolution Hierarchies},
booktitle = 	{Advances in Neural Information Processing Systems I},
address = 	{San Mateo, California},
year = 		1989,
editor = 	{David S. Touretzky},
publisher = 	{Morgan Kaufmann},
pages = 	{29--39},
comment = 	{CMAC algorithm at multiple resolutions}
}

@inbook{Moore56,
author=		{Edward F. Moore},
title=		{Gedanken-Experiments on Sequential Machines},
pages=		{129--153},
booktitle=	{Automata Studies},
note=		{Edited by C. E. Shannon and J. McCarthy},
year=		1956,
publisher=	{Princeton University Press}
}

@techreport{MozerBa89,
author = 	{Mozer, Michael C. and Jonathan Bachrach},
title = 	{Discovering the Structure of a Reactive Environment
		 by Exploration},
institution = 	{University of Colorado Department of Computer Science},
month = 	Nov,
year = 		1989,
note = 		{Report CU-CS-451-89}
}

@article{NarendraTh74,
author=   	{Narendra, Kumpati S. and M. A. L. Thathachar},
title=    	{Learning Automata -- A Survey},
journal=  	{IEEE Transactions on Systems, Man, and Cybernetics},
year=     	1974,
volume=   	{SMC-4},
number=   	4,
pages=    	{323--334},
comment=  	{Stochastic automata that adapt behavior under reinforcement 
		schemes}
}

@book{NarendraTh89,
author = 	{Kumpati S. Narendra and Mandayam A. L. Thathachar},
title = 	{Learning Automata--An Introduction},
publisher = 	{Prentice-Hall},
year = 		1989
}

@inproceedings{Natarajan87,
author=   	{B. K. Natarajan},
title=    	{On Learning Boolean Functions},
booktitle=	{Proceedings of the Nineteenth Annual ACM Symposium on Theory
           	of Computing},
address=  	{New York, New York},
year=     	1987,
month=    	May,
pages=    	{296--304}
}

@inproceedings{Natarajan89,
author=   	{B. K. Natarajan},
title = 	{On Learning From Exercises},
booktitle = 	{Second Workshop on Computational Learning Theory},
address = 	{Santa Cruz, Cal.\ },
year = 		1989,
month=          Aug,
pages=          {72--87}
}

@article{Natarajan91,
author=   	{Natarajan, B.K.},
title=    	{Probably Approximate Learning of Sets and Functions},
journal=  	{SIAM J. Computing},
volume=   	20,
number =	2,
year=     	1991,
month =		Apr,
pages=    	{328--351}
}


@techreport{Neal92,
author=   	{Neal, Radford M.},
title=    	{Bayesian Training of Backpropagation Networks by the
		Hybrid Monte Carlo Method},
institution= 	{Department of Computer Science, U. of Toronto},
year=     	1992,
month=    	Apr,
number=   	{CRG-TR-92-1}
}


@inproceedings{Niblett87,
author=	   	{Niblett, T.},
title=	   	{Constructing Decision Trees in Noisy Domains},
booktitle= 	{Progress in Machine Learning--Proceedings of EWSL 87: 
	   	2nd European Working Session on Learning},
address=   	{Bled, Yugoslavia},
year=	   	1987,
editor=	   	{Bratko, I. and N. Lavrac},
month=	   	may,
pages=	   	{67--78}
}

@book{Nilsson90,
author = 	{Nils J. Nilsson},
title = 	{The Mathematical Foundations of Learning Machines},
year = 		1990,
publisher = 	{Morgan Kaufmann},
note = 		{(Republication of 1965 edition, with a new introduction by
		 T.J. Sejnowski and H. White.)}
}

@article{Omohundro87,
author=		{Omohundro, S.},
title=		{Efficient algorithms with neural networks behavior},
journal=	{Complex Systems},
year=		1987,
volume=		1,
pages=		{273--347}
}

@article{OshersonWe82,
author=   	{Osherson, Daniel N. and Scott Weinstein},
title=    	{Criteria of Language Learning},
journal=  	InfCtrl,
year=     	1982,
volume=   	52,
pages=    	{123--138},
comment=  	{Studies relationship between intensional/extensional 
		learning.},
tag=		{TOC-display}
}

@article{OshersonWe86,
author=   	{Osherson, Daniel N. and Scott Weinstein},
title=    	{Identification in the Limit of First Order Structures},
journal=  	{Journal of Philosophical Logic},
year=     	1986,
volume=   	15,
pages=    	{55--81},
tag=		{TOC-display}
}


@article{OshersonStWe84,
author=   	{Osherson, Daniel N. and Michael Stob and Scott Weinstein},
title=    	{Learning Theory and Natural Language},
journal=  	{Cognition},
year=     	1984,
volume=   	17,
pages=    	{1--28},
comment=  	{Presents argument that number of natural languages is 
		finite.},
tag=		{TOC-display}
}

@book{OshersonStWe86,
author=   	{Osherson, Daniel N. and Michael Stob and Scott Weinstein},
title=    	{Systems that Learn: An Introduction to Learning Theory
		for Cognitive and Computer Scientists},
publisher=  	{MIT Press},
year=     	1986,
comment=  	{Comprehensive recursion-theoretic treatment.}
}

@article{OshersonStWe88,
author=   	{Osherson, Daniel N. and Michael Stob and Scott Weinstein},
title=    	{Mathematical/Mechanical? Learners pay a price 
		for {B}ayesianism},
journal = 	{The Journal of Symbolic Logic},
year = 		1988,
volume = 	53,
number = 	4,
pages = 	{1245--1251},
tag=		{??}
}

@book{OsteyeeGo74,
author=   	{Osteyee, David Bridston},
title=    	{Information, Weight of Evidence, the Singularity between 
		Probability Measures and Signal Detection},
year=     	1974,
publisher= 	{Springer-Verlag},
series=    	{Lecture Notes in Mathematics},
number=    	376,
comment=  	{Text.}
}


@book{Owen82,
author = 	{Owen, Guillermo},
title = 	{Game Theory},
publisher = 	{Academic Press},
year = 		1982
}

@book{Palay85,
author=   	{Palay, Andrew J.},
title=    	{Searching with Probabilities},
year=     	1985,
publisher= 	{Pitman},
comment=  	{Integration of probabilities into B* algorithm (Ph.D. thesis
	  	with Hans Berliner).}
}

@techreport{Paturi88,
author=   	{Paturi, Ramamohan},
title=    	{The Light Bulb Problem},
institution= 	{Computer Science and Engineering},
address=  	{University of California, San Diego},
month=	  	aug,
year=     	1988
}

@article{PaoCa78,
author=   	{Pao, T. W. and J. W. {Carr III}},
title=    	{A solution of the syntactical induction-inference problem 
		for regular languages},
journal=  	{Computat. Lang.},
volume=   	3,
year=     	1978,
pages=    	{53--64}
}



@article{Papadimitriou76,
author=   	{Papadimitriou, Christos H.},
title=    	{On the complexity of edge traversing},
journal=  	{J. Assoc. Comp. Mach.},
year = 		{1976},
volume = 	23,
pages = 	{544--554}
}



@article{Papadimitriou81,
author=   	{Papadimitriou, Christos H.},
title=    	{Worst-Case and Probabilistic Analysis of a Geometric Location 
		Problem},
journal=  	{SIAM J. Computing},
year = 		{1981},
month = 	Aug,
volume = 	10,
number = 	3,
pages = 	{542--557}
}


@techreport{PapadimitriouTs85,
author=   	{Papadimitriou, Christos H. and John N. Tsitsiklis},
title=    	{The Complexity of Markov Decision Processes},
year=     	1985,
institution=  	{MIT Laboratory for Information and Decision Sciences},
number=   	{LIDS-P-1479},
comment=  	{Ordinary versions are complete for P; partially observed 
		are PSPACE-complete.}
}

@article{PapadimitriouYa91,
author=   	{Papadimitriou, Christos H. and Mihalis Yanakakis},
title=    	{Shortest paths without a map},
journal=  	{Theoretical Computer Science},
volume=   	84,
year=     	1991,
pages=    	{127--150}
}


@article{PaskVF60,
author=   	{Pask, Gordon and Heinz Von Foerster},
title=    	{A predictive model for self organizing systems, Parts I and 
		II},
journal=  	{Cybernetica},
year=     	{1960 and 1961},
volume=   	{III and IV},
pages=    	{258--300 and 20--55},
comment=  	{n-person game theory. Learning automata.}
}

@article{Pearl78,
author=   	{Pearl, Judea},
title=    	{On the Connection Between the Complexity and Credibility of 
		Inferred Models},
journal=  	{Journal of General Systems},
year=     	1978,
volume=   	4,
pages=    	{255--264},
comment=  	{Studies tradeoff between uniqueness and ambiguity in the 
		selection of hypotheses.
           	Introduces the use of the Vapnik-Chervonenkis dimension.}
}

@article{Pearl79,
author=   	{Pearl, Judea},
title=    	{Capacity and Error Estimates for Boolean Classifiers with 
		Limited Complexity},
journal=  	{IEEE Transactions on Pattern Analysis and Machine 
		Intelligence},
year=     	1979,
month=    	Oct,
volume=   	{PAMI-1},
number=   	4,
pages=    	{350--355},
comment=  	{An extension of [Pe78].}
}

@unpublished{Pearl84,
author=   	{Pearl, Judea},
title=    	{Jeffrey's Rule and the Problem of Autonomous Inference 
		Agents},
year=     	1984,
note=     	{Class notes for 274A, Fall 1984},
comment=  	{Stresses dangers of using posterior probabilities as new prior
	   	probabilities.}
}

@techreport{Pearl85a,
author=   	{Pearl, Judea},
title=    	{Bayesian Networks: A Model of Self-Activated Memory for 
	   	Evidential Reasoning},
institution= 	{UCLA Computer Science Department},
year=     	1985,
month=    	Jun,
number=   	{CSD-850021, R-43},
comment=  	{Describes Bayesian networks and propagation in 
		singly-connected networks.}
}


@techreport{Pearl85b,
author=   	{Pearl, Judea},
title=    	{How to do with Probabilities What People Say You Can't},
institution= 	{UCLA Computer Science Department},
year=     	1985,
month=    	Sep,
number=   	{CSD-850031, R-49},
comment=  	{Describes Bayesian networks and propagation of beliefs.}
}

@techreport{Pearl85c,
author=   	{Pearl, Judea},
title=    	{Bayes Decision Methods},
institution= 	{UCLA Computer Science Department},
year=     	1985,
month=    	Jun,
number=   	{CSD-850023}
}


@techreport{Pearl85d,
author=   	{Pearl, Judea},
title=    	{How To Do With Probabilities What People Say You Can't},
institution= 	{UCLA Computer Science Department},
year=     	1985,
month=    	Sep,
number=   	{CSD-850031}
}

@techreport{Pearl85e,
author=   	{Pearl, Judea},
title=    	{On Evidential Reasoning In A Hierarchy Of Hypothesis},
institution= 	{UCLA Computer Science Department},
year=     	1985,
month=    	Sep,
number=   	{CSD-850032}
}


@techreport{PearlPa85,
author=   	{Pearl, Judea and Azaria Paz},
title=    	{GRAPHOIDS: A Graph-Based Logic for Reasoning about Relevance
	  	Relations, or When would x tell you more about y if you already
	  	know z},
institution= 	{UCLA Computer Science Department},
year=     	1985,
month=    	Dec,
comment=  	{Axiomatic definition of graphoids.}
}

@inproceedings{PearlPa86,
author=   	{Pearl, Judea and Azaria Paz},
title=    	{On the Logic of Representing Dependencies by Graphs},
booktitle=  	{Proceedings 1986 Canadian AI Conference},
year=     	1986,
month=    	May,
comment=  	{Defines and studies graphoids for representing dependencies}
}


@techreport{PearlVe90,
author=   	{Pearl, Judea and T.S. Verma},
title=    	{A Formal Theory of Inductive Causation},
institution= 	{UCLA Cognitive Systems Laboratory},
number=   	{R-1555 (I)},
year=     	1990,
month=    	Oct
}

@article{PeeblesSi90,
author = 	{P. J. E. Peebles and Joseph Silk},
title = 	{A cosmic book of phenonmena},
journal = 	{Nature},
volume = 	346,
month = 	Jul,
year = 		1990,
pages = 	{233--239},
comment = 	{Careful comparison of various theories about the universe
		with a variety of experimental data.
		Date is July 19, 1990.}
}

@mastersthesis{Perugini89,
author = 	{Nancy Perugini},
title = 	{Neural Network Learning: Effects of Network and Training
		 Set Size},
school =       	{MIT Department of Electrical Engineering and Computer 
		 Science},
month = 	Jun,
year = 		1989
}

@techreport{PinkerPi87,
author=   	{Steven Pinker and Alan Prince},
title=    	{On Language and Connectionism:
           	Analysis of a Parallel Distributed Processing Model
           	of Language Acquisition},
institution=	{MIT Center for Cognitive Science},
year=      	1987,
number=    	{Occasional Paper \#33},
comment=  	{Critique of Rumelhart and McClelland's connectionist approach 
		to learning English past tense construction.}
}

@techreport{Pitt85,
author=   	{Pitt, Leonard Brian},
title=    	{Probabilistic Inductive Inference},
institution= 	{Yale University Computer Science Department},
year=     	1985,
month=    	Jun,
number=   	{YALEU/DCS/TR-400},
comment=  	{Ph.D. thesis. Defines probabilistic inference and shows 
		probabilistic inference equivalence to teams of inductive 
		inference machines; and shows strict hierarchy on probability 
		with cut-points 1/2, 1/3, 1/4, ...}
}

@techreport{PittSm86,
author=   	{Pitt, Leonard and Carl H. Smith},
title=    	{Probability and Plurality for Aggregations of Learning 
		Machines},
institution= 	{University of Maryland Computer Science Department},
year=     	1986,
month=    	Jul,
number=   	{CS-TR-1686},
comment=  	{Show that one can not always trade off probabilism for 
		plurality and vice-versa.}
}

@techreport{PittVa86,
author=   	{Pitt, Leonard and Leslie G. Valiant},
title=    	{Computational Limitations on Learning from Examples},
institution= 	{Harvard University Aiken Computation Laboratory},
year=     	1986,
month=    	Jul,
comment=  	{It is NP-Complete to learn disjunction of two monomials, 
		Boolean threshold functions, Boolean formulae where each 
		variable occurs at most once.}
}

@article{PittVa88,
author=   	{Pitt, Leonard and Leslie G. Valiant},
title=    	{Computational Limitations on Learning from Examples},
journal = 	jacm,
volume =  	35,
number =  	4,
year = 	  	1988,
pages =   	{965--984}
}

@inproceedings{PittWa88,
author=   	{Pitt, Leonard and Manfred K. Warmuth},
title=    	{The Minimum {DFA} Consistency Problem Cannot be
           	Approximated within any Polynomial},
booktitle = 	{Proc.\ $21$th ACM Symposium on Theory of Computing},
publisher = 	{ACM},
address = 	{Seattle},
year = 		1989,
month = 	May,
pages = 	{421--432}
}

@inproceedings{PittWa88b,
author=   	{Pitt, Leonard and Manfred K. Warmuth},
title = 	{Reductions Among Prediction Problems:  On the Difficulty of
		Predicting Automata (extended abstract)},
booktitle = 	{3rd IEEE Conference on Structure in Commplexity Theory},
year = 		{1988},
pages = 	{60--69},
address = 	{Washington, DC},
month = 	Jun
}

@techreport{PittWa88c,
author=		{Pitt, Leonard and Manfred K. Warmuth},
title=		{Prediction Preserving Reducibility},
institution=	{U. C. Santa Cruz Computer Research Laboratory},
year=		1988,
month=		Nov,
number=		{UCSC-CRL-88-26}
}

@inproceedings{PittWa89,
author=   	{Pitt, Leonard and Manfred K. Warmuth},
title=    	{The Minimum {DFA} Consistency Problem Cannot be
           	Approximated within any Polynomial},
booktitle=      {Proceedings of the Twenty-First Annual ACM
                 Symposium on Theory of Computing},
address=        {Seattle, Washington},
month=          May,
year = 		1989
}

@article{PittWa90,
author=		{Pitt, Leonard and Manfred K. Warmuth},
title=		{Prediction Preserving Reducibility},
journal = 	{Journal of Computer and System Sciences},
volume = 	41,
year = 		1990,
pages = 	{430--467}
}


@article{PittWa93,
author=   	{Pitt, Leonard and Manfred K. Warmuth},
title=    	{The Minimum Consistent DFA  Problem Cannot be
		Approximated within any Polynomial},
journal = 	{Journal of the ACM},
volume = 	40,
number = 	1,
year=     	1993,
month=    	Jan,
pages=    	{95--142}
}
	

@misc{Pitt90,
author =       	{Pitt, Leonard},
title =		{Recent Results in Computational Learning Theory},
year =     	1990
}

@techreport{PoggioGi89a,
author = 	{Poggio, Tomaso and Federico Girosi},
title = 	{A Theory of Networks for Approximation and Learning},
institution = 	{MIT Artificial Intelligence Laboratory},
year = 		1989,
month = 	{Jul},
number = 	{AIM1140},
tag=		{TOC-display}
}


@techreport{PoggioGi89b,
author = 	{Poggio, Tomaso and Federico Girosi},
title = 	{Networks and the Best Approximation Property},
institution = 	{MIT Artificial Intelligence Laboratory},
year = 		1989,
month = 	{Oct},
number = 	{AIM1164},
tag=		{TOC-display}
}


@article{PoggioGi89c,
author = 	{Poggio, Tomaso and Federico Girosi},
title =		{Representation Propoerties of Networks: Kolmogorov's 
		 Theorm Is Irrelevant},
journal =	{Neural Computation},
volume =	1,
year = 		1989,
pages = 	{465--469},
tag=		{TOC-display}
}


@techreport{PoggioGi90a,
author = 	{Poggio, Tomaso and Federico Girosi},
title = 	{Extensions of a Theory of Networks for Approximation and
		 Learning: dimensionality and reduction and clustering},
institution = 	{MIT Artificial Intelligence Laboratory},
year = 		1990,
month = 	{April},
number = 	{AIM1167},
tag=		{TOC-display}
}



@article{PoggioGi90b,
author = 	{Poggio, Tomaso and Federico Girosi},
title =		{Regularization Algorithms for Learning That Are 
		 Equivalent to Multilayer Networks},
journal = 	{Science},
volume = 	247,
year = 		1990,
month = 	{Feb 23},
pages = 	{978--982},
tag=		{TOC-display}
}


@book{Pollard84,
author = 	{David Pollard},
title = 	{Convergence of Stochastic Processes},
publisher = 	{Springer-Verlag},
year = 		1984
}

@techreport{Porat87,
author=   	{Sara Porat},
title=    	{Stability and Looping in Connectionist Models with 
		Assymmetric Weights},
institution= 	{University of Rochester Computer Science Department},
year=     	{1987},
month=    	Mar,
number=   	{TR 210},
comment=  	{Show that determining whether a network stabilizes is 
		NP-hard, under both synchronous and fair asynchronous updating
		rules.}
}

@inproceedings{Powell87,
author = 	{M.J.D. Powell},
title = 	{Radial Basis Functions for Multivariable Interpolation:
		A Review},
booktitle = 	{Algorithms for Approximation},
editor = 	{J.C. Mason and M. G. Cox},
year = 		1987,
publisher = 	{Clarendon Press},
address = 	{Oxford},
pages = 	{143--167},
comment = 	{Studies carefully conditions for nonsingularity of
		matrix needed for interpolation}
}

@article{Quinlan83,
author=   	{Quinlan, J. R.},
title=    	{Inferno: A Cautious Approach to Uncertain Inference},
journal=  	{The Computer Journal},
year=     	1983,
volume=   	26,
number=   	3,
pages=    	{255--269},
comment=  	{Survey of previous inference schemes. Proposes `cautious' 
		scheme.}
}

@article{Quinlan86,
author=   	{Quinlan, J. R.},
title=    	{Induction of Decision Trees},
journal=  	{Machine Learning},
year=     	1986,
volume=   	1,
pages=    	{81--106},
comment=  	{Overview of the induction of decision trees.  Proposes 
		information-theoretic measure for choosing decision 
		attributes.  Discusses issue of noise and unknown attribute 
		values.}
}

@article{Quinlan86b,
author=   	{Quinlan, J. R.},
title=    	{Simplifying Decision Trees},
journal=  	{International Journal of Man-Machine Studies},
year=     	1987,
note=     	{(To appear.)}
}

@incollection{Quinlan86c,
author = 	{J. Ross Quinlan},
title = 	{The Effect of Noise on Concept Learning},
booktitle = 	{Machine Learning, An Artificial Intelligence Approach
		(Volume II)},
publisher = 	{Morgan Kaufmann},
year = 		{1986},
chapter = 	{6},
pages = 	{149--166},
comment = 	{An empirical study of the effects of noise on a
		particular learning algorithm.  Concludes that classification 
		noise is more harmful than attribute noise.}
}

@article{QuinlanRi89,
author =  	{Quinlan, J. Ross and Ronald L. Rivest},
title =   	{Inferring Decision Trees Using the {M}inimum {D}escription {L}ength
		 {P}rinciple},
journal = 	{Information and Computation},
volume = 	80,
number = 	3,
year = 		1989,
month = 	Mar,
pages = 	{227--248},
note = 		{(An early version appeared as MIT LCS Technical report 
		MIT/LCS/TM-339 (September 1987).)},
tag=		{TOC-display}
}

@inproceedings{Raghavan88,
author=   	{Raghavan, Prabhakar},
title=    	{Learning in Threshold Networks},
booktitle=	{First Workshop on Computational Learning Theory},
month=    	Aug,
year=     	1988,
publisher = 	{Morgan-Kaufmann},
pages = 	{19--27}
}

@article{RabinerJu86,
author=   	{Rabiner, L. R. and B. H. Juang},
title=    	{An Introduction to Hidden Markov Models},
journal=  	{IEEE ASSP Magazine},
year=     	1986,
month=    	Jan,
volume=   	3,
number=   	1,
pages=    	{4--16},
comment=  	{Good introductory overview.}
}

@article{RabinerLeSo83,
author=   	{Rabiner, L. R. and S. E. Levinson and M. M. Sondhi},
title=    	{On the Application of Vector Quantization and Hidden Markov 
		Models to Speaker-Independent, Isolated Word Recognition},
journal=  	{Bell System Technical Journal},
year=     	1983,
month=    	Apr,
volume=   	62,
number=   	4,
pages=    	{1075--1105},
comment=  	{Gets 96.5 percent accuracy on 100-speaker set for digits.}
}

@mastersthesis{Ramstad92,
author = 	{Robert Ramstad},
title = 	{A Constructivist Approach to Artificial Intelligence 
		 Reexamined},
school = 	{MIT EECS Department},
year = 		1992
}


@techreport{RaoKaShIy93,
author=   	{Rao, Nagewara S. V. and Srikumar Kareti and Weimin Shi
		and S. Sitharama Iyengar},
title=    	{Robot Navigation in Unknown Terrains: Introductory
		Survey of Non-Heuristic Algorithms},
institution=  	{Oak Ridge National Laboratory},
year=     	1993,
month=    	Jul,
number=   	{ORNL/TM-12410}
}



@techreport{RaoObGlLi,
author=   	{Rao, Nagewara S. V. and E.M. Oblow and Charles W. Glover and
		Gunar E. Liepins},
title=    	{N-Learners Problem: Fusion of Concepts},
institution=  	{Oak Ridge National Laboratory},
year=     	1991,
month=    	Sep,
number=   	{ORNL/TM-11904, CESAR-91/23}
}

@incollection{Reeke89,
author=   	{Reeke, Jr., George N. and Olaf Sporns and Gerald M. Edelman},
title=    	{Synthetic Neural Modelling:  Comparisons of Population and 
		Connectionist Approaches},
booktitle =  	{Connectionism in Perspective},
editor = 	{R. Pfeifer and Z. Schreter and F. Fogelman-Souli\'{e}
		 and L. Steels},
year=     	1989,
publisher = 	{Elsevier Science Publishers B. V. (North-Holland)}
}

@article{Rissanen78,
author=   	{Rissanen, Jorma},
title=    	{Modeling By Shortest Data Description},
journal=  	{Automatica},
year=     	1978,
volume=   	14,
pages=    	{465--471},
comment=  	{Proposes that the best model is the one that minimizes the
		overall description length of the data, including the 
		parameters of the model.}
}

@article{RissanenLa81,
author=   	{Rissanen, Jorma and Langdon, Jr., Glen G.},
title=    	{Universal Modeling and Coding},
journal=  	{IEEE Transactions on Information Theory},
volume=   	{IT-27},
number=   	1,
year=     	1981,
month=    	Jan,
pages=    	{12--23},
comment=  	{Overview of first-in first-out arithmetic codes. Proves that
		alphabet extensions don't help coding efficiency.}
}

@article{Rissanen83,
author=   	{Rissanen, Jorma},
title=    	{A Universal Prior for Integers and Estimation by Minimum
	  	Description Length},
journal=  	{The Annals of Statistics},
year=     	1983,
volume=   	11,
number=   	2,
pages=    	{416--431}
}

@article{Rissanen86a,
author=	  	{Rissanen, Jorma},
title=    	{Stochastic Complexity and Modeling},
journal=  	{The Annals of Statistics},
year=     	1986,
volume=   	14,
number=   	3,
pages=    	{1080--1100},
comment=  	{Minimum Description Length Principle, and applications.}
}

@techreport{Rissanen86b,
author=   	{Rissanen, Jorma},
title=    	{Stochastic Complexity and Sufficient Statistics},
institution= 	{IBM Research Laboratory (San Jose)},
year=     	1986,
comment=  	{Defines notion of stochastic complexity of a string relative
		to a class of models.  Describes to ways to approximate 
		stochastic complexity.}
}

@book{Rissanen89,
author = 	{Jorma Rissanen},
title = 	{Stochastic Complexity in Statistical Inquiry},
year = 		1989,
publisher = 	{World Scientific},
volume = 	15,
series = 	{Series in Computer Science}
}

@article{Rivest87,
author = 	{Rivest, Ronald L.},
title = 	{Learning Decision Lists},
journal = 	{Machine Learning},
year = 		1987,
volume = 	2,
number = 	3,
pages = 	{229--246},
tag=		{TOC-display}
}


@article{Rivest87b,
author = 	{Ronald L. Rivest},
title = 	{Game Tree Searching by Min/Max Approximation},
journal = 	{Artificial Intelligence},
volume = 	34,
year = 		1987,
month = 	Dec,
pages = 	{77--96}
}

@misc{Rivest88p,
author = 	{Rivest, Ronald L.},
year = 		{Personal communication}
}

@incollection{Rivest91,
author = 	{Rivest, Ronald L.},
title = 	{Theory of Learning: What's Hard and What's Easy to Learn},
booktitle = 	{Research Directions in Computer Science: An {MIT} 
		Perspective},	
publisher = 	{MIT Press},
year = 		1991,
editor = 	{Albert R. Meyer and John V. Guttag and Ronald L. Rivest 
		and Peter Szolovits},
chapter = 	11,
pages = 	{217--227}
}

@article{RivestRe88,
author = 	{Rivest, Ronald L. and Werner Remmele},
title = 	{Machine Learning: the Human Connection},
journal = 	{Siemens Review},
year = 		1988,
month=		{March/April},
volume = 	55,
number = 	{2/88},
pages = 	{33--38},
tag=		{TOC-display}
}

@incollection{RivestRe91,
author = 	{Rivest, Ronald L. and Werner Remmele},
title = 	{Machine Learning},
booktitle = 	{Applied Computer Science and Software: Turning Theory
		into Practice},
publisher = 	{Springer-Verlag},
year = 		1991,
editor = 	{Heinz Schw\"{a}rtzel},
pages = 	{186--200},
comment = 	{Proceedings of International Symposium, September 30 --
		October 1, 1991, in Munich}
}

@inproceedings{RivestSc87a,
author=   	{Rivest, Ronald L. and Robert E. Schapire},
title=    	{A New Approach to Unsupervised Learning in Deterministic
           	Environments},
booktitle=	{Proceeding of the Fourth International Workshop on
           	Machine Learning},
editor=   	{Pat Langley},
address=  	{Irvine, California},
month=    	Jun,
pages=    	{364--375},
year=     	1987,
tag=		{TOC-display}
}

@inproceedings{RivestSc87b,
author=   	{Rivest, Ronald L. and Robert E. Schapire},
title=    	{Diversity-Based Inference of Finite Automata},
booktitle=	{Proceeding of the Twenty-Eighth Annual Symposium on 
	   	Foundations of Computer Science},
address=  	{Los Angeles, California},
month=    	Oct,
pages=    	{78--87},
year=     	1987
}

@inproceedings{RivestSc89,
author = 	{Ronald L. Rivest and Robert E. Schapire},
title = 	{Inference of Finite Automata using Homing Sequences},
booktitle = 	{Proceedings of the Twenty-First Annual ACM Symposium
		 on Theory of Computing},
publisher = 	{ACM},
address = 	{Seattle, Washington},
year = 		1989,
month = 	May,
pages = 	{411-420},
tag=		{TOC-display}
}

@incollection{RivestSc90,
author=   	{Rivest, Ronald L. and Robert E. Schapire},
title=    	{A New Approach to Unsupervised Learning in Deterministic
           	Environments},
booktitle=	{Machine Learning, An Artificial Intelligence Approach},
editor=   	{Yves Kodratoff and Ryszard S. Michalski},
publisher=	{Morgan Kaufmann},
volume=		{III},
year=     	1990,
pages=    	{670--684},
comment= 	{Basically a reprinting of RivestSc87a}
}

@article{RivestSc93,
author = 	{Ronald L. Rivest and Robert E. Schapire},
title = 	{Inference of Finite Automata using Homing Sequences},
journal = 	{Information and Computation},
volume = 	103,
number = 	2,
year = 		1993,
month = 	Apr,
pages = 	{299--347}
}

@inproceedings{RivestSl88a,
author=		{Rivest, Ronald L. and Robert Sloan},
title=		{A New Model for Inductive Inference},
booktitle=	{Proceedings of the Second Conference on Theoretical
		Aspects of Reasoning about Knowledge},
publisher=      {Morgan Kaufmann},
month=		Mar,
year=		1988,
editor=		{Moshe Vardi},
pages=		{13--27},
tag=		{TOC-display}
}

@inproceedings{RivestSl88b,
author = 	{Ronald L. Rivest and Robert Sloan},
title = 	{Learning Complicated Concepts Reliably and Usefully},
year = 		1988,
month =		aug,
booktitle = 	{Proceedings AAAI-88},
orgainzation=	{American Association for Artificial Intelligence},
pages=		{635--639},
tag=		{TOC-display}
}


@article{RivestSl93,
author = 	{Ronald L. Rivest and Robert H. Sloan},
title = 	{On Choosing between Experimenting and Thinking when
		Learning},
journal = 	{Information and Computation},
year = 		1993,
month = 	Sep,
volume = 	106,
number = 	1,
pages = 	{1--25}
}

@article{RivestSl94,
author = 	{Ronald L. Rivest and Robert H. Sloan},
title = 	{A Formal Model of Hierarchical Concept Learning},
journal = 	{Information and Computation},
volume = 	114,
number = 	1,
year = 		1994,
month = 	Oct,
pages = 	{88--114}
}

@article{RivestWi90,
author = 	{Ronald L. Rivest and Patrick Winston},
title = 	{Machine Learning Research at {MIT}},
journal = 	{Siemens Review},
month = 	{Fall},
year = 		{1990},
pages = 	{12--14}
}

@incollection{RivestYi94,
title = 	{Simulation Results for a new two-armed bandit heuristic},
author = 	{Ronald L. Rivest and Yiqun Yin},
booktitle = 	{Computational Learning Theory and Natural Learning Systems},
publisher = 	{MIT Press},
year = 		1994,
editor = 	{S. J. Hanson and G. A. Drastal and R. L. Rivest},
pages = 	{477--486}
}

@incollection{RivestYi95,
title = 	{Being Taught Can be Faster than Asking Questions},
author = 	{Ronald L. Rivest and Yiqun L. Yin},
booktitle = 	{Proceedings of COLT '95},
publisher = 	{ACM},
year = 		1995,
pages = 	{144--151}
}

@article{Robbins52,
author = 	{H. Robbins},
title = 	{Some aspects of the sequential design of experiments},
journal = 	{Bull. Amer. Math. Soc.},
year = 		1952,
volume = 	55,
pages = 	{527--535}
}

@techreport{Romanik91,
author = 	{Kathleen Romanik},
title = 	{Testing As A Dual To Learning},
institution = 	{Dept. of Computer Science, University of Maryland},
year = 		1991,
month = 	Jun,
number = 	{UMIACS-TR-91.93, CS-TR-2704}
}


@article{RoschMeGrJoBr76,
author = 	{E. Rosch and C. Mervis and W. D. Gray and D. Johnson and
		 P. B. Braem},
title = 	{Basic objects in natural categories},
journal = 	{Cognitive Psychology},
year = 		1976,
volume = 	8,
pages = 	{382--439}
}

@article{Rosenblatt58,
author = 	{Rosenblatt, F.},
title = 	{The Perceptron: A Probabilistic Model for Information Storage
		 and Organization in the Brain},
journal = 	{Psychological Review},
year = 		1958,
volume = 	65,
pages = 	{386--407},
comment = 	{Classic article introducing the perceptron model},
note = 		{(Reprinted in {\sl Neurocomputing} (MIT Press, 1988).)}
}

@inproceedings{Rudich85,
author = 	{Rudich, S.},
title = 	{Inferring the structure of a {M}arkov chain from its output},
booktitle = 	{Proceedings 26th Annual Conference on Foundations of Computer Science},
month = 	Oct,
year = 		1985,
pages = 	{321--326},
comment = 	{No journal version, as of 3/5/91. (Unlikely to be one...)}
}

@techreport{RumelhartHiWi85,
author=   	{Rumelhart, David E. and Geoffrey E. Hinton and Ronald J.
		Williams},
title=    	{Learning Internal Representations by Error Propagation},
institution=  	{Institute for Cognitive Science, U.C. San Diego},
year=     	1985,
month=    	Sep,
number=   	{ICS Report 8506},
note=     	{To appear in {\sl Parallel Distributed Processing: 
		Explorations in the Microstructure of Cognition}, Vol. 1, 
		edited by Rumelhart and McClelland (MIT Press)},
comment=  	{Introduces `generalized delta rule' for back-propagating 
		information in a network of deterministic sigmoid (logistic) 
		rules.}
}

@incollection{RumelhartHiMc86,
author=   	{Rumelhart, David E. and Geoffrey E. Hinton and J. L. 
		McClelland},
title=    	{A General Framework for Parallel Distributed Processing},
chapter=  	2,
booktitle=	{Parallel Distributed Processing (Volume I: Foundations)},
editor=   	{David E. Rumelhart and James L. McClelland},
publisher=	{MIT Press},
year=     	1986,
pages=    	{45--76},
comment=  	{Overview of various models}
}

@incollection{RumelhartHiWi86,
author=   	{Rumelhart, David E. and Geoffrey E. Hinton and Ronald J. 
		Williams},
title=    	{Learning Internal Representations by Error Propagation},
booktitle=	{Parallel Distributed Processing -- Explorations in the 
		Microstructure of Cognition},
editor=   	{David E. Rumelhart and James L. McClelland},
publisher= 	{MIT Press},
year=      	1986,
chapter=   	8,
pages=     	{318--362},
comment=   	{Classic paper introducing the generalized delta rule 
		(back-propagation).}
}

@book{RumelhartMc86,
editor=   	{Rumelhart, David E. and McClelland, James L.},
title=    	{Parallel Distributed Processing (Volume I: Foundations)},
publisher=	{MIT Press},
year=     	1986,
pages=    	{45--76},
comment=  	{Overview of various models}
}

@article{RumelhartZi85,
author=   	{Rumelhart, David E. and David Zipser},
title=    	{Feature Discovery by Competitive Learning},
journal=  	{Cognitive Science},
year=     	1985,
volume=   	9,
pages=    	{75--112},
comment=  	{Historical survey of perceptrons etc.; competitive learning 
		in a layered network with inhibitory clusters}
}

@book{DeSaintExupery43,
author=   	{Saint-Exup\`ery, Antoine de},
title=    	{The Little Prince},
publisher=	{Harcourt, Brace, \& World},
year=     	1943
}


@article{SaittaBe93,
author = 	{Lorenza Saitta and Francesco Bergadano},
title = 	{Pattern Recognition and Valiant's Learning Framework},
journal = 	{IEEE Transactions on Pattern Analysis and Machine Intelligence},
year = 		1993,
month = 	Feb,
volume = 	{15},
number = 	2,
pages = 	{145--155}
}


@inproceedings{Sakakibara89,
author = 	{Yasubumi Sakakibara},
title = 	{Learnability in the Presence of Classification Noise},
booktitle = 	{Fujitsu IIAS-SIS Workshop on Computational Learning Theory},
month = 	Nov,
year = 		1989,
pages = 	{1--27}
}

@techreport{Sakakibara90,
author = 	{Yasubumi Sakakibara},
title = 	{An Efficient Robust Algorithm for Learning Decision Lists},
institution = 	{International Institute for Advanced Study of Social
		Information Science, Fujitsu Laboratories Ltd},
year = 		1990,
month = 	Aug,
number = 	{No. 105},
comment = 	{Learns k-DL in the presence of classification noise}
}

@phdthesis{Sakakibara91,
author = 	{Yasubumi Sakakibara},
title =		{Algorithmic Learning of Formal Languages and Decision Trees},
school =	{Tokyo Institute of Technology},
year =		1991,
month =		Oct,
note = 		{(International Institute for Advanced Study of Social
                Information Science, Fujitsu Laboratories Ltd, Research
                Report IIAS-RR-91-22E)}
}

@article{Sakakibara91b,
author=    	{Yasubumi Sakakibara},
title=     	{On Learning from Queries and Counterexamples in the 
		Presence of Noise},
journal=   	{Information Processing Letters},
year=      	1991,
month=     	Mar,
volume=    	37,
number=    	5,
pages=     	{279--284}
}

@article{Samuel59,
author = 	{A. L. Samuel},
title = 	{Some studies in machine learning using the game of checkers},
journal = 	{IBM Journal of Research and Development},
year = 		1959,
month = 	Jul,
volume = 	3,
pages = 	{211--229},
note = 		{(Reprinted in {\em Computers and Thought}, (eds. 
		  E. A. Feigenbaum and J. Feldman), McGraw-Hill, 1963,
		  pages 39--70).}
}

@techreport{Salzberg88,
author = 	{Steven Salzberg},
title = 	{Exemplar-based learning:  theory and implementation},
institution = 	{Harvard University},
year = 		{1988},
type = 		{Center for Research in Computing Technology},
number = 	{TR-10-88},
address = 	{Cambridge, Mass.},
month = 	oct,
comment= 	{Actually uses learning of differences of orthogonal
		rectangles stuff in a practical application (analyzing breast 
		cancer statistics)} 
}

@article{Sauer72,
author = 	{N. Sauer}, 
title = 	{On the Density of Families of Sets},
journal = 	{Journal of Combinatorial Theory Series A},
year = 		1972,
volume = 	13,
pages = 	{145--147}
}


@article{Savitch72, 
author = 	{Walter J. Savitch}, 
title = 	{Maze Recognizing Automata and Nondeterministic Tape 
		Complexity},  
journal = 	{JCSS}, 
year = 		1972,
volume = 	7,
pages = 	{389--403}
}

@mastersthesis{Schapire88,
author=		{Schapire, Robert E.},
title=		{Diversity-Based Inference of Finite Automata},
school=		{MIT Lab.\ for Computer Science},
year=		1988,
month=		may,
note=           {Technical Report MIT/LCS/TR-413},
tag=		{TOC-display}
}

@inproceedings{Schapire89,
author=		{Schapire, Robert E.},
title=		{The Strength of Weak Learnability},
booktitle=	{Proceedings of the Thirtieth Annual Symposium on 
		   Foundations of Computer Science},
address=	{Research Triangle Park, North Carolina},
month=    	Oct,
year=		1989,
tag=		{TOC-display}
}

@inproceedings{Schapire89b,
author=		{Schapire, Robert E.},
title=		{Pattern Languages are Not Learnable},
booktitle = 	{Proceedings of COLT '90},
publisher= 	{Morgan Kaufmann},
year = 		1990,
pages =		{122--129},
tag=		{TOC-display}
}

@article{Schapire90,
author = 	{Schapire, Robert E.},
title = 	{The Strength of Weak Learnability},
journal = 	{Machine Learning},
year = 		1990,
volume = 	5,
number = 	2,
pages = 	{197--227},
tag=		{TOC-display}
}

@phdthesis{Schapire91,
author = 	{Robert Elias Schapire},
title =		{The Design and Analysis of Efficient Learning Algorithms},
school =	{MIT EECS Department},
year =		1991,
month =		Feb,
note = 		{(MIT Laboratory for Computer Science Technical Report
		MIT/LCS/TR-493; reprinted by MIT Press.)}
}

@inproceedings{Schapire91b,
author = 	{Schapire, Robert E.},
title = 	{Learning Probabilistic Read-Once Formulas on Product
		Distributions},
booktitle = 	{Proceedings of the Fourth Annual Workshop on
		Computational Learning Theory},
address = 	{Santa Cruz, California},
year = 		1991,
month = 	Aug,
pages = 	{184--198}
}

@book{Schapire92,
author = 	{Schapire, Robert E.},
title = 	{The Design and Analysis of Efficient Learning Algorithms},
publisher = 	{{MIT} {P}ress},
year = 		{1992},
address = 	{Cambridge, MA},
comment = 	{His PhD thesis in book form}
}

@article{SejnowskiRo87,
author=   	{Sejnowski, Terrence J. and Charles R. Rosenberg},
title=    	{Parallel Networks that Learn to Pronounce English Text},
journal=  	{Journal of Complex Systems},
year=     	1987,
month=    	Feb,
volume=   	1,
number=   	1,
pages=    	{145--168},
comment=  	{Classic paper covering the NETtalk system, which learns to 
		convert English text to speech.}
}

@unpublished{SelfCh87,
author=   	{Self, Matthew and Cheeseman, Peter C.},
title=    	{Bayesian Prediction for Artificial Intelligence},
note=     	{(unpublished manuscript)}
}

@inproceedings{ShackelfordVo88,
author = 	{George Shackelford and Dennis Volper},
title = 	{Learning {k-DNF} with Noise in the Attributes},
booktitle = 	{First Workshop on Computatinal Learning Theory},
year = 		{1988},
address = 	{Cambridge, Mass.\},
month = 	aug,
pages = 	{97--103},
publisher = 	{Morgan Kaufmann},
comment= 	{Shows how to pac learn kDNF with random attribute noise of
		up to one half.}
}

@article{Shannon49,
author=   	{Shannon, Claude},
title=    	{Communication theory of secrecy systems},
journal=  	{Bell System Technical Journal},
year=     	1949,
month=    	Oct,
volume=   	28,
pages=    	{656--715}
}

@techreport{Shapiro81,
author=   	{Shapiro, Ehud Y.},
title=    	{Inductive Inference of Theories From Facts},
institution= 	{Yale University Department of Computer Science},
year=     	1981,
month=    	Feb,
number=   	{Research Report 192},
comment=  	{Uses Horn clauses as representation and backtracing as a 
		method to discover axiom system for a given set of examples}
}

@article{Shapley71,
author=   	{Lloyd S. Shapley},
title=    	{Cores of Convex games},
journal=  	{International Journal of Game Theory},
year=     	1971,
volume=   	1,
number=		1,
pages=    	{11--26}
}


@article{ShimojoIc89,
author = 	{Shinsuke Shimojo and Shin'ichi Ichikawa},
title = 	{Intuitive reasoning about probability:
		 Theoretical and experimental analyses of the 
		 ``problem of the three prisoners''},
journal = 	{Cognition},
volume = 	32,
year = 		1989,
pages = 	{1--24}
}

@article{ShoreGr82,
author=   	{Shore, John E. and Robert M. Gray},
title=    	{Minimum Cross-Entropy Pattern Classification and Cluster 
		Analysis},
journal=  	{IEEE Transactions on Pattern Analysis and Machine 
		Intelligence},
year=     	1982,
month=    	Jan,
volume=   	{PAMI-4},
number=   	1,
pages=    	{11--17},
comment=  	{Uses minimum cross-entropy distribution to derive variation on
	   	nearest-neighbor classification rules.}
}

@article{ShoreJo80,
author=   	{Shore, John E. and Rodney W. Johnson},
title=    	{Axiomatic Derivation of the Principle of Maximum Entropy and
	   	the Principle of Minimum Cross-Entropy},
journal=  	{IEEE Transactions on Information Theory},
volume=   	{IT-26},
number=   	1,
year=     	1980,
month=    	Jan,
pages=    	{26--37},
comment=  	{Derives maximum entropy principle from principles of 
		uniqueness, invariance under coordinate systems, system 
		independence, and subset independence}
}

@article{ShoreJo81,
author=   	{Shore, John E. and Rodney W. Johnson},
title=    	{Properties of Cross-Entropy Minimization},
journal=  	{IEEE Transactions on Information Theory},
volume=   	{IT-27},
number=   	4,
year=     	1981,
month=    	Jul,
pages=    	{472--482},
comment=  	{General overview of properties.}
}

@unpublished{Shvaytser88,
author = 	{Haim Shvaytser},
title = 	{Linear Manifolds are Learnable From Positive Examples},
note = 		{Unpublished manuscript},
month = 	apr,
year = 		{1988}
}

@article{Simon54,
author=   	{Simon, Herbert A.},
title=    	{Spurious Correlation: A Causal Interpretation},
year=     	1954,
journal=  	{Journal of the American Statistical Association},
pages=    	{407--479},
comment=  	{Concludes we need a priori assumptions of independence or 
		causality.}
}

@article{Simon56,
author=   	{Simon, Herbert A.},
title=    	{Rational Choice and the Structure of the Environment},
journal=  	{Psychological Review},
year=     	1956,
volume=   	63,
number=   	2,
pages=    	{129--138},
comment=  	{Model of a creature with multiple goals (e.g. food, water),
		in a tree-structured environment with limited look-ahead.}
}

@incollection{Simon83,
author=   	{Simon, Herber A.},
title=    	{Why Should Machines Learn?},
booktitle=	{Machine Learning, An Artificial Intelligence Approach},
editor=   	{R. S. Michalski and J. G. Carbonell and T. M. Mitchell},
publisher=	{Tioga},
address=  	{Palo Alto, California},
year=     	1983}

@inproceedings{Simon93,
author = 	{Simon, Hans Ulrich},
title =		{General Bounds on the Number of Examples Needed for Learning
		 Probabilistic Concepts},
booktitle = 	{Proceedings of the Sixth Annual {ACM} Workshop on Computational
		Learning Theory},
publisher = 	{{ACM} Press},
year = 		{1993}
}

@article{SinclairJe89,
author = 	{Sinclair, Alistair and Mark Jerrum},
title = 	{Approximate Counting, Uniform Generation and 
		 Rapidly Mixing Markov Chains},
journal = 	{Information and Computation},
year = 		1989,
month = 	Jul,
volume = 	82,
number = 	1,
pages = 	{93--133}
}

@unpublished{Sloan87,
author=   	{Sloan, Robert H.},
title=    	{Some Notes on {C}hernoff Bounds},
note=     	{(Unpublished)},
year=     	1987}

@inproceedings{Sloan88,
author = 	{Robert H. Sloan},
title = 	{Types of Noise in Data for Concept Learning},
booktitle = 	{First Workshop on Computational Learning Theory},
year = 		{1988},
editor = 	{David Haussler and Leonard Pitt},
pages = 	{91--96},
publisher =	{Morgan Kaufmann},
month = 	aug
}

@phdthesis{Sloan89,
author = 	{Robert H. Sloan},
title = 	{Computational Learning Theory: New Models and Algorithms},
school = 	{MIT EECS Department},
year = 		1989,
month = 	May,
note = 		{(Published as MIT/LCS/TR-448.)}
}

@techreport{SmithSt92,
author = 	{Sean W. Smith and Carl Sturtivant},
title = 	{Self-improving reactive agents: case studies of 
		 Reinforcement Learning Frameworks},
year = 		1992,
month = 	Oct,
number = 	{CMU-CS-92-190},
institution = 	{Carnegie Mellon Computer Science Department}
}

@inproceedings{Smith94,
author = 	{Carl H. Smith},
title = 	{Three Decades of Team Learning},
booktitle = 	{Algorithmic Learning Theory},
year = 		{1994},
publisher =	{Springer Verlag},
note = 		{To appear.}
}


@article{Solomonoff64a,
author=   	{Solomonoff, R. J.},
title=    	{A Formal Theory of Inductive Inference. {Part I}.},
year=     	1964,
journal=  	InfCtrl,
volume=   	7,
pages=    	{1--22},
comment=  	{Concerned with extrapolation of sequences.  Defines 
		probability of extension via likelihood random TM program 
		will generate it.}
}

@article{Solomonoff64b,
author=   	{Solomonoff, R. J.},
title=    	{A Formal Theory of Inductive Inference. {Part II}.},
year=     	1964,
journal=  	InfCtrl,
volume=   	7,
pages=    	{224--254},
comment=  	{Continues Part I.  Inference of probabilities and grammars.}
}

@article{Specht67,
author = 	{D. F. Specht},
title = 	{Generation of polynomial discriminant functions for pattern
		recognition},
journal = 	{IEEE Transactions on Electronic Computers},
volume = 	{EC-16},
year = 		1967,
number = 	3,
pages = 	{308--319}
}

@book{Strang86,
author=   	{Strang, Gilbert},
title=    	{Introduction to Applied Mathematics},
publisher=	{Wellesley-Cambridge Press},
year=     	{1986}
}

@article{Summers77,
author = 	{Summers, Phillip D.},
title = 	{A methodology for {LISP} program construction from examples},
journal = 	jacm,
volume = 	24,
number = 	1,
year = 		1977,
month = 	Jan,
pages = 	{161--175}
}

@article{Sutton88,
author = 	{Richard S. Sutton},
title = 	{Learning to Predict by the Methods of Temporal Differences},
journal =	{Machine Learning},
year = 		1988,
month = 	Aug,
volume = 	3,
number = 	1,
pages = 	{9--44}
}

@article{SuttonBa81,
author=   	{Sutton, Richard S. and Andrew G. Barto},
title=    	{Toward a Modern Theory of Adaptive Networks: Expectation and
		Prediction},
journal=  	{Psychological Review},
year=     	1981,
volume=   	88,
number=   	2,
pages=    	{135--170},
comment=  	{Model of neuron where neuron increases output in expectation 
		of being stimulated}
}

@inproceedings{Sutton91,
author=		{Sutton, Richard S.},
title=		{Reinforcement Learning Architectures for Animats},
booktitle = 	{First International Conference on Simulation of Adaptive
		Behavior},
year=		{1991}
}

@unpublished{SuttonBa85,
author=   	{Sutton, Richard S. and Andrew G. Barto},
title=    	{An adaptive network that constructs and uses an internal model
	   	of its world},
year=     	1985,
comment=  	{Maze-learning with adaptive predictor neuron models.},
note = 		{~}
}

@article{Tarjan75,
author=   	{Tarjan, Robert E.},
title=    	{Efficiency of a good but not linear set union algorithm},
journal=  	{Journal of the ACM},
volume=   	22,
number=   	2,
month=    	Apr,
year=     	1975,
pages=    	{215--225}
}

@techreport{TarsiPe84,
author=   	{Tarsi, Michael and Judea Pearl},
title=    	{Algorithmic Reconstruction of Trees},
institution= 	{UCLA Computer Science Department},
year=     	1984,
month=    	Dec,
number=   	{UCLA-ENG-8498},
comment=  	{Describes how to build a tree with n leaves in time n log(n) 
	   	using only test as to whether deepest common ancester of u 
		and v is on the path from root to w, if the max degree is 
		bounded.}
}

@article{Tesauro87,
author = 	{Tesauro, Gerald},
title = 	{Scaling relationships in back-propagation learning:
		 dependence on training set size},
journal = 	{Complex Systems},
year = 		1987,
volume = 	1,
pages = 	{367--372},
comment = 	{Studies learning of 32-bit parity with 8 or 16 or 32 hidden
	         units.  Training time seems to go as 4/3 power of number of
		 samples, up to point where capacity is exceeded.}
}


@techreport{Tesauro90,
author = 	{Tesauro, Gerald},
title = 	{Neurogammon: A Neural-Network Backgammon Program},
institution=  	{IBM T.J. Watson Research Center},
number =	{RC 15619 (\#69436)},
year = 		1990,
month=    	Mar
}


@article{TesauroJa88,
author = 	{Gerald Tesauro and Bob Janssens},
title = 	{Scaling relationships in back-propagation learning},
journal = 	{Complex Systems},
year = 		1988,
volume = 	2,
pages = 	{39--44},
comment = 	{Training time for parity behaves as $4^n$, where $n$
		is the number of inputs.}
}

@article{TesauroSe87,
author = 	{Gerald Tesauro and Terrence J. Sejnowski},
title = 	{A `Neural' Network that Learns to Play Backgammon},
journal = 	{Artificial Intelligence},
volume = 	{39},
number = 	{3},
year = 		1989,
month = 	Jul,
pages = 	{357--390}
}

@article{TesauroSe89,
author = 	{Gerald Tesauro and Terrence J. Sejnowski},
title = 	{A Parallel Network that Learns to Play Backgammon},
journal = 	{Artificial Intelligence},
volume = 	{in press},
year = 		1989
}

@article{TikochinskyTiLe84,
author=   	{Tikochinsky, Y. and N. Z. Tishby and R. D. Levine},
title=    	{Consistent Inference of Probabilities for Reproducible 
		Experiments},
journal=  	{Physical Review Letters},
year=     	1984,
volume=   	52,
number=   	16,
pages=    	{1357--1360},
comment=  	{Justification for maximum-entropy approach.}
}

@book{TouGo74,
author = 	{J. T. Tou and R. C. Gonzalez},
title = 	{Pattern Recognition Principles},
publisher = 	{Addison-Wesley},
year = 		1974
}

@article{Tsitsiklis86,
author = 	{John N. Tsitsiklis},
title = 	{A Lemma on the Multiarmed Bandit Problem},
journal = 	{IEEE Transactions on Automatic Control},
volume = 	{AC-31},
number = 	6,
month = 	Jun,
year = 		1986
}

@article{Turing50,
author = 	{A. M. Turing},
title = 	{Computing Machinery and intelligence},
journal = 	{Mind},
volume = 	59,
year = 		1950,
month = 	Oct,
pages = 	{433--460},
note = 		{(Reprinted in {\em Computers and Thought}, (eds. 
		  E. A. Feigenbaum and J. Feldman), McGraw-Hill, 1963,
		  pages 11--38).},
comment = 	{Classic article on whether computers can think; introduces
		 the `Turing test'.}
}
		  
@article{Valiant84,
author=   	{Valiant, Leslie G.},
title=    	{A Theory of the Learnable},
journal=  	CACM,
year=     	1984,
month=    	Nov,
volume=   	27,
number=   	11,
pages=    	{1134--1142},
comment=  	{Defines `learnability' wrt EXAMPLES and ORACLE using arbitrary
		probability measure on event space.  Shows k-CNF learnable from
		examples only.}
}


@inproceedings{Valiant85,
author= 	{Valiant, Leslie G.},
title=		{Learning disjunctions of conjunctions},
booktitle=	{Proceedings  IJCAI-85},
organization=	{International Joint Committee for Artificial Intelligence},
pages=		{560--566},
publisher= 	{Morgan Kaufmann},
year=		1985,
month=		Aug,
comment= 	{Introduces the malicious error noise model for pac learning}
}

@inproceedings{Valiant89,
author= 	{Valiant, Leslie G.},
title=		{A View of Computational Learning Theory},
booktitle=	{Proceedings of the First NEC Research Symposium},
organization=	{Society for Industrial and Applied Mathematics, Philadelphia},
pages=		{32--51},
publisher= 	{Morgan Kaufmann},
year=		1989
}

@article{VanLehn87,
author= 	{VanLehn, Kurt},
title= 		{Learning One Subprocedure per Lesson},
journal= 	{Artificial Intelligence},
volume = 	31,
number = 	1,
month = 	Jan,
year= 		1987,
pages= 		{1--40}
}

@article{VapnikCh71,
author=   	{Vapnik, V. N. and A. Ya. Chervonenkis},
title=    	{On the Uniform Convergence of Relative Frequencies of Events
		to their probabilities},
journal=  	{Theory of Probability and its Applications},
volume=   	{XVI},
number=   	2,
year=     	1971,
pages=    	{264--280},
comment=  	{Shows that a sufficient condition for the probability of every
	   	set converging to its correct probability is finite VC 
		dimension.}
}

@book{Vapnik82,
author = 	{Vapnik, V. N.},
title = 	{Estimation of Dependences Based on Empirical Data},
publisher = 	{Springer-Verlag},
year = 		{1982},
address = 	{New York}
}

@phdthesis{Wallace89,
author = 	{Richard Scott Wallace},
title = 	{Finding Natural Clusters Through Entropy Minimization},
school = 	{Carnegie Mellon Computer Science Department},
note = 		{Tech. Report CMU-CS-89-183},
year =		1989,
month = 	jun
}

@unpublished{WallacePa??,
author = 	{C. S. Wallace and J. D. Patrick},
title = 	{Coding Decision Trees},
note = 		{To appear ???}
}

@inproceedings{Watkins87,
author=	   	{Watkins, C.J.C.H.},
title=	   	{Combining Cross--Validation and Search},
booktitle= 	{Progress in Machine Learning--Proceedings of EWSL 87: 
	   	2nd European Working Session on Learning},
address=   	{Bled, Yugoslavia},
year=	   	1987,
editor=	   	{Bratko, I. and N. Lavrac},
month=	   	may,
pages=	   	{79--90}
}

% Check school for this entry
@phdthesis{Watkins89,
author = 	{Watkins, C. J. C. H.},
title = 	{Learning from Delayed Rewards},
school = 	{King's College, Oxford},
year = 		{1989},
month = 	May,
note = 		{(To be reprinted by MIT Press.)}
}

@techreport{WaibelHaGiSh87,
author = 	{A. Waibel and T. Hanazawa and G. Ginton and K Shikano},
title = 	{Phoneme Recognition Using Time-Delay Neural Networks},
year = 		1987,
institution = 	{ATR Interpreting Telephony Laboratories}
}

@article{WallaceBo68,
author=   	{Wallace, C.S. and D.M. Boulton},
title=    	{An Information Measure for Classification},
journal=  	{The Computer Journal},
year=     	1968,
volume=   	11,
number=   	2,
pages=    	{185--194},
comment=  	{Introduces idea that `best classification is that which 
		results in the briefest recording of all the attribute 
		information'}
}

@article{Walter50,
author = 	{W. Grey Walter},
title = 	{An Imitation of Life},
journal = 	{Scientific American},
month = 	May,
year =	 	1950,
pages = 	{42--45}
}

@article{Walter51,
author = 	{W. Grey Walter},
title = 	{A Machine That Learns},
journal = 	{Scientific American},
month = 	Aug,
year =	 	1951,
pages = 	{60--63}
}

@article{WenocurDu81,
author=   	{Wenocur, R. S. and R. M. Dudley},
title=    	{Some Special Vapnik-Chervonenkis Classes},
journal=  	{Discrete Mathematics},
year=     	1981,
volume=   	33,
pages=    	{313--318},
comment=  	{Shows VC dimension of half-spaces in n dimensions is n.}
}

@book{Whittle83,
author = 	{Peter Whittle},
title = 	{Optimization Over Time},
volume = 	{II},
publisher = 	{Wiley},
year = 		1983
}

@article{WidrowHo60,
author = 	{Bernard Widrow and Marcian E. Hoff},
title = 	{Adaptive Switching Circuits},
journal =	{1960 IRE WESCON Convention Record},
publisher = 	{IRE},
year = 		1960,
pages = 	{96--104},
note = 		{Reprinted in {\sl Neurocomputing} (MIT Press, 1988).}
}

@techreport{WileyTe85,
author=   	{Wiley, R. Paul and Robert R. Tenney},
title=    	{Performace Evaluation of Stochastic Timed Decision-Free
		Petri Nets},
institution=  	{MIT Laboratory for Information and Decision Sciences},
year=     	1985,
month=    	Mar,
number=   	{LIDS-P-1443},
comment=  	{Interesting model for a stochastic system.}
}

 
@techreport{WilhelmsSk89,
author =	{Wilhelms, Jane and Robert Skinner},
title =		{A "Notion" for Interactive Behavioral Animation Control},
institution =	{University of California, Santa Cruz},
year =		1989,
month =		Feb,
number =	{UCSC-CRL-89-01}
}


@inproceedings{Wilson85,
author=   	{Wilson, Stuart W.},
title=    	{Knowledge Growth in an Artificial Animal},
booktitle= 	{Proceedings of an International Conference on Genetic 
		Algorithms and their Applications},
year=	  	1985,
month=    	Jul,
pages=    	{16--23},
comment=  	{Empirical results for a `critter' wandering around in the 
		woods trying to find food, using a genetic algorithm a la
		Holland to learn general situation/action rules.}
}


@techreport{Winston81,
author = 	{Winston, Patrick H.},
title = 	{Learning New Principles From Precedents and Exercises:
		The Details},
institution = 	{MIT Artificial Intelligence Laboratory},
year = 		1981,
month = 	{May},
number = 	{AIM632},
tag=		{TOC-display}
}


@incollection{Winston75,
author = 	{Winston, Patrick H.},
title = 	{Learning Structural Descriptions from Examples},
booktitle = 	{The Psychology of Computer Vision},
publisher = 	{McGraw-Hill},
year = 		1975,
address = 	{New York},
editor = 	{Winston, Patrick H.},
tag=		{TOC-display}
}


@article{Witten77,
author = 	{Witten, Ian H.},
title = 	{An Adaptive Optimal Controller for Discrete-Time
		Markov Environments},
journal = 	{Information and Control},
year = 		1977,
volume = 	34,
pages = 	{286--295},
comment = 	{Controller sees state of environment at each instant, and
		 gets reward from that state.  Uses discounted expectation
		 of future reward to guide action selection.}
}

@article{Wolpert92,
author = 	{Wolpert, David H.},
title = 	{On the Connection Between In-Sample Testing and
		Generalization Error},
journal = 	{Complex Systems},
year = 		1992,
month =		Feb,
volume = 	{6(1)},
pages = 	{47-94}
}


@article{WoodlandSm89,
author = 	{Woodland, P.C. and S.G. Smyth},
title = 	{An Experimental Comparison of Connectionist and Conventional 
		 Classification Systems on Natural Data},
journal = 	{Speech Communication},
year = 		1989,
month =		Oct,
volume = 	9,
pages = 	{73--82}
}


@article{Wyner72,
author=		{Wyner, A. D.},
title=		{An upper bound on the entropy series},
journal= 	{Information and Control},
volume=		20,
year=		1972,
pages=		{176--181}	
}

@inproceedings{Yao82,
author = 	{Andrew C. Yao},
title = 	{Theory and Applications of Trapdoor Functions},
booktitle = 	{23rd Annual Symposium on Foundations of Computer Science},
year = 		{1982},
pages = 	{80--91}
}

@unpublished{Young87p,
author=   	{Neal Young},
title=    	{Private communication} ,
note=     	{(unpublished)},
year=     	1987
}