Deciding minimal distinguishing DFAs is NP-complete

arXiv (Cornell University)

Abstract

In this paper, we present a proof of the NP-completeness of computing the smallest Deterministic Finite Automaton (DFA) that distinguishes two given regular languages as DFAs. A distinguishing DFA is an automaton that recognizes a language which is a subset of exactly one of the given languages. We establish the NP-hardness of this decision problem by providing a reduction from the Boolean Satisfiability Problem (SAT) to deciding the existence of a distinguishing automaton of a specific size.

Authors 1

1. Jan Martens corresponding Aachen Leiden Institute of Advanced Computer Science

   Leiden University

   Affiliation as printed

   Leiden Institute of Advanced Computer Science, Leiden University, The Netherlands