Recognition and dualization of disguised bidual Horn functions.

DOI10.1016/S0020-0190(01)00301-5MaRDI QIDQ1853017zbMATH OpenOpenAlexFDO

Authors Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino

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)

Recommendations

• Bidual Horn functions and extensions
• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• scientific article; zbMATH DE number 1136094
• Double Horn functions
• On renamable Horn and generalized Horn functions

Cites work

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

Cited in

(4)

• Incremental polynomial time dualization of quadratic functions and a subclass of degree-\(k\) functions
• On Berge Multiplication for Monotone Boolean Dualization
• Bidual Horn functions and extensions
• Dual subimplicants of positive Boolean functions

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

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