A Survey of State Merging Strategies for DFA Identification in the Limit

Autores/as

  • Cristina Tîrnăucă

DOI:

https://doi.org/10.17345/triangle8.121-136

Palabras clave:

language, literature, computation

Resumen

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.

Descargas

Los datos de descargas todavía no están disponibles.

Descargas

Publicado

06/29/2018

Cómo citar

Tîrnăucă, C. (2018). A Survey of State Merging Strategies for DFA Identification in the Limit. Triangle, (8), 121–136. https://doi.org/10.17345/triangle8.121-136

Número

Sección

Articles