Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete
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 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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata
Nonuniform families of polynomial-size finite automata, which are series of indexed finite automata having polynomially many inner states, are used in the past literature to solve nonuniform families of promise decision …
GA and ILS for optimizing the size of NFA models
Grammatical inference consists in learning a formal grammar (as a set of rewrite rules or a finite state machine). We are concerned with learning Nondeterministic Finite Automata (NFA) of a given size from samples of pos…
Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory
We present a complete theoretical and empirical framework establishing feedforward neural networks as universal finite-state machines (N-FSMs). Our results prove that finite-depth ReLU and threshold networks can exactly …
HPS: a hierarchical Persian stemming method
In this paper, a novel hierarchical Persian stemming approach based on the Part-Of-Speech of the word in a sentence is presented. The implemented stemmer includes hash tables and several deterministic finite automata in …
Sentence