Abstract
We study the problem of bounding from above and below a given set of bit vectors by the set of satisfying truth assignments of a Horn formula. We point out a rather unexpected connection between the upper bounding problem and the problem of generating all transversals of a hypergraph, and settle several related complexity questions.
Research partially supported by the Esprit project ALCOM.
Research partially supported by the National Sience Foundation.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Angluin, M. Frazier, L. Pitt “Learning conjunctions of Horn clauses,” 1990 FOCS pp. 186–192.
C. Berge Graphes et Hypergraphes, Dunod, 1980.
R. Dechter and J. Pearl “Structure identification in relational data,” Artificial Intelligence, 1993.
T. Eiter, G. Gottlob “Identifying the minimal transversals of a hypergraph and related problems,” SIAM J. Comp., to appear.
D. S. Johnson, M. Yannakakis, C. H. Papadimitriou “On generating all maximal independent sets,” IPL 27, 119–123, 1988.
H. A. Kautz, M. J. Kearns, B. Selman “Horn approximations of empirical data,” to appear in Artificial Intelligence, 1993.
H. A. Kautz, M. J. Kearns, B. Selman “Reasoning with characteristic models,” to appear in AAAI, 1993.
C. H. Papadimitriou “On selecting a satsfying truth assignment,” Proc. 1991 FOCS.
B. Selman, H. A. Kautz “Knowledge compilation using Horn approximation,” Proc. AAAI 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kavvadias, D., Papadimitriou, C.H., Sideri, M. (1993). On Horn envelopes and hypergraph transversals. In: Ng, K.W., Raghavan, P., Balasubramanian, N.V., Chin, F.Y.L. (eds) Algorithms and Computation. ISAAC 1993. Lecture Notes in Computer Science, vol 762. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57568-5_271
Download citation
DOI: https://doi.org/10.1007/3-540-57568-5_271
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57568-9
Online ISBN: 978-3-540-48233-8
eBook Packages: Springer Book Archive