Xref: utzoo comp.ai:8918 comp.theory:1759
Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!relay.nswc.navy.mil!oasys!mimsy!mojo!eng.umd.edu!lev
From: lev@eng.umd.edu (Lev Novik)
Newsgroups: comp.ai,comp.theory
Subject: Logical question
Message-ID: <1991Apr3.153544.6585@eng.umd.edu>
Date: 3 Apr 91 15:35:44 GMT
Sender: news@eng.umd.edu (C-News)
Reply-To: lev@eng.umd.edu (Lev Novik)
Organization: University of Maryland, College Park
Lines: 22

I have a problem, for which I assume there's a classical solution, but so far I
wasn't able to find one.

##PROBLEM##

Suppose we have a set of elements, and a set of formulas for those elements.
Formula is a pair : (subset, element), which means that given all elements in
THE SUBSET, we can find THE ELEMENT. 

Find A smallest subset of elements, so that everything else may be derived from
it using the given formulas. (Note, that we need A SMALLEST set, not a set that 
cannot be reduced).
###########

I would appreciate any algorithm or reference to one.
Thanks in advance

 __________________________________________________________________________
|  Lev Novik                         \/   phone : (301) 345-2464           |
|  University of Maryland            /\   e-mail: lev@cs.umd.edu           |
|  College Park                      \/                                    |
 --------------------------------------------------------------------------