No Detail Found!

On the maximal minimal cube lengths in distinct DNF tautologies

Author(s)
Manuel Kauers Institute for Algebra, Johannes Kepler University Linz,Linz,Austria
Martina Seidl Institute for Formal Models and Verification, Johannes Kepler University Linz,Linz,Austria
Doron Zeilberger Department of Mathematics, Rutgers University (New Brunswick),Piscataway,USA
Abstract
Inspired by a recent article by Zaleski and Zeilberger [arXiv:1801.05097 [math.CO]; Math. Mag., To appear], we investigate the question of determining the largest k for which there exist Boolean formulas in disjunctive normal form (DNF) with n variables, which are tautologies, whose conjunctions have distinct sets of variables, and such that all the conjunctions have at least k literals. Using a SAT solver, we answer the question for some sizes which Zaleski and Zeilberger left open. We also determine the corresponding numbers for DNFs obeying certain symmetries.
Publication Details
Page(s) 47-51
DOI DOI not available
Published Journal: Discrete Mathematics Letters, Volume: 2, Issue: 0, Year: 2019

Request the full text from PASTIC

Keywords
SAT solving, covering systems, symmetry breaking
References
Artin M. .1991 .. , : .
Biere A. .2017 .. Proceedings of SAT Competition 2017 - Solver and Benchmark Descriptions, : .
Biere A.,Heule M.,Maaren H. Van,T. H. Van .2009 .. Artificial Intelligence and Applications, 185 : .
Chen J .2010 .A new SAT encoding of the at-most-one constraint. Proceedings of the Tenth International Workshop of Constraint Modelling and Reformulation, : .
Erdo P. .1950 .˝s, On integers of the form 2k + p and some related problems, Summa Brasil. , 2 : 113-123.
Frisch A. M.,Giannaros P. A. .2010 .SAT encodings of the at-most-k constraint: some old, some new, some fast, some slow. Proceedings of the Tenth International Workshop of Constraint Modelling and Reformulation, : .
Knuth D. E.,Fascicle 6,Addison-Wesley 6 .2015 .. The Art of Computer Programming, 4 : .
Sakallah K. A.,Biere M.,Heule H. Van,Maaren T. .2009 .Symmetry and satisfiability. Artificial Intelligence and Applications, 185 : .
Zaleski A.,Zeilberger D. .1801 .Boolean function analogs of covering systems. , : .
0

Citations

0

Downloads

16

Views