Technical Report Series in Neural and Computational Learning

[John Shawe-Taylor]

The European Community ESPRIT Working Group in Neural and Computational 
       Learning Theory (NeuroCOLT): one new report available

----------------------------------------
NeuroCOLT Technical Report NC-TR-95-050:
----------------------------------------
Learning Ordered Binary Decision Diagrams
by  Ricard Gavald\`a and David Guijarro, Universitat Polit\`ecnica de
    Catalunya

Abstract:
This note studies the learnability of ordered binary decision diagrams
(obdds).  We give a polynomial-time algorithm using membership and
equivalence queries that finds the minimum obdd for the target
respecting a given ordering.  We also prove that both types of queries
and the restriction to a given ordering are necessary if we want
minimality in the output, unless P=NP.  If learning has to occur with
respect to the optimal variable ordering, polynomial-time learnability
implies the approximability of two NP-hard optimization problems:  the
problem of finding the optimal variable ordering for a given obdd and
the Optimal Linear Arrangement problem on graphs.

-----------------------
The Report NC-TR-95-050 can be accessed and printed as follows 

% ftp cscx.cs.rhbnc.ac.uk  (134.219.200.45)
Name: anonymous
password: your full email address
ftp> cd pub/neurocolt/tech_reports
ftp> binary
ftp> get nc-tr-95-050.ps.Z
ftp> bye
% zcat nc-tr-95-050.ps.Z | lpr -l

Similarly for the other technical report.

Uncompressed versions of the postscript files have also been
left for anyone not having an uncompress facility.

A full list of the currently available Technical Reports in the 
Series is held in a file `abstracts' in the same directory.

The files may also be accessed via WWW starting from the NeuroCOLT homepage:

http://www.dcs.rhbnc.ac.uk/neural/neurocolt.html


Best wishes
John Shawe-Taylor