Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete

Radu Cosmin Dumitru, Ryo Yoshinaka, Ayumi Shinohara

It is well known that computing a minimum deterministic finite automaton consistent with a given set of positive and negative examples is NP-hard. Previous work has identified cond…