On-line algorithms for satisfiability problems with uncertainty

被引：12

作者：

Ausiello, G ^{[1
]}

Giaccio, R ^{[1
]}

机构：

[1] UNIV ROMA LA SAPIENZA, DIPARTIMENTO INFORMAT & SISTEMIST, I-00198 ROME, ITALY

来源：

THEORETICAL COMPUTER SCIENCE | 1997年 / 171卷 / 1-2期

关键词：

D O I：

10.1016/S0304-3975(96)00123-5

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 Horn-SAT problem and find a minimum model for the formula working on the dynamic weighted hypergraph representation. These algorithms make increasing assumptions on the formula and we find that the second one solves the on-line Horn-SAT problem with a total time linear in the size of the formula, matching the optimal result for Boolean Horn formulae.

引用

页码：3 / 24

页数：22

共 26 条

[1] DYNAMIC MAINTENANCE OF DIRECTED HYPERGRAPHS [J].

AUSIELLO, G ;

NANNI, U ;

ITALIANO, GF .

THEORETICAL COMPUTER SCIENCE, 1990, 72 (2-3) :97-117

[2] ONLINE ALGORITHMS FOR POLYNOMIALLY SOLVABLE SATISFIABILITY PROBLEMS [J].

AUSIELLO, G ;

ITALIANO, GF .

JOURNAL OF LOGIC PROGRAMMING, 1991, 10 (01) :69-90

[3] MINIMAL REPRESENTATION OF DIRECTED HYPERGRAPHS [J].

AUSIELLO, G ;

DATRI, A ;

SACCA, D .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :418-431

[4]

BONISSONE PP, 1985, 1ST P WORKSH UNC ART, P57

[5]

Buchanan B.G., 1984, Rule Based Expert Systems: The Mycin Experiments of the Stanford Heuristic Programming Project (The Addison-Wesley series in artificial intelligence)

[6]

CAMBINI R, 1992, TR192 U PIS DIP INF

[7]

Dubois D., 1980, FUZZY SETS SYSTEMS

[8]

DUDA RO, 1976, AFIPS C P NEW YORK, P1074

[9] DIRECTED HYPERGRAPHS AND APPLICATIONS [J].

GALLO, G ;

LONGO, G ;

PALLOTTINO, S ;

NGUYEN, S .

DISCRETE APPLIED MATHEMATICS, 1993, 42 (2-3) :177-201

[10]

GARVEY TD, 1981, 7TH P INT JOINT C AR, P319

← 1 2 3 →