×

Inference of reversible languages. (English) Zbl 0759.68070

Summary: We consider inductive inference of certain classes of languages, namely the \(k\)-reversible languages for some fixed \(k\geq 0\), from positive, possibly infinite samples. More precisely, given any rational language \(S\), the sample, we prove that there exists a smallest, with respect to inclusion, \(k\)-reversible language containing it, which is then also rational. After an algebraic proof, we describe a polynomial algorithm performing the inference.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata
68T10 Pattern recognition, speech recognition
PDFBibTeX XMLCite
Full Text: DOI