2026-07-23T05:46:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25469 2026-03-19T13:29:01Z ddc:004 open_access

Minimal DFAs Witnessing Language Inequivalence Martens, Jan Deterministic Finite Automata Language Inequivalence DFA decomposition Prime languages We study small witnesses for the inequivalence of two regular languages. A natural witness is a distinguishing word, e.g. a word in exactly one of the two languages. We propose using more succinct witnesses in the form of witnessing DFAs. A witnessing DFA recognizes a subset of one of the languages and contains at least one distinguishing word. In this way the DFA expresses behaviour contained in the first language but not the second. We show witnessing DFAs can be used to present more concise witnesses for the inequivalence of two regular languages. We show that the decision problem for the existence of a witnessing DFA of certain size is NP-complete in general, and in P in the special case of unary DFAs. Besides these computational aspects, we study structural properties of witnessing DFAs. Not all languages can be a minimal witness. It turns out that minimal witnesses are exactly the languages that are not decomposable in the union of languages with smaller state-complexity, the so-called prime languages as studied earlier by Kupferman and Mosheiff. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Martens 2026 Is Part Of LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2026.44 urn:nbn:de:0030-drops-254691 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.44 eng https://creativecommons.org/licenses/by/4.0/legalcode