10 citations · 12 across the 3 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.LO2023
Computing minimal distinguishing Hennessy-Milner formulas is NP-hard, but variants are tractable
Jan Martens, Jan Friso Groote
We study the problem of computing minimal distinguishing formulas for non-bisimilar states in finite LTSs. We show that this is NP-hard if the size of the formula must be minimal.…
cs.FL2023
Deciding minimal distinguishing DFAs is NP-complete
Jan Martens
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 di…