Recognition and dualization of disguised bidual Horn functions.

DOI10.1016/S0020-0190(01)00301-5zbMath1051.68139MaRDI QIDQ1853017

Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino

Publication date: 21 January 2003

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Algorithms; Boolean function; Horn function; Bidual Horn function; Dualization; Output-polynomial

Mathematics Subject Classification ID

68W05: Nonnumerical algorithms

Related Items

Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions

Cites Work

• Unnamed Item
• Unnamed Item
• Removing redundancy from a clause
• Dualization of regular Boolean functions
• On generating all maximal independent sets
• LTUR: A simplified linear-time unit resolution algorithm for Horn formulae and computer implementation
• Horn functions and their DNFs
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• Double Horn functions
• Horn functions and submodular Boolean functions
• Bidual Horn functions and extensions
• Complexity of identification and dualization of positive Boolean functions
• On the Complexity of Dualization of Monotone Disjunctive Normal Forms
• The Complexity of Enumeration and Reliability Problems
• Recognizing disguised NR(1) instances of the satisfiability problem
• On the Complexity of Timetable and Multicommodity Flow Problems
• Renaming a Set of Clauses as a Horn Set
• The Maximum Latency and Identification of Positive Boolean Functions
• Identifying the Minimal Transversals of a Hypergraph and Related Problems
• Dual subimplicants of positive Boolean functions