# zbMATH — the first resource for mathematics

The complexity of learning SUBSEQ$$(A)$$. (English) Zbl 1180.03041
The properties of SUBSEQ($$A$$) are considered, where $$A$$ is any language and SUBSEQ($$A$$) is the set of subsequences of strings in $$A$$. The investigation is focussed on learning of a deterministic finite automaton (DFA) to accept the regular language SUBSEQ($$A$$). The model of learning from the Inductive Inference theory is applied: the desirable DFA is obtained as a limit of the sequence whose steps are defined by the lexicographically enumerated strings of $$A$$ (one string at a time).
##### MSC:
 03D80 Applications of computability and recursion theory 68Q32 Computational learning theory 68Q45 Formal languages and automata
Full Text: