TY - JOUR
T1 - On the hardness of approximating the minimum consistent acyclic DFA and decision diagram
AU - Shimozono, Shinichi
AU - Hirata, Kouichi
AU - Shinohara, Ayumi
PY - 1998/5/29
Y1 - 1998/5/29
N2 - We show that the problems to find the smallest acyclic DFA and OBDD with a fixed order of variables that are consistent with given sets of positive and negative examples are not approximable in polynomial time within worst case factors n1/28 and n1/21, respectively, with the input size n unless P = NP.
AB - We show that the problems to find the smallest acyclic DFA and OBDD with a fixed order of variables that are consistent with given sets of positive and negative examples are not approximable in polynomial time within worst case factors n1/28 and n1/21, respectively, with the input size n unless P = NP.
KW - Approximation
KW - Combinatorial problems
KW - Computational complexity
KW - Data structures
KW - Finite state machine minimization
UR - http://www.scopus.com/inward/record.url?scp=0043265939&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0043265939&partnerID=8YFLogxK
U2 - 10.1016/s0020-0190(98)00065-9
DO - 10.1016/s0020-0190(98)00065-9
M3 - Article
AN - SCOPUS:0043265939
SN - 0020-0190
VL - 66
SP - 165
EP - 170
JO - Information Processing Letters
JF - Information Processing Letters
IS - 4
ER -