10 citations · 12 across the 3 of their papers we have counts for
Showing cs.FLShow all
2 papers · 1 filter
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…
cs.FL2020
Regular resynchronizability of origin transducers is undecidable
Denis Kuperberg, Jan Martens
We study the relation of containment up to unknown regular resynchronization between two-way non-deterministic transducers. We show that it constitutes a preorder, and that the cor…