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).


03D80 Applications of computability and recursion theory
68Q32 Computational learning theory
68Q45 Formal languages and automata
Full Text: DOI Link