## Abstract

The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample 1993. Assuming that P ≠ NP, it is shown that for any constant k, no polynomial-time algorithm can be guaranteed to find a consistent DFA with fewer than opt^{k} states, where opt is the number of states in the minimum state DFA consistent with the sample. This result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an NFA, a regular expression, or a regular grammar that is consistent with the sample. A similar nonapproximability result is presented for the problem of finding small consistent linear grammars. For the case of finding minimum consistent DFAs when the alphabet is not of constant size but instead is allowed to vary with the problem specification, the slightly stronger lower bound on approximability of opt^{(1-ε)log logopt} is shown for any ε > 0.

Original language | English (US) |
---|---|

Pages (from-to) | 95-142 |

Number of pages | 48 |

Journal | Journal of the ACM (JACM) |

Volume | 40 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1 1993 |

## Keywords

- approximation algorithms
- minimization of finite state machines
- nonapproximability

## ASJC Scopus subject areas

- Software
- Control and Systems Engineering
- Information Systems
- Hardware and Architecture
- Artificial Intelligence