Deciding minimal distinguishing DFAs is NP-complete

2023/06/06 by Martens, Jan
#F.4.3 #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)

paper · doi:10.48550/arxiv.2306.03533

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.

Related

• On minimising automata with errors
• The DFAs of Finitely Different Languages
• DFAMiner: Mining minimal separating DFAs from labelled samples
• A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton
• Decomposing Permutation Automata