Title of article
On the size of maximum renamable Horn sub-CNF Original Research Article
Author/Authors
Petr Ku?era، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2005
Pages
5
From page
126
To page
130
Abstract
In [Boros, Discrete Appl. Math. 96/97 (1999) 29–40] a lower bound was shown for the size of a maximum renamable Horn sub-CNF of a given CNF. In this short note we show that this bound is tight for complete d-regular formulae on d variables. In fact, we show that this bound is tight even for the size of a maximum q-Horn subformula of a given complete d-regular formulae on d variables; the result for renamable Horn subformulae follows.
Keywords
Horn Boolean formula , Conjunctive normal form , Renamable Horn formula , Maximum renamable Horn sub-CNF , q-Horn formula
Journal title
Discrete Applied Mathematics
Serial Year
2005
Journal title
Discrete Applied Mathematics
Record number
886113
Link To Document