Recognition and dualization of disguised bidual Horn functions.

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

Thomas Eiter, Kazuhisa Makino, Toshihide Ibaraki

Publication date: 21 January 2003

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

Full work available at URL: https://doi.org/10.1016/s0020-0190(01)00301-5

zbMATH Keywords

AlgorithmsBoolean functionHorn functionBidual Horn functionDualizationOutput-polynomial

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (1)

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

This page was built for publication: Recognition and dualization of disguised bidual Horn functions.