The complexity of learning SUBSEQ\((A)\). (English) Zbl 1180.03041

Fenner, Stephen; Gasarch, William; Postow, Brian

J. Symb. Log. 74, No. 3, 939-975 (2009).

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

Reviewer: Antanas Žilinskas (Vilnius)

MSC:

03D80	Applications of computability and recursion theory
68Q32	Computational learning theory
68Q45	Formal languages and automata

Keywords:

formal languages; machine learning; inductive inference; complexity