Residual languages are important and natural components of regular languages. Most approaches in grammatical inference rely on this notion. Classical algorithms such as RPNI try to identify prefixes of positive learning examples which give rise to identical residual languages. Here, we study inclusion relations between residual languages. We lead experiments which show that when regular languages are randomly drawn using non deterministic representations, the number of inclusion relations is very important. We introduced in previous articles a new class of automata which is defined using the notion of residual languages: residual finite state automata (RFSA). RFSA representations of regular languages may have far less states than DFA representations. We prove that RFSA are not polynomially characterizable. However, we design a new learning algorithm, DeLeTe2, based on the search of inclusion relations between residual languages, which produces a RFSA and have both good theoretical properties and good experimental performances.
展开▼
