Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
On-line algorithms for satisfiability problems with uncertainty
verfasst von : Roberto Giaccio
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In this paper the problem of the on-line satisfiability of a Horn formula with uncertainty is addressed; we show how to represent a significant class of formulae by weighted directed hypergraphs and we present two algorithms that solve the on-line SAT problem and find a minimal interpretation for the formula working on the dynamic hypergraph representation. These algorithms make increasing assumptions on the formula and we will find that the second one solves the on-line SAT problem with a total time linear in the size of the formula, matching the optimal result for boolean Horn formulae.