On the size of maximum renamable Horn sub-CNF

DOI10.1016/J.DAM.2004.05.007MaRDI QIDQ2387435zbMATH OpenOpenAlexWikidataFDO

Authors Petr Kučera

Publication date 2 September 2005

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2004.05.007

zbMATH Keywords

Conjunctive normal formHorn Boolean formulaMaximum renamable Horn sub-CNFq-Horn formulaRenamable Horn formula

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Maximum renamable Horn sub-CNFs
• Horn upper bounds and renaming
• The Horn renamability, q-Horn and SLUR threshold for random \(k\)-CNF formulas
• Horn Upper Bounds and Renaming
• On renamable Horn and generalized Horn functions

Cites work

• Maximum renamable Horn sub-CNFs
• Polynomial-time inference of all valid implications for Horn and related formulae
• Recognition of q-Horn formulae in linear time
• Variable and term removal from Boolean formulae

Cited in

(2)

• Maximum renamable Horn sub-CNFs
• A sharp threshold for the renameable-Horn and the \(q\)-Horn properties

This page was built for publication: On the size of maximum renamable Horn sub-CNF

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2387435)