Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912831904940032 |
|---|---|
| author | Dumitru, Radu Cosmin Yoshinaka, Ryo Shinohara, Ayumi |
| author_facet | Dumitru, Radu Cosmin Yoshinaka, Ryo Shinohara, Ayumi |
| contents | It is well known that computing a minimum DFA consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the case where the input sample is prefix-closed. This formulation is equivalent to computing a minimum Moore machine consistent with observations along its runs. We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings. Furthermore, we show that the problem remains NP-hard as a decision problem even when the sample set consists of the prefixes of a single binary string. Our argument also extends to the corresponding problem for Mealy machines. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_12621 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete Dumitru, Radu Cosmin Yoshinaka, Ryo Shinohara, Ayumi Formal Languages and Automata Theory Machine Learning It is well known that computing a minimum DFA consistent with a given set of positive and negative examples is NP-hard. Previous work has identified conditions on the input sample under which the problem becomes tractable or remains hard. In this paper, we study the computational complexity of the case where the input sample is prefix-closed. This formulation is equivalent to computing a minimum Moore machine consistent with observations along its runs. We show that the problem is NP-hard to approximate when the sample set consists of all prefixes of binary strings. Furthermore, we show that the problem remains NP-hard as a decision problem even when the sample set consists of the prefixes of a single binary string. Our argument also extends to the corresponding problem for Mealy machines. |
| title | Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete |
| topic | Formal Languages and Automata Theory Machine Learning |
| url | https://arxiv.org/abs/2601.12621 |