RFSA

Learning regular languages using RFSA par 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.


References in zbMATH (referenced in 14 articles , 1 standard article )

Showing results 1 to 14 of 14.
Sorted by year (citations)

  1. Björklund, Johanna; Fernau, Henning; Kasprzik, Anna: Polynomial inference of universal automata from membership and equivalence queries (2016)
  2. Verwer, Sicco; Eyraud, Rémi; de la Higuera, Colin: PAutomaC: a probabilistic automata and hidden Markov models learning competition (2014)
  3. Kasprzik, Anna: Four one-shot learners for regular tree languages and their polynomial characterizability (2013)
  4. Vázquez de Parga, Manuel; García, Pedro; López, Damián: A polynomial double reversal minimization algorithm for deterministic finite automata (2013)
  5. García, Pedro; López, Damián; Vázquez de Parga, Manuel: Polynomial characteristic sets for $DFA$ identification (2012)
  6. de la Higuera, Colin: Grammatical inference. Learning automata and grammars. (2010)
  7. García, Pedro; Vázquez de Parga, Manuel; Cano, Antonio; López, Damián: On locally reversible languages (2009)
  8. García, Pedro; de Parga, Manuel Vázquez; López, Damián: On the efficient construction of quasi-reversible automata for reversible languages (2008)
  9. de la Higuera, Colin: A bibliographical study of grammatical inference (2005)
  10. Coste, François; Fredouille, Daniel; Kermorvant, Christopher; de la Higuera, Colin: Introducing domain and typing bias in automata inference (2004)
  11. Coste, François; Fredouille, Daniel: Unambiguous automata inference by means of state-merging methods. (2003)
  12. Denis, François; Lemay, Aurélien; Terlutte, Alain: Some classes of regular languages identifiable in the limit from positive data (2002)
  13. Esposito, Yann; Lemay, Aurélien; Denis, François; Dupont, Pierre: Learning probabilistic residual finite state automata (2002)
  14. Denis, François; Lemay, Aurélien; Terlutte, Alain: Learning regular languages using RFSA (2001)