On the hardness of approximating the minimum consistent OBDD problem

DOI10.1007/3-540-61422-2_125MaRDI QIDQ5054808zbMATH OpenOpenAlexFDO

Authors Kouichi Hirata, Shinichi Shimozono, Ayumi Shinohara

Publication date 9 December 2022

Published in Algorithm Theory — SWAT'96 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-61422-2_125

Mathematics Subject Classification ID

Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The nonapproximability of OBDD minimization
• scientific article; zbMATH DE number 1670823
• Asymptotically optimal bounds for OBDDs and the solution of some basic OBDD problems
• On approximation by \(^{\oplus}\)-OBDDs
• Minimization problems for parity OBDDs
• The complexity of minimizing and learning OBDDs and FBDDs
• On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
• The complexity of minimal satisfiability problems
• scientific article; zbMATH DE number 1688380

Cites work

• A theory of the learnable
• Complexity of automaton identification from given data
• Computational limitations on learning from examples
• scientific article; zbMATH DE number 1398051 (Why is no real title available?)
• Learning regular sets from queries and counterexamples
• Lower bounds on learning decision lists and trees
• New approximation algorithms for graph coloring
• On the complexity of minimum inference of regular sets
• On the hardness of approximating minimization problems
• On the necessity of Occam algorithms
• Queries and concept learning
• Reduction of OBDDs in linear time
• The minimum consistent DFA problem cannot be approximated within any polynomial

Cited in

(10)

• Introduction to the OBDD algorithm for the ATP community
• The complexity of minimizing and learning OBDDs and FBDDs
• Hardness of indentifying the minimum ordered binary decision diagram
• The nonapproximability of OBDD minimization
• Minimization problems for parity OBDDs
• Minimization of decision trees is hard to approximate
• On the hardness of approximating the minimum consistent acyclic DFA and decision diagram.
• Finding Small OBDDs for Incompletely Specified Truth Tables Is Hard
• scientific article; zbMATH DE number 1418344 (Why is no real title available?)
• Output-size sensitiveness of OBDD construction through maximal independent set problem

This page was built for publication: On the hardness of approximating the minimum consistent OBDD problem

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