Variable and term removal from Boolean formulae

[en] Given a Boolean formula in disjunctive normal form, the variable deletion control set problem consists in finding a minimum cardinality set of variables whose deletion from the formula results in a DNF satisfying some prescribed property. Similar problems can be defined with respect to the fixation of variables or the deletion of terms in a DNF. In this paper, we investigate the complexity of such problems for a broad class of DNF properties.

Disciplines :

Quantitative methods in economics & management
Mathematics

Author, co-author :

Crama, Yves ; Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production

Ekin, Oya

Hammer, Peter L.

Language :

English

Title :

Variable and term removal from Boolean formulae

Publication date :

1997

Journal title :

Discrete Applied Mathematics

ISSN :

0166-218X

eISSN :

1872-6771

Publisher :

Elsevier Science, Amsterdam, Netherlands

Volume :

Pages :

217-230

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 17 October 2016

Statistics

Number of views

87 (5 by ULiège)

Number of downloads

135 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

E. Boros, Y. Crama and P.L. Hammer, Polynomial-time inference of all valid implications for Horn and related formulae, Ann. Math. Artificial Intelligence 1 (1990) 21-32.
E. Boros, Y. Crama, P.L. Hammer and M. Saks, A complexity index for satisfiability problems, SIAM J. Comput. 23 (1994) 45-49.
E. Boros, P.L. Hammer and X. Sun, Recognition of q-Horn formulae in linear time, Discrete Appl. Math. 55 (1994) 1-13.
R.K. Brayton, G.D. Hachtel, C.T. McMullen and A.L. Sangiovanni-Vincentelli, Logic Minimization Algorithms for VLSI Synthesis (Kluwer, Dordrecht, 1984).
M. Buro and H. Kleine Büning, Report on a SAT competition, Technical Report 'Informatik Nr. 110', Universität Paderborn, 1992.
V. Chandru and J.N. Hooker, Detecting embedded Horn structure in propositional logic, Inform. Process. Lett. 42 (1992) 109-111.
G. Gallo and G. Urbani, Algorithms for testing the satisfiability of propositional formulae, J. Logic Programming 7 (1989) 45-61.
M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, CA, 1979).
M.R. Garey, D.S. Johnson and L. Stockmeyer, Some simplified NP-complete graph problems, Theoretical Comput. Sci. 1 (1976) 237-267.
P.L. Hammer and S. Rudeanu, Boolean Methods in Operations Research (Springer, Berlin, 1968).
H.R. Lewis, Renaming a set of clauses as a Horn set. J. ACM 25 (1978) 134-135.
J.M. Lewis and M. Yannakakis, The node-deletion problem for hereditary properties is NP-complete, J. Comput. System Sci. 20 (1980) 219-230.
S. Muroga, Threshold Logic and its Applications (Wiley-Interscience, New York, 1971).
K. Truemper, Monotone decomposition of matrices, Technical Report UTDCS-1-94, 1994.
M. Yannakakis, Node- and edge-deletion NP-complete problems. Proceedings of Tenth Annual ACM Symposium on Theory of Computing (1978) 253-264.