Buscar

Estamos realizando la búsqueda. Por favor, espere...

A survey of state merging strategies for DFA identification in the limit

Abstract: Identication of deterministic nite automata (DFAs) has an extensive history, both in passive learning and in active learning. Intractability results by Gold [5] and Angluin [1] show that nding the smallest automaton consistent with a set of accepted and rejected strings is NP-complete. Nevertheless, a lot of work has been done on learning DFAs from examples within specic heuristics, starting with Trakhtenbrot and Barzdin's algorithm [15], rediscovered and applied to the discipline of grammatical inference by Gold [5]. Many other algorithms have been developed, the convergence of most of which is based on characteristic sets: RPNI (Regular Positive and Negative Inference) by J. Oncina and P. García [11, 12], Traxbar by K. Lang [8], EDSM (Evidence Driven State Merging), Windowed EDSM and Blue- Fringe EDSM by K. Lang, B. Pearlmutter and R. Price [9], SAGE (Self-Adaptive Greedy Estimate) by H. Juillé [7], etc. This paper provides a comprehensive study of the most important state merging strategies developed so far.

 Autoría: Cristina Tirnauca

 Fuente: Triangle, 2012, 8(12), 121-136

 Editorial: Universitat Rovira i Virgili

 Año de publicación: 2012

 Nº de páginas: 15

 Tipo de publicación: Artículo de Revista

 ISSN: 2013-939X