TY - JOUR
T1 - Universal automata and NFA learning
AU - García, Pedro
AU - Vázquez de Parga, Manuel
AU - Álvarez, Gloria I.
AU - Ruiz, José
N1 - Funding Information:
Work partially supported by Spanish Ministry of Education and Science research project TIN2007-60769. Corresponding author. E-mail addresses: [email protected] (P. García), [email protected] (M. Vázquez de Parga), [email protected] (G.I. Álvarez), [email protected] (J. Ruiz).
PY - 2008/11/6
Y1 - 2008/11/6
N2 - The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done "randomly".
AB - The aim of this paper is to develop a new algorithm that, with a complete sample as input, identifies the family of regular languages by means of nondeterministic finite automata. It is a state-merging algorithm. One of its main features is that the convergence (which is proved) is achieved independently from the order in which the states are merged, that is, the merging of states may be done "randomly".
KW - Finite automata
KW - Grammatical inference
KW - Universal automaton
UR - https://www.scopus.com/pages/publications/50249162059
U2 - 10.1016/j.tcs.2008.05.017
DO - 10.1016/j.tcs.2008.05.017
M3 - Article
AN - SCOPUS:50249162059
SN - 0304-3975
VL - 407
SP - 192
EP - 202
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - 1-3
ER -